w wyl123ly 的博客
MD

数据结构-图

48 KB 2026.10.11 原文件

数据结构-图

一句话概括

图(Graph) 是由「顶点集合」和「边集合」组成的数学模型,用来描述任意两个对象之间都可能存在关系的场景:社交网络的好友关系、地图上的道路、课程之间的先修依赖、网页之间的超链接。

本篇覆盖:图的两种存储方式、BFS/DFS 两大遍历框架、连通性、环检测、拓扑排序(Topological Sort)、最短路径(BFS / Dijkstra / Floyd)、最小生成树(Minimum Spanning Tree, MST)、二分图染色、强连通分量(Strongly Connected Component, SCC)、欧拉回路与哈密顿路径。

所有算法都给出可直接运行的 Python 实现,并逐步说明状态如何变化。

是什么

图的数学定义

一个图写作 :

  • 是顶点(Vertex / Node)的集合, 记作
  • 是边(Edge)的集合, 记作
  • 每条边连接一对顶点,写成

图与树的根本区别:树是"无环连通图"这一特例(且 ),而图允许环、允许不连通、允许任意多的边(最多约 条)。

术语表

术语含义例子
有向图(Directed Graph)边有方向, 表示 ,与 不同微博关注、课程先修
无向图(Undirected Graph)边无方向, 等价于 微信好友、无向道路
加权图(Weighted Graph)每条边带权值(距离、代价、时间)地图导航
度(Degree)无向图中与顶点相连的边数;有向图分「入度 in-degree」与「出度 out-degree」好友数量、粉丝数
路径(Path)顶点序列 ,相邻两点间都有边换乘路线
简单路径顶点不重复的路径—
环(Cycle)起点等于终点的路径循环依赖
自环(Self-loop) 的边自己关注自己
重边(Multi-edge)两顶点间多条边两条不同的路
连通(Connected)无向图中两顶点间存在路径—
连通分量(Connected Component)无向图的极大连通子图社交网络中的孤立圈子
强连通(Strongly Connected)有向图中 能到 且 能到 —
强连通分量(SCC)有向图的极大强连通子图循环依赖的一组模块
稠密图 / 稀疏图 接近 / 接近 完全图 / 稀疏路网
二分图(Bipartite Graph)顶点可分成两个集合,所有边的两端分属不同集合男女配对、课程-教室

握手引理

无向图中所有顶点的度数之和等于边数的两倍:。

推论:度数为奇数的顶点一定是偶数个(这条常出现在图论证明题里)。

有向图中,入度之和 = 出度之和 = 。

为什么需要它

很多现实问题用「线性结构」表达不出来:

现实问题图的建模方式用到的算法
从 A 到 B 的最快路线路口 = 顶点,道路 = 加权边Dijkstra
修路让所有城市连通且总造价最低城市 = 顶点,造价 = 权Kruskal / Prim
课程安排是否可行课程 = 顶点,先修 = 有向边拓扑排序 + 环检测
两人是否属于同一个社交圈人 = 顶点,好友 = 无向边并查集 / BFS
任务能否拆成两组互不冲突冲突 = 边二分图染色
编译器的循环依赖检测模块 = 顶点,依赖 = 有向边Tarjan SCC

关键动机:图算法把「无法枚举的指数级搜索空间」压缩成「对每个顶点和每条边只访问常数次」,从而把 的问题降到 或 。

核心内容

一、两种表示法

邻接矩阵(Adjacency Matrix)

用 的二维数组 g[u][v] 存放边:

  • 无权图:g[u][v] = 1 表示有边,0 表示无边
  • 加权图:g[u][v] = w 表示边权,无边用 INF(正无穷)
邻接表(Adjacency List)

每个顶点维护一个列表,存放它的所有邻居:

  • g[u] = [(v, w), ...],加权图存 (邻居, 权重) 二元组
同一张图的两种存储示例

取图:顶点 ,无向边 ,其中 权重为 7。

        0
       / \
      1---2 --7-- 3

邻接矩阵(INF 表示无边,对角线为 0):

     0    1    2    3
0 [  0,   1,   1,  INF ]
1 [  1,   0,   1,  INF ]
2 [  1,   1,   0,   7  ]
3 [ INF, INF,  7,   0  ]

邻接表:

0 -> [(1,1), (2,1)]
1 -> [(0,1), (2,1)]
2 -> [(0,1), (1,1), (3,7)]
3 -> [(2,7)]
对比表
维度邻接矩阵邻接表
空间复杂度
判断 是否有边,最坏
遍历某顶点的所有邻居
遍历整张图(BFS/DFS)
加边
删边
适合的图稠密图()、需要频繁查边稀疏图(),绝大多数真实场景
额外好处矩阵乘法可求路径条数、可做 Floyd省内存,能存重边

怎么选

先看 : 且需要 Floyd 或频繁询问两点是否有边 → 邻接矩阵; → 一律邻接表。

现实的图几乎都是稀疏的(社交网络平均好友数远小于总人数),所以邻接表是默认选择。

"""图的两种表示法:邻接矩阵与邻接表,以及它们之间的转换。"""

INF = float("inf")


class GraphMatrix:
    """邻接矩阵实现,适合稠密图与需要 O(1) 查边的场景。"""

    def __init__(self, n):
        self.n = n
        # 对角线为 0:顶点到自己的距离是 0,这一点在 Floyd 中很关键
        self.g = [[INF] * n for _ in range(n)]
        for i in range(n):
            self.g[i][i] = 0

    def add_edge(self, u, v, w=1, directed=False):
        self.g[u][v] = w
        if not directed:
            self.g[v][u] = w  # 无向图两个方向都要写

    def has_edge(self, u, v):
        return self.g[u][v] != INF

    def neighbors(self, u):
        return [(v, self.g[u][v]) for v in range(self.n) if u != v and self.g[u][v] != INF]


