DEV Community

Woody
Woody

Posted on

about Graph

#graphql

Image description

Image description

Image description

🧩 一、图的常用数据结构

✅ 1. 邻接矩阵（Adjacency Matrix）

  • 用二维数组表示图中点与点之间的连接关系。
  • 适合稠密图（边多）。 
# 无向图：邻接矩阵
graph = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0]
]
Enter fullscreen mode Exit fullscreen mode

✅ 2. 邻接表（Adjacency List）

  • 用字典或数组 + 链表表示每个节点的邻居。
  • 适合稀疏图（边少）。 
# 无向图：邻接表
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}
Enter fullscreen mode Exit fullscreen mode

✅ 3. 边集数组（Edge List）

  • 用一组边表示整个图：[起点, 终点, 权重] 
edges = [
    (0, 1, 10),
    (0, 2, 5),
    (1, 2, 3)
]
Enter fullscreen mode Exit fullscreen mode

🚀 二、图的经典算法分类 + 经典习题

类型 经典算法 常见题目（LeetCode编号）
遍历 DFS/BFS 200 岛屿数量、695 最大岛屿面积、417 太平洋大西洋水流问题
最短路径 Dijkstra、Floyd、Bellman-Ford 743 网络延迟时间、787 K站中转内最便宜的航班
最小生成树 Prim、Kruskal 1584 连接所有点的最小费用
拓扑排序 Kahn算法、DFS逆后序 207 课程表、210 课程表 II
强连通分量 Tarjan、Kosaraju 1192 查找集群内的关键连接
并查集 Union-Find 547 省份数量、684 冗余连接
二分图 染色法 / BFS/DFS 785 判断是否为二分图

📚 三、推荐刷题顺序（从基础到进阶）

✅ 初级阶段（掌握图的遍历）

✅ 中级阶段（最短路径 & 拓扑排序）

✅ 进阶阶段（MST、强连通分量、二分图）

🔧 四、建议搭配练习

  • 每种算法都手写一遍，尤其是：

    • DFS 递归和非递归写法
    • Dijkstra（优先队列）
    • Kruskal（并查集）
    • Tarjan 强连通分量

  • 建议使用 Python / Java / C++ 各写一题，熟悉图的接口封装。

如果你需要我帮你 生成题单（markdown 文件） 或者 某个算法的代码模板（比如 Dijkstra、Kruskal），可以告诉我，我会立即生成。

是否需要我为你创建一个图论刷题计划或知识脑图？

Top comments (0)