图算法全景解析 — 从遍历到最短路径与生成树

图（Graph）是计算机科学中最通用、最强大的数据结构之一。社交网络中的人际关系、互联网中的网页链接、地图中的城市与公路、编译器中的函数调用关系——这些现实世界的问题都可以自然地抽象为图模型。掌握图算法，是从”编程入门”迈向”算法进阶”的关键一步。

本文将系统讲解图的基本概念、两种核心遍历方式（BFS 和 DFS）、三大最短路径算法（Dijkstra、Floyd-Warshall、Bellman-Ford）、两种最小生成树算法（Prim、Kruskal）以及拓扑排序。所有代码均使用 Python 编写并附有详细注释。

图的基本概念

有向图与无向图

无向图（Undirected Graph）：边没有方向，表示双向关系。如社交网络中的”好友关系”。
有向图（Directed Graph / Digraph）：边有方向，表示单向关系。如微博中的”关注关系”。

带权图与无权图

无权图：所有边的权重相同（通常视为 1）。
带权图（Weighted Graph）：每条边附带一个数值（权重），表示距离、费用、时间等。

图的存储方式

邻接矩阵（Adjacency Matrix）：使用二维数组 graph[i][j] 存储节点 i 到节点 j 的边信息。

# 邻接矩阵表示（无向带权图）
INF = float('inf')
graph_matrix = [
    [0,   4,   INF, INF, INF],
    [4,   0,   8,   INF, INF],
    [INF, 8,   0,   7,   INF],
    [INF, INF, 7,   0,   9  ],
    [INF, INF, INF, 9,   0  ]
]

优点：查询任意两点是否相邻为 O(1)
缺点：空间 O(V²)，对稀疏图浪费严重

邻接表（Adjacency List）：每个节点维护一个列表，存储其所有邻居及边权。

# 邻接表表示（无向带权图）
graph_list = {
    0: [(1, 4)],
    1: [(0, 4), (2, 8)],
    2: [(1, 8), (3, 7)],
    3: [(2, 7), (4, 9)],
    4: [(3, 9)]
}

优点：空间 O(V + E)，遍历邻居高效
缺点：查询两点是否相邻需 O(degree) 时间

选择原则： 稀疏图（E 远小于 V²）用邻接表，稠密图（E 接近 V²）用邻接矩阵。实际工程中，邻接表是更常见的选择。

图的遍历

图的遍历是几乎所有图算法的基础，分为两种经典方式：广度优先搜索（BFS）和深度优先搜索（DFS）。

BFS — 广度优先搜索

原理： BFS 从起始节点出发，逐层向外扩展。它先访问所有距离为 1 的节点，再访问距离为 2 的节点，以此类推。BFS 使用**队列（Queue）**来维护待访问节点的顺序。

核心特性： 在无权图中，BFS 找到的路径一定是最短路径。

from collections import deque