class GraphList:
    """邻接表实现,适合稀疏图,是竞赛与工程中的默认选择。"""

    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]  # g[u] 存 (邻居, 权重)

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

    def neighbors(self, u):
        return self.g[u]

    def degree(self, u):
        return len(self.g[u])


def build_demo():
    """用同一张图构造两种存储,验证结果一致。"""
    edges = [(0, 1, 1), (0, 2, 1), (1, 2, 1), (2, 3, 7)]

    gm = GraphMatrix(4)
    gl = GraphList(4)
    for u, v, w in edges:
        gm.add_edge(u, v, w)
        gl.add_edge(u, v, w)

    print("邻接矩阵 2 的邻居:", sorted(gm.neighbors(2)))   # [(0,1),(1,1),(3,7)]
    print("邻接表   2 的邻居:", sorted(gl.neighbors(2)))   # [(0,1),(1,1),(3,7)]
    assert sorted(gm.neighbors(2)) == sorted(gl.neighbors(2))
    # 握手引理验证:度数和 = 2 * 边数
    assert sum(gl.degree(u) for u in range(4)) == 2 * len(edges)
    print("两种表示一致,握手引理成立")


if __name__ == "__main__":
    build_demo()

二、BFS 与 DFS

两种遍历是所有图算法的骨架。它们都要解决同一个问题:如何不重复地访问到所有可达顶点。区别只在「先访问谁」。

BFS(Breadth-First Search,广度优先搜索)

用队列(Queue):先访问起点,再把起点的所有邻居入队,按「距起点层数」逐层扩散。

  • 关键性质:在无权图中,BFS 首次到达某点的距离就是最短距离
  • 复杂度:,每个顶点入队一次、每条边被检查一次

状态变化示例:从 0 出发,图 0-1, 0-2, 1-2, 2-3

步骤出队队列内容dist
初始—[0][0, ∞, ∞, ∞]
10[1, 2][0, 1, 1, ∞]
21[2](2 已访问,跳过)[0, 1, 1, ∞]
32[3][0, 1, 1, 2]
43[][0, 1, 1, 2]
DFS(Depth-First Search,深度优先搜索)

用栈(Stack)或递归:一路走到底,走不动再回退。

  • 关键性质:能天然给出「进入时间 / 离开时间」,是环检测、拓扑排序、割点桥、SCC 的基础
  • 复杂度:
  • 递归实现简洁但有栈溢出风险, 的链状图应改用显式栈
两者对比
维度BFSDFS
数据结构队列(FIFO)栈 / 递归(LIFO)
时间复杂度
空间复杂度(最坏队列存一整层)(最坏递归深度 )
无权最短路能(首次到达即最短)不能直接给
环检测 / 拓扑排序可以(Kahn)可以(三色 / 逆后序)
割点与桥不常用主力
二分图染色可以可以
典型用途最短步数、层序遍历、多源扩散枚举路径、连通分量、回溯剪枝
"""BFS 与 DFS 的完整实现(邻接表,无向无权图)。

包含:
  1. 单源 BFS 求最短距离与路径
  2. 多源 BFS(求每个点到最近源点的距离)
  3. 递归 DFS 与迭代 DFS
"""
from collections import deque


def build_adj(n, edges, directed=False):
    """把边列表转成邻接表。"""
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
        if not directed:
            g[v].append(u)
    return g


def bfs(g, src):
    """单源 BFS。

    返回 (dist, parent):
      dist[v]   = src 到 v 的最短边数,不可达为 -1
      parent[v] = v 在 BFS 树上的父节点,用于回溯路径
    复杂度 O(V+E):每个顶点最多入队一次,每条边最多被检查两次(无向图)。
    """
    n = len(g)
    dist = [-1] * n
    parent = [-1] * n
    dist[src] = 0
    q = deque([src])           # 队列初始化:只有源点
    while q:
        u = q.popleft()        # 出队:按入队顺序处理,保证按层扩散
        for v in g[u]:
            if dist[v] != -1:
                continue       # 已访问过就跳过,这是 BFS 不重复的关键
            dist[v] = dist[u] + 1
            parent[v] = u
            q.append(v)        # 入队:新发现的顶点排到队尾
    return dist, parent


def restore_path(parent, src, dst):
    """从 parent 数组回溯出 src -> dst 的具体路径。"""
    if parent[dst] == -1 and src != dst:
        return []              # 不可达
    path = []
    cur = dst
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    return path[::-1]


def multi_source_bfs(g, sources):
    """多源 BFS:把所有源点先入队,一次遍历求出每个点到最近源点的距离。

    典型场景:地图上多个便利店,求每个小区到最近便利店的距离(等价于加一个
    虚拟超级源点连向所有源点)。
    """
    dist = [-1] * len(g)
    q = deque()
    for s in sources:
        dist[s] = 0
        q.append(s)            # 所有源点同时入队,层数从 0 开始一起扩散
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist


def dfs_recursive(g, u, visited, order=None, parent=None):
    """递归 DFS:记录首次访问顺序。"""
    visited[u] = True
    if order is not None:
        order.append(u)
    for v in g[u]:
        if not visited[v]:
            if parent is not None:
                parent[v] = u
            dfs_recursive(g, v, visited, order, parent)


