Skip to main content

​
核心认知

图是一种比链表和树更自由的数据结构。 它由两部分组成：
  • 节点
  • 边
如果你把现实问题抽象成“对象之间的连接关系”，很多时候就是在建图。

​
图论题真正难在哪

图论题的难点经常不是算法名，而是建图。 你要先回答：
  • 谁是节点
  • 谁和谁之间有边
  • 这条边有没有方向
  • 这条边有没有权重
图一旦建对，后面的 DFS、BFS、Dijkstra 往往就顺了。

​
常见存储方式

图的两种经典表示方式是：
  • 邻接矩阵
  • 邻接表
算法题里更常见的是邻接表，因为更省空间，也更适合遍历。 
graph = {
    0: [1, 2],
    1: [2],
    2: [3],
    3: []
}
这个写法就可以理解成一个简单的有向图。

​
一个最基础的 Python 例子

图论题入门最常见的就是 DFS。 
def dfs(graph: dict[int, list[int]], start: int) -> list[int]:
    visited = set()
    order: list[int] = []

    def traverse(node: int) -> None:
        if node in visited:
            return
        visited.add(node)
        order.append(node)

        for nxt in graph[node]:
            traverse(nxt)

    traverse(start)
    return order
这里最关键的不是递归本身，而是 visited。
只要图里可能有环，就一定要警惕重复访问。

​
图和树的区别

树其实可以看作一种特殊的图。 和树相比，图更复杂的地方在于：
  • 可能有环
  • 可能不止一个入口
  • 节点之间的关系不一定是层级型
所以很多图论题的第一反应应该是：
  • 需不需要去重
  • 会不会走回头路

​
常见题型

图论题经常会出现这些方向：
  • DFS / BFS 遍历
  • 连通性问题
  • 拓扑排序
  • 最短路径
  • 最小生成树
  • 并查集
你不用一开始就全部掌握，但至少要先把 DFS 和 BFS 稳住。

​
最短路径为什么重要

只要题目在问：
  • 最少走几步
  • 最小代价是多少
那你就应该对“最短路径”保持敏感。 在无权图里，BFS 往往就够用了。
在带权图里，常见会用到 Dijkstra。

​
学习建议

建议按这个顺序练：
  • 图的 DFS 和 BFS
  • 岛屿问题
  • 拓扑排序
  • 并查集
  • 最短路径
当你开始习惯先“建图”，再“选算法”，图论题会清晰很多。