图算法

图算法是处理关系型数据的核心工具,本篇梳理四类高频算法:遍历、最短路、最小生成树与拓扑排序。

BFS 与 DFS 遍历

广度优先搜索(BFS)与深度优先搜索(DFS)都是图的基本遍历方式,时间复杂度均为 O(V + E)。

• BFS 使用队列,按层向外扩展,适合求解无权图最短路径与层级关系。
• DFS 使用栈(或递归),沿一条路径深入到底再回溯,适合求解连通分量、拓扑排序与路径存在性问题。

from collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                q.append(v)
    return visited

最短路算法

• Dijkstra:单元最短路,处理非负权图,使用优先队列(小顶堆)维护待扩展顶点,复杂度 O((V + E) log V)。负权边下结果不可靠。
• Floyd-Warshall:多源最短路,允许负权边但不允许负权环,核心是三层循环的状态转移 dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]),复杂度 O(V³),空间 O(V²)。
• Bellman-Ford:可检测负权环,单元最短路,复杂度 O(V·E)。

最小生成树

• Prim:从一个顶点出发,每次选择横切边中权值最小者加入生成树,适合稠密图,使用堆优化后 O(E log V)。
• Kruskal:将所有边按权值排序,依次加入不构成环的边(用并查集判定),适合稀疏图,复杂度 O(E log E)。

拓扑排序(Kahn 算法)

拓扑排序针对有向无环图(DAG),输出顶点的线性序列,使得每条有向边 u → v 中 u 都出现在 v 之前。基于 BFS 的 Kahn 算法步骤:

1. 计算所有顶点的入度。
2. 将入度为 0 的顶点入队。
3. 反复出队,加入结果序列,并将其所有邻居的入度减 1;若邻居入度变为 0 则入队。
4. 若结果序列长度小于 V,图中存在环。

from collections import deque, defaultdict

def topo_sort(n, edges):
    indeg = [0] * n
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None