def dfs_iterative(g, src):
    """迭代 DFS:用显式栈,避免深图递归爆栈。

    注意:为了与递归版得到相同的访问顺序,这里把邻居逆序压栈,
    因为栈是后进先出,最后压入的会最先被弹出。
    """
    visited = [False] * len(g)
    order = []
    stack = [src]
    while stack:
        u = stack.pop()
        if visited[u]:
            continue           # 可能在压栈后被别的路径访问过,需要二次检查
        visited[u] = True
        order.append(u)
        for v in reversed(g[u]):
            if not visited[v]:
                stack.append(v)
    return order


if __name__ == "__main__":
    edges = [(0, 1), (0, 2), (1, 2), (2, 3), (4, 5)]
    g = build_adj(7, edges)

    dist, parent = bfs(g, 0)
    print("从 0 出发的 dist:", dist)           # [0, 1, 1, 2, -1, -1, -1]
    print("0 -> 3 的路径:", restore_path(parent, 0, 3))   # [0, 2, 3]

    print("多源 BFS(源点 0 和 5):", multi_source_bfs(g, [0, 5]))
    # [0, 1, 1, 2, 1, 0, -1]
    # 注意下标 4:它离源点 5 只有 1 步(边 4-5),而不是离 0 的 3 步
    # 6 号点是孤立点,所有源点都到不了,所以是 -1

    visited = [False] * 7
    order = []
    dfs_recursive(g, 0, visited, order)
    print("递归 DFS 顺序:", order)
    print("迭代 DFS 顺序:", dfs_iterative(g, 0))

三、连通性与割点桥

求无向图的连通分量

对每个未访问顶点做一次 BFS/DFS,计数器就是连通分量个数。复杂度 。

def count_components(n, edges):
    """返回无向图的连通分量个数以及每个点所属的分量编号。"""
    g = build_adj(n, edges)
    comp = [-1] * n
    cid = 0
    for s in range(n):
        if comp[s] != -1:
            continue
        # 从 s 出发 flood fill 整个分量
        stack = [s]
        comp[s] = cid
        while stack:
            u = stack.pop()
            for v in g[u]:
                if comp[v] == -1:
                    comp[v] = cid
                    stack.append(v)
        cid += 1
    return cid, comp
割点与桥
  • 割点(Articulation Point / Cut Vertex):删掉它之后,连通分量数量增加
  • 桥(Bridge / Cut Edge):删掉它之后,连通分量数量增加

它们的意义是网络的薄弱环节:路由器布局中,割点就是单点故障。

判定思路(Tarjan 的 dfn / low 算法):

  1. DFS 一遍,记录每个点的访问时间 dfn[u](第几个被访问)
  2. low[u] = 从 出发,经过至多一条回边能到达的最小 dfn
  3. 对树边 :
  • 若 low[v] > dfn[u],则 是桥
  • 若 low[v] >= dfn[u] 且 不是根,则 是割点
  1. 根节点是割点 它有 个 DFS 子树
def find_bridges_and_cut_vertices(n, edges):
    """Tarjan 求无向图的桥与割点,复杂度 O(V+E)。"""
    g = build_adj(n, edges)
    dfn = [-1] * n
    low = [0] * n
    timer = 0
    bridges = []
    cut = set()

    def dfs(u, parent_edge):
        nonlocal timer
        dfn[u] = low[u] = timer
        timer += 1
        children = 0
        for v in g[u]:
            if dfn[v] == -1:                     # 树边
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > dfn[u]:              # 子树回不到 u 或更早 -> 桥
                    bridges.append((u, v))
                if parent_edge != -1 and low[v] >= dfn[u]:
                    cut.add(u)                   # 非根且有子树回不到祖先 -> 割点
            elif v != parent_edge:               # 回边(跳过指向父节点的边)
                low[u] = min(low[u], dfn[v])
        if parent_edge == -1 and children >= 2:
            cut.add(u)                           # 根:>=2 棵子树才是割点

    for s in range(n):
        if dfn[s] == -1:
            dfs(s, -1)
    return bridges, sorted(cut)


if __name__ == "__main__":
    # 0-1-2-3 是一条链,再加一个环 3-4-5-3
    n = 6
    edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 3)]
    print(find_bridges_and_cut_vertices(n, edges))
    # 桥: [(2,3),(1,2),(0,1)];割点: [1,2,3]

四、环检测

有向图:三色标记法

给每个顶点三种颜色:

颜色含义说明
白色(0)未访问还没进入过
灰色(1)在递归栈中正在访问它的子树
黑色(2)已完成它的所有后继都处理完了

判定规则:DFS 中遇到一个灰色顶点,就说明存在环。 这条边叫回边(back edge),它指向当前递归栈里的祖先,恰好构成一个环。

为什么是灰色而不是黑色

遇到黑色顶点说明那条路已经完全走完,从它出发回不到当前点,不构成环。

只有「还在栈里」的祖先才能和当前点连成一个环。

无向图:并查集(Disjoint Set Union, DSU)

无向图加边时,如果两个端点已经属于同一个集合,这条边就形成了一个环。

class DSU:
    """并查集:路径压缩 + 按秩合并,均摊复杂度 O(alpha(n)) ≈ O(1)。"""

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n          # 连通块数量

    def find(self, x):
        # 路径压缩:把沿途所有节点直接挂到根上,后续查询近乎 O(1)
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # 路径减半
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False        # 已在同一集合,说明这条边成环
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True


def has_cycle_undirected(n, edges):
    """无向图环检测(并查集版)。"""
    dsu = DSU(n)
    for u, v in edges:
        if not dsu.union(u, v):
            return True, (u, v)   # 两端已连通,这条边构成环
    return False, None


