← 知识手册目录核心数据结构 · GESP 6 / 7 / 8 级相关跳到完整速查 ↓

PYTHON KNOWLEDGE · 15

树、图、DFS、BFS 与最短路

从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。

GESP 6 级GESP 7 级GESP 8 级

01 · FORMAL DEFINITION

正式定义

图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。

02 · MUST KNOW

学完这一章，必须说清楚的规则

  1. 01

    邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。

  2. 02

    DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。

  3. 03

    无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。

  4. 04

    树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。

  5. 05

    Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。

  6. 06

    Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。

03 · RUNNABLE EXAMPLE

可运行示例与因果解释

PYTHON
from collections import deque
graph = [[1, 2], [0, 3], [0, 3], [1, 2]]
dist = [-1] * len(graph)
dist[0] = 0
queue = deque([0])
while queue:
    u = queue.popleft()
    for v in graph[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            queue.append(v)
print(dist)

COMMON PITFALLS

常见误区

  • 遍历一般图时不记录 visited
  • 对负权边使用 Dijkstra
  • 混淆最短路径树与最小生成树
  • 递归 DFS 忽略深度限制

SCOPE & BOUNDARIES

适用边界

  • 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
  • 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。