图论基础

图论在省赛中属于中高难度考点，但题型固定、模板明确。只要掌握好存图方式、最短路算法和最小生成树，就能应对大部分图论题目。

• 图的存储方式（邻接矩阵、邻接表）
• 拓扑排序（有向无环图）
• 最短路算法（Floyd、Dijkstra、Bellman-Ford/SPFA）
• 最小生成树（Kruskal、Prim）
• 并查集（辅助Kruskal及连通性判断）

图的存储方式

1. 邻接矩阵

适用于点数 ≤ 500，稠密图

# 初始化 n x n 矩阵，inf 表示无边
INF = 10**15
adj = [[INF]*n for _ in range(n)]
for i in range(n):
    adj[i][i] = 0

# 添加有向边 u->v 权重 w
adj[u][v] = w

# 添加无向边
adj[u][v] = adj[v][u] = w

优缺点：查询边权 O(1)，但空间 O(n²)，n 较大时不可行。

2. 邻接表

最常用，适合稀疏图

# 列表嵌套 (neighbor, weight)
graph = [[] for _ in range(n)]

# 添加有向边 u->v 权重 w
graph[u].append((v, w))

# 添加无向边
graph[u].append((v, w))
graph[v].append((u, w))

优缺点：空间 O(n+m)，遍历邻居快，是竞赛首选。

拓扑排序

判断有向图是否有环，求执行顺序

适用场景：任务调度、课程表、依赖关系。

算法（Kahn算法，基于入度）：

1. 计算每个点的入度。
2. 将所有入度为0的点加入队列。
3. 取出队首，将其邻居入度减1，若邻居入度变0则入队。
4. 若最后遍历的节点数少于总点数，则存在环。

from collections import deque

deftopological_sort(n, edges):
    graph = [[] for _ in range(n)]
    indeg = [0] * n
for u, v in edges:   # u -> v
        graph[u].append(v)
        indeg[v] += 1

    q = deque([i for i in range(n) if indeg[i] == 0])
    result = []
while q:
        u = q.popleft()
        result.append(u)
for v in graph[u]:
            indeg[v] -= 1
if indeg[v] == 0:
                q.append(v)

if len(result) != n:
returnNone# 存在环
return result

注意：拓扑序可能不唯一，任意输出一种即可。

最短路算法

1. Floyd-Warshall

多源最短路，点数 ≤ 400

deffloyd(dist):
    n = len(dist)
for k in range(n):
for i in range(n):
if dist[i][k] == INF: continue
for j in range(n):
if dist[k][j] == INF: continue
if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
return dist

复杂度 O(n³)，适用于点数小（如 n≤200）的题目。

2. Dijkstra

单源非负权最短路，最常用

• 朴素 O(n²) 适合稠密图且 n ≤ 5000。
• 堆优化 O((n+m) log n) 适合稀疏图，n 可达 

堆优化模板：

import heapq

defdijkstra(start, graph, n):
    INF = 10**18
    dist = [INF] * n
    dist[start] = 0
    pq = [(0, start)]   # (distance, node)
while pq:
        d, u = heapq.heappop(pq)
if d != dist[u]:
continue
for v, w in graph[u]:
            nd = d + w
if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
return dist

注意：图不能有负权边，否则 Dijkstra 失效。

3. Bellman-Ford / SPFA

处理负权边，判断负环

• Bellman-Ford：O(nm)，对每条边松弛 n-1 次，再检查一次是否能继续松弛。
• SPFA：队列优化，平均 O(m)，最坏 O(nm)。

其实可以跳过

最小生成树（MST）

1. Kruskal

贪心 + 并查集，适用于稀疏图

deffind(parent, x):
if parent[x] != x:
        parent[x] = find(parent, parent[x])
return parent[x]

defunion(parent, rank, x, y):
    rx, ry = find(parent, x), find(parent, y)
if rx == ry:
returnFalse
if rank[rx] < rank[ry]:
        parent[rx] = ry
elif rank[rx] > rank[ry]:
        parent[ry] = rx
else:
        parent[ry] = rx
        rank[rx] += 1
returnTrue