def has_cycle_directed(n, edges):
    """有向图环检测(三色标记法)。返回 (是否有环, 环上的一条边)。"""
    g = build_adj(n, edges, directed=True)
    color = [0] * n     # 0 白 1 灰 2 黑

    def dfs(u):
        color[u] = 1                      # 进入:染灰,压入递归栈
        for v in g[u]:
            if color[v] == 1:
                return True, (u, v)       # 撞到灰色:回边,有环
            if color[v] == 0 and dfs(v)[0]:
                return True, (u, v)
        color[u] = 2                      # 离开:染黑,出栈
        return False, None

    for s in range(n):
        if color[s] == 0:
            found, edge = dfs(s)
            if found:
                return True, edge
    return False, None


if __name__ == "__main__":
    print(has_cycle_undirected(4, [(0, 1), (1, 2), (2, 3)]))          # (False, None)
    print(has_cycle_undirected(4, [(0, 1), (1, 2), (2, 0)]))          # (True, (2, 0))
    print(has_cycle_directed(3, [(0, 1), (1, 2), (2, 0)]))            # (True, (2, 0))
    print(has_cycle_directed(3, [(0, 1), (0, 2), (1, 2)]))            # (False, None)

五、拓扑排序

问题:给定有向图,把所有顶点排成一个线性序列,使每条边 中 都排在 前面。

存在条件:图是有向无环图(Directed Acyclic Graph, DAG)。有环就没法排(A 先于 B,B 先于 A 矛盾)。

Kahn 算法(BFS 版)

核心是入度:

  1. 统计所有点的入度,把入度为 0 的点入队
  2. 反复出队一个点 ,加入结果序列;把 的所有邻居入度减 1
  3. 若某邻居入度变成 0,入队
  4. 结束时若结果长度 ,说明有环

状态变化示例:课程依赖 0->2, 1->2, 2->3

步骤入度数组队列结果
初始[0,0,2,1][0,1][]
出队 0[0,0,1,1][1][0]
出队 1[0,0,0,1][2][0,1]
出队 2[0,0,0,0][3][0,1,2]
出队 3[0,0,0,0][][0,1,2,3]
DFS 算法

后序遍历(post-order)的逆序就是拓扑序。直觉:一个点被染黑时,它的所有后继都已染黑,所以它在「完成时间」上最早于后继——倒过来刚好满足「前驱在前」。

"""拓扑排序:Kahn 算法与 DFS 两种实现,附带课程表应用题。"""
from collections import deque


def topo_kahn(n, edges):
    """Kahn 算法。返回 (拓扑序, 是否有环)。

    复杂度 O(V+E):每条边恰好被松弛一次。
    """
    g = build_adj(n, edges, directed=True)
    indeg = [0] * n
    for u, v in edges:
        indeg[v] += 1                  # 统计入度
    q = deque([i for i in range(n) if indeg[i] == 0])   # 入度为 0 的点可以最先做
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1              # 前驱 u 已完成,v 的约束少一个
            if indeg[v] == 0:
                q.append(v)            # v 的所有前驱都完成了,可以做
    return (order, True) if len(order) == n else (order, False)


def topo_dfs(n, edges):
    """DFS 版拓扑排序:后序逆序。顺便用三色法判环。"""
    g = build_adj(n, edges, directed=True)
    color = [0] * n
    order = []
    ok = True

    def dfs(u):
        nonlocal ok
        color[u] = 1
        for v in g[u]:
            if color[v] == 1:
                ok = False             # 回边 -> 有环,拓扑序无意义
                return
            if color[v] == 0:
                dfs(v)
        color[u] = 2
        order.append(u)                # 后序:所有后继都已完成

    for s in range(n):
        if color[s] == 0:
            dfs(s)
    order.reverse()                    # 后序的逆序即拓扑序
    return order, ok


def can_finish(num_courses, prerequisites):
    """LeetCode 207 课程表:判断能否修完所有课程。

    prerequisites[i] = [a, b] 表示修 a 之前必须先修 b,即边 b -> a。
    """
    edges = [(b, a) for a, b in prerequisites]
    _, ok = topo_kahn(num_courses, edges)
    return ok


def find_order(num_courses, prerequisites):
    """LeetCode 210 课程表 II:返回一种可行的修课顺序,不可能则返回 []。"""
    edges = [(b, a) for a, b in prerequisites]
    order, ok = topo_kahn(num_courses, edges)
    return order if ok else []


