蓝桥杯python备赛笔记之（九）图论

无权图：用graph = [[] for _ in range(n+1)]，graph[u]存储与 u 直接相连的所有顶点 v；
带权图：用graph = [[] for _ in range(n+1)]，graph[u]存储元组(v, w)，其中 w 为 u→v 的边权重。

实现代码

# 1. 无向无权图：n个顶点，m条边
n, m = 5, 6
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)  # 无向图需双向添加

# 2. 有向带权图：n个顶点，m条边
n, m = 5, 6
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))  # 有向图仅单向添加

3. 图的遍历（基础中的基础）

图的遍历是所有图论算法的基础，蓝桥杯必考深度优先搜索（DFS）和广度优先搜索（BFS），需熟练掌握递归 / 非递归版 DFS、队列版 BFS，以及访问标记（避免重复遍历）。

核心前提

定义访问数组visited = [False] * (n+1)，visited[u] = True表示顶点 u 已遍历，初始化全为False。

（1）深度优先搜索（DFS）：递归 + 非递归版

核心思想：从起点出发，沿着一条路径走到头，再回溯走其他路径（先深后广），适合连通性判断、找路径、拓扑排序（递归）。

递归版：代码简洁，蓝桥杯首选（注意 Python 递归深度限制，n≤1000 时无问题）；
非递归版：用栈模拟递归，避免深度超限，适合大数据量。

代码模板（无向无权图，起点为 1）

# 递归版DFS（推荐，简洁）
n = 5
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

def dfs(u):
    visited[u] = True  # 标记已访问
    print(u, end=' ')  # 遍历操作，可根据题意修改
    for v in graph[u]:
        if not visited[v]:
            dfs(v)  # 递归遍历未访问的邻接顶点

dfs(1)  # 从顶点1开始遍历

# 非递归版DFS（栈实现）
def dfs_stack(start):
    stack = [start]
    visited[start] = True
    while stack:
        u = stack.pop()  # 栈：后进先出
        print(u, end=' ')
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                stack.append(v)

dfs_stack(1)

（2）广度优先搜索（BFS）：队列版

核心思想：从起点出发，先遍历所有邻接顶点，再依次遍历邻接顶点的邻接顶点（先广后深），适合求无权图的最短路径、层序遍历、找最短步数。

必用队列（Python 中用deque，popleft () 时间复杂度 O (1)，远快于列表 pop (0)）；
天然适合最短路径：无权图中，BFS 第一次到达目标顶点的路径即为最短路径（步数最少）。

代码模板（无向无权图，起点为 1，求到各点的最短距离）

from collections import deque

n = 5
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
dist = [-1] * (n+1)  # 存储最短距离，-1表示未到达

def bfs(start):
    q = deque()
    q.append(start)
    visited[start] = True
    dist[start] = 0  # 起点到自身距离为0
    while q:
        u = q.popleft()  # 队列：先进先出
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                dist[v] = dist[u] + 1  # 层数+1，即最短距离
                q.append(v)
    return dist

dist = bfs(1)
print(dist)  # 输出：[-1, 0, 1, 1, 2, 2]（索引0无意义）

（3）遍历的高频应用

判断图的连通性：遍历后统计visited中True的数量，等于 n 则为连通图；
统计连通分量数：循环遍历所有顶点，未访问则启动 DFS/BFS，计数 + 1；
无权图最短路径：BFS 的 dist 数组直接为最短距离；
找起点到终点的路径：DFS/BFS 中记录前驱节点，从终点回溯到起点即可。

二、蓝桥杯必考图论算法（模板化，直接套用）

蓝桥杯图论题的核心是经典算法的模板化应用，无需理解底层原理，只需根据题目特征选择算法、修改模板参数即可，以下是必考 4 大算法，覆盖 90% 的图论考题，需背熟模板。

算法 1：单源最短路径 ——Dijkstra 算法（带权图，非负权边）

适用场景

求有向 / 无向带权图中，一个起点到所有其他顶点的最短路径，边权重必须非负（蓝桥杯必考场景，如道路距离、成本计算），是图论的核心考点。

核心思想

贪心 + 堆：用小根堆维护未访问顶点的当前最短距离，每次选距离最小的顶点，更新其邻接顶点的距离，时间复杂度O(mlogn)（适配 Python 大数据量）。