defkruskal(n, edges):# edges: (u, v, w)
    edges.sort(key=lambda e: e[2])
    parent = list(range(n))
    rank = [0] * n
    mst_weight = 0
    cnt = 0
for u, v, w in edges:
if union(parent, rank, u, v):
            mst_weight += w
            cnt += 1
if cnt == n-1:
break
return mst_weight if cnt == n-1elseNone

2. Prim

适用于稠密图，O(n²) 或堆优化 O((n+m) log n) 堆优化版与 Dijkstra 类似，区别在于 dist 表示到当前生成树的最小边权。

import heapq

defprim(start, graph, n):
    INF = 10**18
    visited = [False] * n
    min_edge = [INF] * n
    min_edge[start] = 0
    pq = [(0, start)]
    total = 0
    cnt = 0
while pq:
        w, u = heapq.heappop(pq)
if visited[u]:
continue
        visited[u] = True
        total += w
        cnt += 1
for v, c in graph[u]:
ifnot visited[v] and c < min_edge[v]:
                min_edge[v] = c
                heapq.heappush(pq, (c, v))
return total if cnt == n elseNone

选择建议：边数少用 Kruskal（代码简单），边数多用 Prim 堆优化。

并查集（Union-Find）

并查集是图论辅助工具，用于动态连通性和 Kruskal。

模板：

classDSU:
def__init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

deffind(self, x):
while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
return x
# 或者递归路径压缩
# if self.parent[x] != x:
#     self.parent[x] = self.find(self.parent[x])
# return self.parent[x]

defunion(self, x, y):
        rx, ry = self.find(x), self.find(y)
if rx == ry:
returnFalse
if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
else:
            self.parent[ry] = rx
            self.rank[rx] += 1
returnTrue

常见题型

1. 最短路计数

求从起点到终点的最短路径条数。在 Dijkstra 松弛时，如果 nd == dist[v]，则 count[v] += count[u]；如果 nd < dist[v]，则 count[v] = count[u]，并更新 dist。

2. 判断负环

使用 SPFA 记录入队次数，或 Bellman-Ford 第 n 次松弛仍可更新。

3. 最小生成树

例如：连接所有村庄的最小造价

直接 Kruskal 或 Prim。

4. 拓扑排序

例如：判断课程表是否可行

5. 二分图判定（染色法）

可用 DFS 或 BFS 染色，相邻节点不同色。

defis_bipartite(graph):
    color = [-1] * n
for i in range(n):
if color[i] == -1:
            stack = [i]
            color[i] = 0
while stack:
                u = stack.pop()
for v in graph[u]:
if color[v] == -1:
                        color[v] = color[u] ^ 1
                        stack.append(v)
elif color[v] == color[u]:
returnFalse
returnTrue

Dijkstra 模板题

题目：给定 n 个点 m 条边的有向图，求起点 s 到终点 t 的最短距离。若不可达输出 -1。

输入：

3 3
1 2 5
2 3 2
1 3 6
1 3

输出：

5

代码：

import sys
import heapq

defsolve():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    graph = [[] for _ in range(n+1)]   # 1-index
for _ in range(m):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        graph[u].append((v, w))
    s = int(next(it)); t = int(next(it))
    INF = 10**18
    dist = [INF] * (n+1)
    dist[s] = 0
    pq = [(0, s)]
while pq:
        d, u = heapq.heappop(pq)
if d != dist[u]:
continue
for v, w in graph[u]:
            nd = d + w
if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    print(dist[t] if dist[t] != INF else-1)

if __name__ == "__main__":
    solve()

坑点

1. INF 设置：设为 10**18 或 float('inf')，但注意 float('inf') 不能用于 heapq 与整数比较？可以，但最好用整数大数。
2. 重边与自环：Dijkstra 可处理重边（取最小），自环若权值为正则无影响，负权自环会导致负环。
3. 图不连通：最短路需判断 dist[t] == INF；MST 需判断边数是否达到 n-1。
4. 堆优化 Dijkstra 的 visited 数组：可以不用，通过 if d != dist[u] 跳过旧条目。
5. Python 递归深度：DFS 遍历图时注意设置 sys.setrecursionlimit。
6. 邻接表存储时，无向图要添加两条边。