if __name__ == "__main__":
    print(topo_kahn(4, [(0, 2), (1, 2), (2, 3)]))
    # ([0, 1, 2, 3], True)
    print(topo_dfs(4, [(0, 2), (1, 2), (2, 3)]))
    # ([1, 0, 2, 3], True)
    # 与 Kahn 的 [0, 1, 2, 3] 不同但同样合法:0 和 1 之间没有约束,谁先都行

    print(can_finish(2, [[1, 0]]))          # True
    print(can_finish(2, [[1, 0], [0, 1]]))  # False(互相依赖,成环)
    print(find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  # [0,1,2,3] 或 [0,2,1,3]

拓扑序不唯一

任何时刻有多个入度为 0 的点时,选谁都可以得到合法的拓扑序。

若题目要求「字典序最小」,把队列换成最小堆,复杂度变为 。

六、最短路径

1. BFS:无权图单源最短路

已在遍历一节给出:。只要边权都相等,BFS 就是最优解。

2. Dijkstra:非负权单源最短路

贪心思想:每次从「未确定的点」中取出当前距离最小的点,它的距离就已经是最终答案(因为所有边权非负,绕远路不可能更短)。

  • 朴素版:每轮线性扫描找最小值,,适合稠密图
  • 堆优化版:用优先队列取最小值,,适合稀疏图

状态变化示例:图为 0-(1)-1, 0-(4)-2, 1-(2)-2, 1-(5)-3, 2-(1)-3

步骤确定点dist优先队列(部分)
初始—[0, ∞, ∞, ∞][(0,0)]
10[0,1,4,∞][(1,1),(4,2)]
21[0,1,3,6][(3,2),(6,3)]
32[0,1,3,4][(4,3)]
43[0,1,3,4][]

Dijkstra 不能处理负权边

反例:0-(2)-1, 0-(5)-2, 1-(-4)-2。Dijkstra 会先确定 dist[2]=5,但真实最短路是 。

负权图要用 Bellman-Ford()或 SPFA。

3. Floyd-Warshall:多源最短路

动态规划:设 表示「只允许经过前 个顶点作为中转时, 到 的最短距离」,则

滚动掉第一维后用三重循环原地更新,复杂度 ,空间 。能处理负权边(但不能有负环)。

三种算法对比
算法类型时间复杂度空间负权边负环适用场景
BFS单源,无权不适用不适用边权全为 1、求最少步数
Dijkstra(朴素)单源✗✗稠密图()
Dijkstra(堆优化)单源✗✗稀疏图,最常用
Bellman-Ford单源✓可检测有负权边、需要判负环
Floyd-Warshall多源✓可检测(对角线为负),求所有点对距离
"""最短路径三件套:Dijkstra(朴素 + 堆优化)与 Floyd-Warshall。"""
import heapq

INF = float("inf")


def dijkstra_naive(n, edges, src):
    """朴素 Dijkstra O(V^2),用邻接矩阵。

    适合稠密图:因为没有堆操作的开销,常数比堆优化小。
    """
    g = [[INF] * n for _ in range(n)]
    for i in range(n):
        g[i][i] = 0
    for u, v, w in edges:
        g[u][v] = min(g[u][v], w)      # 有重边时取最小
        g[v][u] = min(g[v][u], w)
    dist = [INF] * n
    used = [False] * n
    dist[src] = 0
    for _ in range(n):
        # 第一步:在未确定的点里找距离最小的
        u, best = -1, INF
        for i in range(n):
            if not used[i] and dist[i] < best:
                u, best = i, dist[i]
        if u == -1:
            break                          # 剩余点都不可达
        used[u] = True                     # 第二步:确定 u 的最短距离
        for v in range(n):                 # 第三步:用 u 松弛所有邻居
            if dist[u] + g[u][v] < dist[v]:
                dist[v] = dist[u] + g[u][v]
    return dist


def dijkstra_heap(n, edges, src, directed=False):
    """堆优化 Dijkstra O((V+E) log V),用邻接表。"""
    g = build_weighted_adj(n, edges, directed)
    dist = [INF] * n
    dist[src] = 0
    pq = [(0, src)]                        # (当前已知最短距离, 顶点)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                       # 惰性删除:这是被更优值取代的旧记录
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))  # 允许同一点多次入堆
    return dist


def build_weighted_adj(n, edges, directed=False):
    g = [[] for _ in range(n)]
    for u, v, w in edges:
        g[u].append((v, w))
        if not directed:
            g[v].append((u, w))
    return g


def floyd(n, edges, directed=False):
    """Floyd-Warshall O(V^3),返回距离矩阵。"""
    d = [[INF] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)
        if not directed:
            d[v][u] = min(d[v][u], w)
    for k in range(n):                     # 中转点必须放最外层!
        for i in range(n):
            if d[i][k] == INF:
                continue                   # 剪枝:i 到不了 k 就不用试了
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d


if __name__ == "__main__":
    edges = [(0, 1, 1), (0, 2, 4), (1, 2, 2), (1, 3, 5), (2, 3, 1)]
    print("朴素 :", dijkstra_naive(4, edges, 0))    # [0, 1, 3, 4]
    print("堆优化:", dijkstra_heap(4, edges, 0))     # [0, 1, 3, 4]
    for row in floyd(4, edges):
        print(["INF" if x == INF else x for x in row])
    # [[0,1,3,4],[1,0,2,3],[3,2,0,1],[4,3,1,0]]

七、最小生成树

问题:在带权连通无向图中选出一棵生成树(含全部 个顶点、恰好 条边),使边权总和最小。

切分定理(Cut Property)

把顶点分成两个非空集合 与 (这个划分叫切分)。横跨切分的边中,权值最小的那条一定属于某棵最小生成树。

这条定理是 Kruskal 和 Prim 正确性的共同基础:Kruskal 每次选的是「让两个连通块合并的最小边」,Prim 每次选的是「已选集合与未选集合之间最小的边」。

Kruskal 算法

按边权从小到大排序,依次尝试加入;用并查集判断是否成环,成环就跳过。复杂度 (瓶颈在排序),适合稀疏图。

Prim 算法

从一个点出发,每次把「连接已选集合与未选集合的最小边」加进来,重复 次。堆优化后复杂度 ,适合稠密图(朴素版 )。

对比
维度KruskalPrim
思想全局贪心选最小边 + 并查集局部贪心扩展点集
时间复杂度(堆优化)/ (朴素)
适合图稀疏图稠密图
是否需要并查集是否
处理不连通图能自然得到「最小生成森林」只能得到起点所在分量的 MST
实现难度简单中等
"""最小生成树:Kruskal 与 Prim。"""
import heapq


def kruskal(n, edges):
    """Kruskal:返回 (总权值, 选中的边列表)。复杂度 O(E log E)。"""
    dsu = DSU(n)
    mst, total = [], 0
    # 按权值排序,之后依次贪心取最小边
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if dsu.union(u, v):       # 不成环才接受这条边
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break             # 已有 n-1 条边,生成树完成
    return (total, mst) if len(mst) == n - 1 else (None, mst)   # None 表示不连通