def bfs(graph, start):
    """
    广度优先搜索
    :param graph: 邻接表，graph[u] = [(v1, w1), (v2, w2), ...] 或 [v1, v2, ...]
    :param start: 起始节点
    :return: BFS 遍历顺序
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            # 兼容带权和无权邻接表
            v = neighbor[0] if isinstance(neighbor, tuple) else neighbor
            if v not in visited:
                visited.add(v)
                queue.append(v)

    return order

# BFS 求无权图最短路径
def bfs_shortest_path(graph, start, end):
    """
    在无权图中求从 start 到 end 的最短路径
    """
    visited = {start}
    queue = deque([(start, [start])])

    while queue:
        node, path = queue.popleft()
        if node == end:
            return path

        for neighbor in graph[node]:
            v = neighbor[0] if isinstance(neighbor, tuple) else neighbor
            if v not in visited:
                visited.add(v)
                queue.append((v, path + [v]))

    return None  # 不可达

应用场景：

无权图的最短路径
层序遍历（二叉树的层次遍历本质就是 BFS）
连通分量检测
网络爬虫的广度抓取策略

DFS — 深度优先搜索

原理： DFS 从起始节点出发，沿着一条路径尽可能深入，直到无法继续时回溯到上一个分叉点。DFS 可以使用递归或显式栈实现。

def dfs_recursive(graph, start, visited=None):
    """
    深度优先搜索（递归实现）
    """
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]

    for neighbor in graph[start]:
        v = neighbor[0] if isinstance(neighbor, tuple) else neighbor
        if v not in visited:
            order.extend(dfs_recursive(graph, v, visited))

    return order

def dfs_iterative(graph, start):
    """
    深度优先搜索（栈实现）
    """
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)

        # 逆序压栈以保证访问顺序与递归一致
        for neighbor in reversed(graph[node]):
            v = neighbor[0] if isinstance(neighbor, tuple) else neighbor
            if v not in visited:
                stack.append(v)

    return order

应用场景：

连通性判断（图是否连通）
环检测
拓扑排序
路径搜索与回溯算法
强连通分量（Tarjan 算法、Kosaraju 算法）

BFS vs DFS 对比

特性	BFS	DFS
数据结构	队列	栈/递归
空间复杂度	O(V)（最坏情况存储一整层）	O(V)（最坏情况递归深度为V）
最短路径	保证（无权图）	不保证
适合场景	层次遍历、最短路径	连通性、环检测、拓扑排序

最短路径算法

Dijkstra 算法

原理： Dijkstra 算法是解决单源最短路径问题的经典贪心算法。它维护一个已确定最短距离的节点集合，每次从未确定集合中选取距离最小的节点，用该节点更新其邻居的距离估计。

适用条件： 边权必须为非负数。

优先队列优化版本的时间复杂度： O((V + E) log V)

import heapq

def dijkstra(graph, start):
    """
    Dijkstra 单源最短路径算法
    :param graph: 邻接表，graph[u] = [(v, weight), ...]
    :param start: 起始节点
    :return: dist（最短距离字典）, prev（前驱节点字典，用于路径还原）
    """
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}
    # 优先队列：(距离, 节点)
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)

        # 如果取出的距离已过时，跳过
        if d > dist[u]:
            continue

        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))

    return dist, prev

def reconstruct_path(prev, start, end):
    """根据前驱节点字典还原路径"""
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = prev[current]
    path.reverse()
    return path if path[0] == start else []

# 使用示例
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
    'D': [('B', 5), ('C', 8), ('E', 2)],
    'E': [('C', 10), ('D', 2)]
}

dist, prev = dijkstra(graph, 'A')
print(f"A 到各点最短距离: {dist}")
print(f"A 到 E 的最短路径: {reconstruct_path(prev, 'A', 'E')}")

Floyd-Warshall 算法

原理： Floyd-Warshall 算法求解全源最短路径，即所有节点对之间的最短距离。核心思想是动态规划：依次考虑每个节点 k 作为中转点，看是否能缩短 i 到 j 的距离。

时间复杂度： O(V³)

适用场景： 图规模较小（V ≤ 几百）、需要全部节点对的最短路径、可处理负权边（但不能有负权环）。

def floyd_warshall(graph_matrix):
    """
    Floyd-Warshall 全源最短路径
    :param graph_matrix: V×V 的邻接矩阵，graph_matrix[i][j] 为边权，无边为 INF
    :return: dist 矩阵
    """
    V = len(graph_matrix)
    # 复制矩阵避免修改原数据
    dist = [row[:] for row in graph_matrix]

    # 核心三重循环：k 为中转点
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 使用示例
INF = float('inf')
matrix = [
    [0,   3,   INF, 7  ],
    [8,   0,   2,   INF],
    [5,   INF, 0,   1  ],
    [2,   INF, INF, 0  ]
]
result = floyd_warshall(matrix)
for row in result:
    print(row)

Bellman-Ford 算法

原理： Bellman-Ford 算法也是单源最短路径算法，但它能处理负权边。算法对所有边进行 V-1 轮松弛操作，每轮检查每条边是否能缩短距离。如果第 V 轮仍然能松弛，则说明图中存在负权环。

时间复杂度： O(VE)

def bellman_ford(vertices, edges, start):
    """
    Bellman-Ford 单源最短路径（可处理负权边）
    :param vertices: 节点列表
    :param edges: 边列表，[(u, v, weight), ...]
    :param start: 起始节点
    :return: dist 字典，若存在负权环返回 None
    """
    dist = {v: float('inf') for v in vertices}
    dist[start] = 0

    # V-1 轮松弛
    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 第 V 轮检测负权环
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            print("图中存在负权环！")
            return None

    return dist

# 使用示例
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
    ('A', 'B', -1), ('A', 'C', 4),
    ('B', 'C', 3),  ('B', 'D', 2), ('B', 'E', 2),
    ('D', 'B', 1),  ('D', 'C', 5), ('E', 'D', -3)
]
print(bellman_ford(vertices, edges, 'A'))

最短路径算法对比

算法	类型	时间复杂度	能否处理负权	适用场景
Dijkstra	单源	O((V+E) log V)	不能	非负权图、稀疏图
Floyd-Warshall	全源	O(V³)	能（无负环）	小规模图、全对最短路
Bellman-Ford	单源	O(VE)	能（可检测负环）	负权边、汇率套利检测

最小生成树

最小生成树（Minimum Spanning Tree，MST）是一棵包含图中所有顶点的无环连通子图，且所有边的权重之和最小。MST 在网络设计（如最低成本布线）中有重要应用。

Prim 算法

原理： Prim 算法从任意一个顶点出发，每次选择连接已选顶点集合和未选顶点集合之间权重最小的边，将对应的未选顶点加入集合。这是一种贪心策略。

时间复杂度： O((V + E) log V)（使用优先队列）

import heapq

def prim(graph, start):
    """
    Prim 最小生成树算法
    :param graph: 邻接表，graph[u] = [(v, weight), ...]
    :param start: 起始节点
    :return: MST 的边列表和总权重
    """
    mst_edges = []
    total_weight = 0
    visited = set()
    # 优先队列：(权重, 当前节点, 来源节点)
    pq = [(0, start, None)]

    while pq and len(visited) < len(graph):
        weight, u, from_node = heapq.heappop(pq)

        if u in visited:
            continue

        visited.add(u)
        total_weight += weight
        if from_node is not None:
            mst_edges.append((from_node, u, weight))

        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(pq, (w, v, u))

    return mst_edges, total_weight

Kruskal 算法

原理： Kruskal 算法将所有边按权重从小到大排序，依次考虑每条边——如果加入该边不会形成环（通过并查集判断），就将其加入 MST。

时间复杂度： O(E log E)（排序为主要开销）

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(vertices, edges):
    """
    Kruskal 最小生成树算法
    :param vertices: 节点列表
    :param edges: 边列表 [(u, v, weight), ...]
    :return: MST 的边列表和总权重
    """
    # 将节点映射为整数索引
    v_map = {v: i for i, v in enumerate(vertices)}
    uf = UnionFind(len(vertices))

    # 按权重排序
    sorted_edges = sorted(edges, key=lambda e: e[2])

    mst_edges = []
    total_weight = 0

    for u, v, w in sorted_edges:
        if uf.union(v_map[u], v_map[v]):
            mst_edges.append((u, v, w))
            total_weight += w
            if len(mst_edges) == len(vertices) - 1:
                break  # MST 已有 V-1 条边

    return mst_edges, total_weight

# 使用示例
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
    ('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1),
    ('B', 'D', 5), ('C', 'D', 8), ('C', 'E', 10), ('D', 'E', 2)
]
mst, weight = kruskal(vertices, edges)
print(f"最小生成树: {mst}")
print(f"总权重: {weight}")

Prim vs Kruskal 对比

特性	Prim	Kruskal
策略	从顶点出发，贪心扩展	按边排序，贪心选边
数据结构	优先队列	并查集
时间复杂度	O((V+E) log V)	O(E log E)
适合场景	稠密图（边多）	稀疏图（边少）
起始要求	需要指定起始顶点	不需要

拓扑排序

定义： 拓扑排序是对**有向无环图（DAG）**中所有顶点的一种线性排序，使得对于每条有向边 (u, v)，u 在排序中出现在 v 之前。

应用场景： 课程先修关系、任务调度、编译依赖分析、包管理器的安装顺序。

Kahn 算法（BFS 方式）

原理： 维护所有入度为 0 的节点的队列。每次取出一个入度为 0 的节点，将其加入结果，并将其所有邻居的入度减 1。如果某个邻居的入度变为 0，加入队列。

from collections import deque

def topological_sort_kahn(graph, vertices):
    """
    Kahn 算法实现拓扑排序（BFS）
    :param graph: 有向图邻接表，graph[u] = [v1, v2, ...]
    :param vertices: 所有顶点列表
    :return: 拓扑排序结果，若存在环返回 None
    """
    # 计算所有节点的入度
    in_degree = {v: 0 for v in vertices}
    for u in graph:
        for v in graph[u]:
            in_degree[v] = in_degree.get(v, 0) + 1

    # 将所有入度为 0 的节点入队
    queue = deque([v for v in vertices if in_degree[v] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 如果结果长度不等于节点数，说明存在环
    if len(result) != len(vertices):
        print("图中存在环，无法拓扑排序！")
        return None

    return result

# 使用示例：课程选修顺序
course_graph = {
    '高等数学': ['线性代数', '概率论'],
    '线性代数': ['机器学习'],
    '概率论': ['机器学习', '统计学'],
    '编程基础': ['数据结构'],
    '数据结构': ['算法设计', '机器学习'],
    '算法设计': [],
    '机器学习': [],
    '统计学': []
}
vertices = list(course_graph.keys())
print(topological_sort_kahn(course_graph, vertices))

时间复杂度： O(V + E)

各算法时间复杂度汇总

算法	时间复杂度	空间复杂度	用途
BFS	O(V + E)	O(V)	遍历、无权最短路径
DFS	O(V + E)	O(V)	遍历、连通性、环检测
Dijkstra	O((V+E) log V)	O(V)	单源最短路径（非负权）
Floyd-Warshall	O(V³)	O(V²)	全源最短路径
Bellman-Ford	O(VE)	O(V)	单源最短路径（负权）
Prim	O((V+E) log V)	O(V)	最小生成树（稠密图）
Kruskal	O(E log E)	O(V)	最小生成树（稀疏图）
Kahn 拓扑排序	O(V + E)	O(V)	DAG 线性排序

总结：不同场景下的算法选择

图算法的选择取决于问题的具体需求：

求最短路径：

非负权图、单源 → Dijkstra
含负权边、单源 → Bellman-Ford
全部节点对之间、小规模 → Floyd-Warshall
无权图 → 直接 BFS

求最小生成树：

稠密图 → Prim
稀疏图 → Kruskal

求拓扑顺序：

DAG → Kahn 算法（BFS）或 DFS 后序反转

检测环：

无向图 → DFS 或并查集
有向图 → DFS（检测回边）或 Kahn 算法（拓扑排序失败说明有环）

检测连通性：

无向图 → BFS/DFS 或并查集
有向图强连通分量 → Tarjan 算法或 Kosaraju 算法

图算法是算法学习中内容最丰富、应用最广泛的领域之一。扎实掌握本文介绍的这些基础算法，将为你理解更高级的图论问题（如网络流、二分匹配、最小费用流等）奠定坚实的基础。建议在学习过程中多动手画图、手动模拟算法执行过程，这比单纯看代码更有助于深入理解。