蓝桥杯专用模板（邻接表 + 堆，Python 版）

from collections import deque
import heapq

def dijkstra(n, graph, start):
    """
    n：顶点数（1~n）
    graph：带权邻接表，graph[u] = [(v, w)]
    start：起点
    return：start到所有顶点的最短距离数组dist
    """
    INF = float('inf')
    dist = [INF] * (n + 1)  # 初始化距离为无穷大
    dist[start] = 0  # 起点到自身距离为0
    heap = []
    heapq.heappush(heap, (0, start))  # 堆存储(当前距离, 顶点)，小根堆按距离排序
    
    while heap:
        cur_dist, u = heapq.heappop(heap)
        # 剪枝：当前距离大于已记录的最短距离，直接跳过
        if cur_dist > dist[u]:
            continue
        # 遍历u的所有邻接顶点
        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

# 使用示例
n, m = 4, 4  # 4个顶点，4条边
graph = [[] for _ in range(n+1)]
# 添加边：1→2(1), 1→3(4), 2→3(2), 3→4(1)
edges = [(1,2,1), (1,3,4), (2,3,2), (3,4,1)]
for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))  # 无向带权图，双向添加
dist = dijkstra(n, graph, 1)
print(dist)  # 输出：[inf, 0, 1, 3, 4]

高频技巧

求起点到终点的最短距离：直接取dist[end]；
带路径记录：新增pre数组，pre[v] = u表示 v 的前驱是 u，更新距离时记录pre[v] = u，最后从终点回溯到起点即可；
堆的优化：Python 的heapq是小根堆，直接使用即可，无需额外处理。

算法 2：单源最短路径 ——SPFA 算法（带权图，含负权边，无负环）

适用场景

求有向 / 无向带权图中含负权边（边权重为负数）但无负环的单源最短路径，蓝桥杯偶考（若题目出现负权边，直接用 SPFA，替代 Dijkstra）。

核心思想

BFS + 松弛操作：用队列维护待松弛的顶点，每次取出顶点更新邻接顶点的距离，若邻接顶点未在队列中则入队，时间复杂度O(m)，最坏O(nm)。

模板代码

from collections import deque

def spfa(n, graph, start):
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[start] = 0
    in_queue = [False] * (n + 1)  # 标记顶点是否在队列中，避免重复入队
    q = deque()
    q.append(start)
    in_queue[start] = True
    
    while q:
        u = q.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True
    return dist

# 使用示例（含负权边）
n, m = 3, 3
graph = [[] for _ in range(n+1)]
edges = [(1,2,2), (2,3,-1), (1,3,5)]
for u, v, w in edges:
    graph[u].append((v, w))
dist = spfa(n, graph, 1)
print(dist)  # 输出：[inf, 0, 2, 1]

算法 3：最小生成树（MST）——Kruskal 算法（并查集 + 贪心）

适用场景

求无向带权连通图的最小生成树（连接所有顶点，边权和最小，无环），蓝桥杯必考，常与并查集结合（核心用并查集判断边是否成环）。

核心思想

贪心 + 并查集：

将所有边按权重升序排序；
依次遍历边，用并查集判断边的两个顶点是否在同一集合；
若不在，则合并集合并累加边权（加入生成树）；
直到生成树有 n-1 条边（n 为顶点数）。

蓝桥杯专用模板（并查集 + 边排序）

# 第一步：实现并查集（直接复用之前的模板）
class DSU:
    def __init__(self, n):
        self.fa = [i for i in range(n+1)]
        self.rank = [1] * (n+1)
    def find(self, x):
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    def union(self, u, v):
        u_root = self.find(u)
        v_root = self.find(v)
        if u_root == v_root:
            return False
        if self.rank[u_root] < self.rank[v_root]:
            self.fa[u_root] = v_root
        else:
            self.fa[v_root] = u_root
            if self.rank[u_root] == self.rank[v_root]:
                self.rank[u_root] += 1
        return True