def prim(n, edges, src=0):
    """Prim(堆优化):返回 (总权值, 选中的边列表)。复杂度 O(E log V)。"""
    g = build_weighted_adj(n, edges)
    used = [False] * n
    pq = [(0, src, -1)]           # (边权, 目标点, 来向点)
    total, mst = 0, []
    while pq:
        w, u, parent = heapq.heappop(pq)
        if used[u]:
            continue              # 惰性删除:这个点已通过更短的边加入
        used[u] = True
        total += w
        if parent != -1:
            mst.append((parent, u, w))
        for v, w2 in g[u]:        # 把 u 的新边全部压入堆,作为候选
            if not used[v]:
                heapq.heappush(pq, (w2, v, u))
    return (total, mst) if len(mst) == n - 1 else (None, mst)


if __name__ == "__main__":
    n = 5
    edges = [
        (0, 1, 2), (0, 3, 6), (1, 2, 3), (1, 3, 8),
        (1, 4, 5), (2, 4, 7), (3, 4, 9),
    ]
    print("Kruskal:", kruskal(n, edges)[0])   # 16
    print("Prim   :", prim(n, edges)[0])      # 16

八、二分图判定与染色

二分图(Bipartite Graph):顶点能分成两个集合 ,使每条边的两端一个在 、一个在 。

判定方法:黑白染色。任选起点染黑,它的邻居染白,依次 BFS/DFS。若发现某条边的两端颜色相同,就不是二分图。

重要等价命题:

二分图 ⟺ 图中不存在奇环

一个图是二分图,当且仅当它不含长度为奇数的环。因为绕奇环走一圈会要求同一个点既黑又白,矛盾。

这就是 LeetCode 785「判断二分图」的解法基础,也是「能否把学生分成两组且组内无冲突」的判定依据。

def is_bipartite(n, edges):
    """黑白染色判定二分图,并返回一个合法染色。复杂度 O(V+E)。"""
    g = build_adj(n, edges)
    color = [-1] * n               # -1 未染色,0 一种颜色,1 另一种
    for s in range(n):             # 图可能不连通,每个分量都要染
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in g[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1     # 邻居染相反颜色
                    q.append(v)
                elif color[v] == color[u]:
                    return False, None           # 相邻同色 -> 有奇环 -> 不是二分图
    return True, color


if __name__ == "__main__":
    # 偶环 0-1-2-3-0 是二分图
    print(is_bipartite(4, [(0, 1), (1, 2), (2, 3), (3, 0)]))   # (True, [0,1,0,1])
    # 三角环 0-1-2-0 不是二分图
    print(is_bipartite(3, [(0, 1), (1, 2), (2, 0)]))           # (False, None)

九、强连通分量(Tarjan 思路)

强连通分量:有向图中极大的、内部任意两点互相可达的顶点集合。把每个 SCC 缩成一个点后,得到的图一定是 DAG(叫缩点图 / condensation)。

Tarjan 算法用一个 DFS 同时求出所有 SCC:

  1. 维护 dfn[u](访问时间)与 low[u](能回溯到的最小 dfn)
  2. 维护一个栈,按 DFS 顺序压入访问过的点
  3. DFS 完 的所有邻居后,若 low[u] == dfn[u],说明 是它所在 SCC 的「根」——栈中从 到栈顶的所有点构成一个 SCC,全部弹出

复杂度 ,只需一次 DFS,比 Kosaraju 算法(两遍 DFS + 反图)更紧凑。

def tarjan_scc(n, edges):
    """Tarjan 求强连通分量,返回每个点所属的 SCC 编号(缩点后的点号)。"""
    g = build_adj(n, edges, directed=True)
    dfn = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    comp = [-1] * n
    timer = 0
    cid = 0

    def dfs(u):
        nonlocal timer, cid
        dfn[u] = low[u] = timer
        timer += 1
        stack.append(u)
        on_stack[u] = True
        for v in g[u]:
            if dfn[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])       # 用子树的 low 更新
            elif on_stack[v]:
                low[u] = min(low[u], dfn[v])       # 后退边:只能连到栈内的点
        if low[u] == dfn[u]:
            # u 是 SCC 的根,弹出栈中 u 之上的所有点
            while True:
                x = stack.pop()
                on_stack[x] = False
                comp[x] = cid
                if x == u:
                    break
            cid += 1

    for s in range(n):
        if dfn[s] == -1:
            dfs(s)
    return comp, cid


if __name__ == "__main__":
    # 0->1->2->0 构成一个 SCC;3 单独;4->5->4 构成另一个
    edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 4)]
    print(tarjan_scc(6, edges))     # ([0,0,0,1,2,2], 3)

十、欧拉回路与哈密顿路径

这是图论里最容易被混淆的一对概念:

概念定义判定复杂度
欧拉路径(Eulerian Path)经过每条边恰好一次的路径无向图:0 或 2 个奇度点;有向图:至多一个点出度比入度大 1,至多一个点入度比出度大 1,多项式时间可解
欧拉回路(Eulerian Circuit)起点终点相同的欧拉路径所有点度数为偶(无向);所有点入度 = 出度(有向),Hierholzer 算法
哈密顿路径(Hamiltonian Path)经过每个顶点恰好一次的路径无已知的简单充要条件NP 完全( 大时无多项式解)

一句话记住区别

欧拉是「边不重复」,哈密顿是「点不重复」。

前者是好问题(多项式可解,本质是 DFS 找环),后者是难问题(NP 完全,只能暴力 + 状压 DP,)。

这个「看起来很像却一个简单一个极难」的对比,正是 P vs NP 问题最直观的入口(详见 算法-复杂度分析)。

