计算机基础

04. 图算法

深入图的存储结构与经典算法：DFS/BFS 遍历、Dijkstra 最短路径、最小生成树、拓扑排序，掌握图论问题的核心解法。

spcent 4 分钟阅读 1647 字

1. 图的表示

1.1 邻接矩阵

适合稠密图（边数接近 n²），支持 O(1) 判边。

# n 个节点的图
n = 5
# 有权图：matrix[i][j] = 边权，无边 = inf
inf = float('inf')
adj_matrix = [[inf] * n for _ in range(n)]
for i in range(n):
    adj_matrix[i][i] = 0

# 添加边
adj_matrix[0][1] = 4
adj_matrix[1][2] = 1

1.2 邻接表

适合稀疏图（边数远小于 n²），空间 O(V + E)。

from collections import defaultdict

class Graph:
    def __init__(self):
        self.adj = defaultdict(list)  # 节点 -> [(邻居, 权重)]

    def add_edge(self, u, v, w=1, directed=False):
        self.adj[u].append((v, w))
        if not directed:
            self.adj[v].append((u, w))

2. 图的遍历

2.1 DFS（深度优先搜索）

def dfs(graph, start):
    visited = set()
    result = []

    def _dfs(node):
        visited.add(node)
        result.append(node)
        for neighbor, _ in graph.adj[node]:
            if neighbor not in visited:
                _dfs(neighbor)

    _dfs(start)
    return result

# 非递归 DFS（栈模拟）
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        result.append(node)
        for neighbor, _ in reversed(graph.adj[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    return result

2.2 BFS（广度优先搜索）

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor, _ in graph.adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

BFS 的层级特性：第一次访问到某个节点时，路径长度最短（无权图）。

3. 最短路径算法

3.1 Dijkstra 算法（单源，非负权）

贪心策略，每次确定距离源点最近的节点。

import heapq

def dijkstra(graph, start, n):
    """O(E log V)"""
    dist = {i: float('inf') for i in range(n)}
    dist[start] = 0
    pq = [(0, start)]  # (距离, 节点)
    parent = {start: None}

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue  # 旧条目，跳过
        for v, w in graph.adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, parent

# 重构路径
def reconstruct_path(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent.get(target)
    return path[::-1]

3.2 Bellman-Ford 算法（可处理负权边）

def bellman_ford(edges, n, start):
    """
    edges: [(u, v, w), ...]
    可检测负权环
    """
    dist = [float('inf')] * n
    dist[start] = 0

    # 松弛 n-1 次
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # 检测负权环
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("图中存在负权环")

    return dist

3.3 Floyd-Warshall（全源最短路径）

def floyd_warshall(n, adj):
    """O(n³)，动态规划"""
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in adj:
        dist[u][v] = w

    for k in range(n):      # 中间点
        for i in range(n):  # 起点
            for j in range(n):  # 终点
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

3.4 算法选择指南

算法时间适用场景能否处理负权
DijkstraO(E log V)单源、非负权❌
Bellman-FordO(VE)单源、含负权✅
Floyd-WarshallO(V³)全源✅（无负权环）
SPFAO(E) 平均Bellman-Ford 优化✅

4. 最小生成树（MST）

4.1 Kruskal 算法（边贪心）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # 按秩合并
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(edges, n):
    """
    edges: [(u, v, w), ...]
    返回 MST 的总权重和边列表
    """
    edges.sort(key=lambda x: x[2])  # 按权重排序
    uf = UnionFind(n)
    mst_weight = 0
    mst_edges = []

    for u, v, w in edges:
        if uf.union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break

    return mst_weight, mst_edges

4.2 Prim 算法（点贪心）

import heapq

def prim(graph, n, start=0):
    """O(E log V)，类似 Dijkstra"""
    visited = [False] * n
    min_heap = [(0, start, -1)]  # (权重, 当前节点, 父节点)
    mst_weight = 0
    mst_edges = []

    while min_heap and len(mst_edges) < n - 1:
        w, u, p = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        mst_weight += w
        if p != -1:
            mst_edges.append((p, u, w))

        for v, w2 in graph.adj[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (w2, v, u))

    return mst_weight, mst_edges

5. 拓扑排序

适用：有向无环图（DAG），如任务调度、依赖解析。

5.1 Kahn 算法（BFS）

def topo_sort(graph, n):
    in_degree = [0] * n
    for u in range(n):
        for v, _ in graph.adj[u]:
            in_degree[v] += 1

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []

    while queue:
        u = queue.popleft()
        result.append(u)
        for v, _ in graph.adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(result) != n:
        raise ValueError("图中存在环，无法拓扑排序")
    return result

5.2 DFS 版本

def topo_sort_dfs(graph, n):
    visited = [0] * n  # 0=未访问, 1=访问中, 2=已完成
    result = []

    def dfs(u):
        visited[u] = 1
        for v, _ in graph.adj[u]:
            if visited[v] == 1:
                raise ValueError("图中存在环")
            if visited[v] == 0:
                dfs(v)
        visited[u] = 2
        result.append(u)

    for i in range(n):
        if visited[i] == 0:
            dfs(i)

    return result[::-1]  # 逆序输出

6. 其他经典问题

6.1 二分图检测

def is_bipartite(graph, n):
    color = [-1] * n  # -1=未染色, 0/1=两种颜色
    for start in range(n):
        if color[start] != -1:
            continue
        queue = deque([start])
        color[start] = 0
        while queue:
            u = queue.popleft()
            for v, _ in graph.adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False
    return True

6.2 强连通分量（Kosaraju 算法）

def kosaraju(graph, n):
    """两次 DFS，O(V + E)"""
    # 第一次：记录完成顺序
    visited = [False] * n
    order = []

    def dfs1(u):
        visited[u] = True
        for v, _ in graph.adj[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)

    for i in range(n):
        if not visited[i]:
            dfs1(i)

    # 构建转置图
    rev_graph = Graph()
    for u in range(n):
        for v, w in graph.adj[u]:
            rev_graph.add_edge(v, u, w, directed=True)

    # 第二次：按逆序遍历转置图
    visited = [False] * n
    sccs = []

    def dfs2(u, component):
        visited[u] = True
        component.append(u)
        for v, _ in rev_graph.adj[u]:
            if not visited[v]:
                dfs2(v, component)

    for u in reversed(order):
        if not visited[u]:
            component = []
            dfs2(u, component)
            sccs.append(component)

    return sccs

7. 算法选择速查表

问题推荐算法时间复杂度
无权图最短路径BFSO(V + E)
非负权图单源最短Dijkstra + 堆O(E log V)
含负权图单源Bellman-Ford / SPFAO(VE) / O(E)
全源最短路径Floyd-WarshallO(V³)
最小生成树Kruskal / PrimO(E log E) / O(E log V)
拓扑排序Kahn / DFSO(V + E)
连通分量DFS / Union-FindO(V + E)
强连通分量Kosaraju / TarjanO(V + E)

参考文章

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「计算机基础」更多文章

  1. 16. 数据链路层
  2. 15. 网络层与路由
  3. 14. 网络模型与协议