# 第二步：Kruskal算法
def kruskal(n, edges):
    """
    n：顶点数（1~n）
    edges：边列表，每个元素为(u, v, w)，w为边权
    return：最小生成树的边权和，若无法生成（非连通图）返回-1
    """
    dsu = DSU(n)
    edges.sort(key=lambda x: x[2])  # 边按权重升序排序
    res = 0  # 存储最小边权和
    cnt = 0  # 记录生成树的边数
    for u, v, w in edges:
        if dsu.union(u, v):
            res += w
            cnt += 1
            if cnt == n - 1:  # 生成树需n-1条边，提前退出
                break
    return res if cnt == n-1 else -1

# 使用示例
n, m = 4, 5
edges = [(1,2,1), (1,3,4), (2,3,2), (2,4,5), (3,4,1)]
min_sum = kruskal(n, edges)
print(min_sum)  # 输出：4（1-2(1)+2-3(2)+3-4(1)）

算法 4：最小生成树（MST）——Prim 算法（堆 + 贪心）

适用场景

求无向带权稠密图（边数多）的最小生成树，蓝桥杯考频低于 Kruskal，但若题目顶点少、边数多，用 Prim 更高效。

核心思想

贪心 + 堆：从一个起点出发，逐步将距离生成树最近的顶点加入生成树，更新邻接顶点到生成树的距离，时间复杂度O(mlogn)。

模板代码

import heapq

def prim(n, graph, start=1):
    """
    n：顶点数（1~n）
    graph：带权邻接表，graph[u] = [(v, w)]
    start：起始顶点，默认1
    return：最小生成树的边权和
    """
    INF = float('inf')
    dist = [INF] * (n + 1)  # dist[v]表示v到生成树的最短距离
    visited = [False] * (n + 1)
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    res = 0
    cnt = 0
    
    while heap:
        cur_w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        res += cur_w
        cnt += 1
        if cnt == n:
            break
        # 更新邻接顶点到生成树的距离
        for v, w in graph[u]:
            if not visited[v] and w < dist[v]:
                dist[v] = w
                heapq.heappush(heap, (w, v))
    return res if cnt == n else -1

# 使用示例
n, m = 4, 5
graph = [[] for _ in range(n+1)]
edges = [(1,2,1), (1,3,4), (2,3,2), (2,4,5), (3,4,1)]
for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))
min_sum = prim(n, graph)
print(min_sum)  # 输出：4

三、蓝桥杯偶考图论算法（按需掌握）

以下算法蓝桥杯考频较低，多出现于国赛或省赛难题，只需了解适用场景和核心思路，掌握基础模板即可。

1. 多源最短路径 ——Floyd-Warshall 算法

适用场景

求任意两个顶点之间的最短路径，支持负权边（无负环），顶点数 n≤500（空间复杂度 O (n²)，Python 适配小数据量）。

核心思想

动态规划：dp[k][i][j]表示经过前 k 个顶点，i 到 j 的最短路径，优化为二维数组dp[i][j]，三重循环实现，代码极简。

模板代码

def floyd(n, graph):
    """
    n：顶点数（1~n）
    graph：邻接矩阵，graph[i][j]为i→j的边权，INF表示无直接边
    return：任意两点的最短距离矩阵
    """
    INF = float('inf')
    # 初始化距离矩阵
    dist = [[INF]*(n+1) for _ in range(n+1)]
    for i in range(n+1):
        dist[i][i] = 0
    # 赋值邻接矩阵
    for i in range(n+1):
        for j in range(n+1):
            if graph[i][j] != INF:
                dist[i][j] = graph[i][j]
    # 三重循环更新
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

# 使用示例
n = 4
INF = float('inf')
graph = [[INF]*(n+1) for _ in range(n+1)]
edges = [(1,2,1), (1,3,4), (2,3,2), (3,4,1)]
for u, v, w in edges:
    graph[u][v] = w
    graph[v][u] = w
dist = floyd(n, graph)
print(dist[1][4])  # 输出：4（1→2→3→4）

2. 拓扑排序 ——Kahn 算法（BFS）

适用场景

求有向无环图（DAG）的拓扑序列，蓝桥杯常考任务调度、课程安排等问题（需满足先后顺序）。

核心思想

入度 + 队列：

计算所有顶点的入度；
将入度为 0 的顶点入队；
依次出队，遍历其邻接顶点，入度 - 1，若入度为 0 则入队；
最终若拓扑序列长度等于顶点数，则无环，否则有环。