欧拉回路常用 Hierholzer 算法:DFS 走到不能走,回溯时把点压入路径,最后逆序即为答案。

def euler_circuit(n, edges):
    """Hierholzer 求无向图的欧拉回路。返回路径顶点序列,不存在返回 None。"""
    g = build_adj(n, edges)
    deg = [len(g[i]) for i in range(n)]
    # 判定:所有顶点度数为偶,且所有有边的点在同一个连通分量里
    for i in range(n):
        if deg[i] % 2 == 1:
            return None
    # 用边的索引做去重,避免重边被误删
    used_edge = set()
    edge_id = {}
    for idx, (u, v) in enumerate(edges):
        edge_id.setdefault((u, v), []).append(idx)
        edge_id.setdefault((v, u), []).append(idx)

    ptr = [0] * n            # 当前弧优化:每条边只被扫描一次
    path = []
    stack = [next((i for i in range(n) if deg[i] > 0), 0)]
    while stack:
        u = stack[-1]
        advanced = False
        while ptr[u] < len(g[u]):
            v = g[u][ptr[u]]
            ptr[u] += 1
            # 找一条还没用过的边
            eid = next((i for i in edge_id[(u, v)] if i not in used_edge), None)
            if eid is None:
                continue
            used_edge.add(eid)
            stack.append(v)
            advanced = True
            break
        if not advanced:
            path.append(stack.pop())     # 回溯时记录,最后逆序
    return path[::-1]


if __name__ == "__main__":
    # 四边形 0-1-2-3-0,每个点度数为 2,存在欧拉回路
    print(euler_circuit(4, [(0, 1), (1, 2), (2, 3), (3, 0)]))   # [0,3,2,1,0] 之类
    # 加分一条悬挂边会让两个点变奇度,不存在欧拉回路
    print(euler_circuit(5, [(0, 1), (1, 2), (2, 3), (3, 0), (0, 4)]))  # None

一笔画问题的两个前提

除了度数条件,还必须检查所有有边的顶点属于同一连通分量。

一个孤立点不影响判定,但两个分离的环各自度数为偶,却无法一笔画完。

怎么用

场景一:迷宫最短路(BFS 网格图)

网格是最常见的隐式图:每个格子是顶点,上下左右相邻是边。

from collections import deque


def shortest_path_grid(grid, start, goal):
    """在 0/1 网格中求最短步数,1 表示障碍。返回步数,不可达返回 -1。"""
    R, C = len(grid), len(grid[0])
    dist = [[-1] * C for _ in range(R)]
    dist[start[0]][start[1]] = 0
    q = deque([start])
    while q:
        r, c = q.popleft()
        if (r, c) == goal:
            return dist[r][c]        # BFS 首次到达即最短
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0 and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return -1


if __name__ == "__main__":
    grid = [
        [0, 0, 0, 0],
        [1, 1, 0, 1],
        [0, 0, 0, 0],
    ]
    print(shortest_path_grid(grid, (0, 0), (2, 3)))   # 5

场景二:判断任务依赖是否可执行

def can_schedule(num_tasks, dependencies):
    """dependencies[i] = (a, b) 表示 a 依赖 b(b 必须先完成)。"""
    edges = [(b, a) for a, b in dependencies]
    _, ok = topo_kahn(num_tasks, edges)
    return ok


def schedule_order(num_tasks, dependencies):
    """给出一个可行的执行顺序。"""
    edges = [(b, a) for a, b in dependencies]
    order, ok = topo_kahn(num_tasks, edges)
    return order if ok else None

注意事项与常见坑

坑 1:Dijkstra 的「惰性删除」漏写

堆优化 Dijkstra 里,同一个点可能被多次入堆(每次距离变短都入堆一次)。出堆时必须加

if d > dist[u]: continue,否则会用到过期的旧距离,结果偏大。

坑 2:Floyd 的中转点循环必须在最外层

写成 for i: for j: for k: 就错了。k 必须在最外层,因为它代表「阶段」,即 DP 的阶段维度。

顺序写错时很多用例仍然能过(尤其是只有 3、4 个点的图),非常隐蔽。

坑 3:无向图 DFS 忘记跳过父节点

在 Tarjan 求割点桥、以及无向图环检测中,必须区分「指向父节点的边」和「真正的回边」。

直接写 elif v != parent 在有重边时会误判,严谨做法是传「父边的编号」而不是父节点。

坑 4:递归 DFS 在深图上栈溢出

一条 个点的链会让 Python 递归超出默认的 1000 层限制。要么改用显式栈,

要么 sys.setrecursionlimit(300000) 并配合增大线程栈(threading.stack_size)。

坑 5:把拓扑排序当成唯一解

拓扑序通常有多个。若题目要求「编号小的优先」,必须用最小堆替换队列,否则得到的顺序不满足要求。

坑 6:稠密图上用堆优化 Dijkstra

堆里会塞进 个元素, 时反而不如朴素的 。选算法前先估算 。

坑 7:混淆「环」与「自环」

自环 本身就是环。Kahn 算法中自环会让该点入度永远为 1,最终结果长度不足 ,能被正确检出;

但无向图并查集判环时,自环会让 find(u) == find(u),同样能检出——不要以为要特判。

坑 8:多源 BFS 只入队一个源

把所有源点同时入队、距离一起从 0 开始,才等价于超级源点。分多次单源 BFS 是 ,会超时。

练习题

题 1(基础)连通分量计数

给定 个点和 条无向边,输出连通分量个数和每个点所属分量编号。

<details>

<summary>参考思路</summary>

对每个未访问点做一次 DFS/BFS,计数器加一。复杂度 。见「连通性」一节的 count_components。

</details>

题 2(基础)判断有向图是否有环

给定有向图,判断是否存在环。

<details>

<summary>参考思路</summary>

两种做法:三色标记 DFS(撞到灰色即有环)或 Kahn 拓扑排序(结果长度不足 即有环)。都是 。

</details>

题 3(中等)课程表(LeetCode 207 / 210)

numCourses = 4,prerequisites = [[1,0],[2,0],[3,1],[3,2]],判断能否修完并给出一个顺序。

分步解答:

第 1 步:把先修关系转成有向边。

[a, b] 表示修 a 前先修 b,即边 。得到边集:

第 2 步:统计入度。

顶点0123
入度0112

第 3 步:入度为 0 的点入队。 队列 = [0],结果 = []。

第 4 步:循环出队。

轮次出队入度变化入队结果
101→0, 2→01, 2[0]
213→1—[0,1]
323→03[0,1,2]
43——[0,1,2,3]

第 5 步:判断。 结果长度 4 = 顶点数 4,无环,可以修完。一个合法顺序是 [0,1,2,3]([0,2,1,3] 同样合法)。

def solve():
    n, prereq = 4, [[1, 0], [2, 0], [3, 1], [3, 2]]
    edges = [(b, a) for a, b in prereq]
    order, ok = topo_kahn(n, edges)
    return order if ok else []

复杂度:时间 ,空间 。

题 4(中等)网络延迟时间(LeetCode 743)

有 个网络节点,times[i] = (u, v, w) 表示 的传播时间为 。求从节点 出发,信号传遍所有节点所需的最短时间;不可达返回 。

<details>

<summary>参考思路</summary>

这是有向图单源最短路(边权非负):跑堆优化 Dijkstra 得 dist,答案 = max(dist);若有 INF 则返回 。复杂度 。

</details>

题 5(进阶)判定二分图并输出分组

给定 个点和冲突边,判断能否分成两组,使组内没有冲突边;能则输出两组的具体成员。

<details>

<summary>参考思路</summary>

BFS 黑白染色。图可能不连通,每个分量都要单独起一个起点。染色完成后,

color == 0 的归一组,color == 1 的归另一组。复杂度 。

</details>

题 6(进阶)用 Kruskal 求最小生成森林

给定不连通的无向带权图,求每个连通分量的最小生成树,输出总权值。

<details>

<summary>参考思路</summary>

Kruskal 天然支持:边按权排序后逐个尝试,并查集合并成功的就计入。不要以「选够 条边」为退出条件,

而是遍历完所有边,最后检查 dsu.count 是否为分量数。

</details>

常见问题 FAQ

Q1:什么情况下该用邻接矩阵而不是邻接表?

三个信号:① 很小()且图很稠密;② 需要频繁查询「 和 之间有没有边 / 边权多少」(矩阵 ,表要 );③ 要用 Floyd 算法(它天然需要矩阵)。

其他情况一律用邻接表。

Q2:BFS 真的能求最短路吗?为什么加权图不行?

BFS 的层数等于「经过的边数」。无权图中每一步代价都是 1,所以边数最少 = 代价最小。

加权图里一条边权 100、另一条路径 3 条边各权 1,BFS 会错误地选前者。这时要用 Dijkstra。

Q3:Dijkstra 和 Prim 长得几乎一样,区别在哪?

两者都用优先队列、都做「取最小 + 松弛」。

Dijkstra 的键是「源点到该点的累计距离」(累加),

Prim 的键是「该点到已选集合的单条边权」(不累加)。

一行之差,解决的是完全不同的两个问题。

Q4:什么时候必须用 Tarjan 而不是简单 DFS?

只要问题涉及「哪些点/边是关键的」「哪些点互相可达」,就轮到 Tarjan:

割点、桥、强连通分量、双连通分量、2-SAT。

它们都依赖 dfn/low 这两个数组携带的结构信息,普通 DFS 拿不到。

Q5:图中顶点编号不是 0 到 n-1 怎么办?

先做离散化(Coordinate Compression):把所有出现过的顶点收集起来排序,用字典映射成 。

例如字符串顶点 {"A":[..], "B":[..]} 映射成 {"A":0, "B":1},再套用上面的所有模板。

相关笔记

  • 算法-图算法:本篇的算法视角补充,含 Bellman-Ford、SPFA、网络流与并查集进阶
  • 数据结构-树与堆:树是图的特例,堆是 Dijkstra 与 Prim 的优先队列基础
  • 算法-复杂度分析:、 这些结论的推导基础,以及 P vs NP(哈密顿路径为何难)
  • 数据结构-哈希表:稀疏图的邻接表常与哈希表结合存放字符串顶点
  • 00-索引:全库笔记导航
  • 学习路线图:按阶段的学习顺序建议

参考来源

  • OI Wiki 图论部分:https://oi-wiki.org/graph/
  • OI Wiki 拓扑排序:https://oi-wiki.org/graph/topo/
  • OI Wiki 最短路:https://oi-wiki.org/graph/shortest-path/
  • OI Wiki 最小生成树:https://oi-wiki.org/graph/mst/
  • OI Wiki 强连通分量:https://oi-wiki.org/graph/scc/
  • VisuAlgo 图数据结构可视化:https://visualgo.net/en/graphds
  • VisuAlgo 单源最短路可视化:https://visualgo.net/en/sssp
  • VisuAlgo 最小生成树可视化:https://visualgo.net/en/mst
  • MIT OCW 6.006 Introduction to Algorithms:https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
  • Python 官方文档 collections.deque:https://docs.python.org/3/library/collections.html#collections.deque
  • Python 官方文档 heapq:https://docs.python.org/3/library/heapq.html