模板代码

from collections import deque

def topological_sort(n, graph):
    """
    n：顶点数（1~n）
    graph：有向无权邻接表
    return：拓扑序列，若有环返回[]
    """
    in_degree = [0] * (n + 1)  # 计算入度
    for u in range(1, n+1):
        for v in graph[u]:
            in_degree[v] += 1
    q = deque()
    # 入度为0的顶点入队
    for u in range(1, n+1):
        if in_degree[u] == 0:
            q.append(u)
    res = []
    while q:
        u = q.popleft()
        res.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    return res if len(res) == n else []

# 使用示例
n, m = 4, 3
graph = [[] for _ in range(n+1)]
edges = [(1,2), (2,3), (1,4)]  # 1→2, 2→3, 1→4
for u, v in edges:
    graph[u].append(v)
topo = topological_sort(n, graph)
print(topo)  # 输出：[1,2,4,3] 或 [1,4,2,3]（拓扑序列不唯一）

四、蓝桥杯图论实战技巧与避坑指南

1. 算法选择秘籍（根据题目特征直接选）

蓝桥杯图论题的关键是快速匹配算法，无需纠结，按以下规则选择：

表格

题目特征	首选算法
无权图最短路径 / 最短步数	BFS
带权图非负权，单源最短路径	Dijkstra（堆版）
带权图含负权边，单源最短路径	SPFA
任意两点最短路径，n 小	Floyd-Warshall
无向带权图，最小生成树，边数少	Kruskal（并查集）
无向带权图，最小生成树，稠密图	Prim（堆版）
有向无环图，任务调度 / 先后顺序	拓扑排序（Kahn）
连通性判断 / 连通分量统计	DFS/BFS/ 并查集

2. 高频避坑点（蓝桥杯丢分重灾区）

（1）顶点编号问题

蓝桥杯题目中顶点常从 1 开始，Python 列表索引从 0 开始，初始化数组（graph/visited/dist）时需多开一个位置（如 n 个顶点，数组长度为 n+1），索引 0 弃用；
若题目顶点从 0 开始，直接按 0~n-1 初始化即可。

（2）无向图 / 有向图的边添加错误

无向图：边 u-v 需双向添加graph[u].append(v)和graph[v].append(u)（带权图同理），漏加会导致遍历不完整；
有向图：仅需添加graph[u].append(v)，多加速度会导致逻辑错误。

（3）Dijkstra 算法的堆剪枝

堆中可能存在同一顶点的多个距离记录，必须判断cur_dist > dist[u]，否则会重复更新，导致时间超限；
示例：堆中存在 (5,2) 和 (3,2)，当弹出 (5,2) 时，dist [2] 已更新为 3，直接跳过。

（4）Python 的队列选择

BFS/SPFA/ 拓扑排序中，必须用collections.deque，其popleft()是 O (1)；
若用列表pop(0)，时间复杂度 O (n)，大数据量会直接超时（蓝桥杯高频丢分点）。

（5）并查集的路径压缩 + 按秩合并

Kruskal 算法中，并查集必须带路径压缩和按秩合并，否则会超时（尤其是大数据量）；
直接复用之前的并查集类，无需修改。

（6）无穷大的赋值

定义无穷大时，避免用过大的数字（如 1e18），建议用float('inf')，防止边权累加时溢出；
注意：Python 中inf + 数字仍为inf，不影响判断。

3. Python 性能优化技巧（应对时间限制）

蓝桥杯 Python 的时间限制通常为 1s，图论题若数据量较大（n≥1e4，m≥1e5），需做以下优化：

输入优化：用sys.stdin.readline替代input，大数据量输入时速度提升 10 倍以上；
```
import sys
input = sys.stdin.readline
```
减少循环内的计算：提前计算len(graph)、将全局变量改为局部变量（Python 局部变量访问更快）；
堆的优化：Dijkstra/Prim 中，堆仅存储 (距离 / 权重，顶点)，无需额外信息，减少堆操作时间；
剪枝：Dijkstra 中跳过cur_dist > dist[u]，Kruskal 中边数达到 n-1 时提前退出。