当前位置：首页 > news >正文

【数据结构】图，拓扑排序未完

news 2025/7/14 6:49:03

参考：「数据结构详解·十二」有向无环图 & 拓扑排序-CSDN博客

AB13 【模板】拓扑排序

【模板】拓扑排序_牛客题霸_牛客网

描述

给定一个包含 nn 个点和 mm 条边的有向无环图（DAG, Directed Acyclic Graph），求出该图的拓扑序。若图的拓扑序不唯一，输出任意合法的拓扑序即可。若该图不能拓扑排序（即图中存在环），输出 −1−1。

输入描述

第一行输入两个整数 n,mn,m（1≤n,m≤2⋅1051≤n,m≤2⋅105），表示点的个数和边的条数。
接下来的 mm 行，每行输入两个整数 ui,viui,vi（1≤u,v≤n1≤u,v≤n），表示 uiui 到 vivi 之间有一条有向边。

输出描述

若图存在拓扑序，输出一行 nn 个整数，表示拓扑序。否则输出 −1−1。
注意：输出的最后一个数后面不要带空格。

解决方案

我们可以使用两种常见的算法来解决这个问题：Kahn算法（基于入度和广度优先搜索BFS）或深度优先搜索DFS。以下是基于这两种算法的解决方案。

方法一：Kahn算法

‌初始化‌：
- 计算每个顶点的入度。
- 将所有入度为0的顶点加入一个队列。
‌处理队列‌：
- 当队列不为空时，执行以下操作：
  - 从队列中取出一个顶点，将其加入结果序列。
  - 对于该顶点的每个邻接顶点，将其入度减1。
  - 如果某个邻接顶点的入度变为0，则将其加入队列。
‌检查环‌：
- 如果最终输出的顶点数不等于图中的顶点数，则图中存在环，输出 −1−1。
- 否则，输出结果序列作为拓扑序。

from collections import deque, defaultdictdef topological_sort(n, m, edges):#  定义入度队列in_degree = defaultdict(int)# 定义 链接表  表示边graph = defaultdict(list)# 构建图和入度字典for u, v in edges:graph[u].append(v)in_degree[v] += 1queue = deque([v for v in in_degree if in_degree[v] == 0])result = []while queue:u = queue.popleft()  # 取出队列头部result.append(u)  # 加入结果中for v in graph[u]: # 对 u 指向的其他点 边 减去1  删除这条边 in_degree[v] -= 1if in_degree[v] == 0: # 如果减去的边之后v的queue.append(v)# 检查是否所有顶点都被访问if len(result) == n:return resultelse:return [-1]# 示例输入
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]# 获取拓扑序
topological_order = topological_sort(n, m, edges)# 输出结果
if topological_order[0] == -1:print(-1)
else:print(' '.join(map(str, topological_order)), end='')

queue = deque([v for v in in_degree if in_degree[v] == 0]) 这句代码解释

这句代码是Python中使用collections.deque初始化队列的典型操作，用于拓扑排序的Kahn算法中。具体解析如下：‌功能作用‌
从入度字典in_degree中筛选出入度为0的所有顶点，并用这些顶点初始化一个双端队列（deque），作为拓扑排序的起始处理节点集。‌代码拆解‌in_degree：字典结构，存储每个顶点的当前入度数（如{1:0, 2:1}表示顶点1入度0，顶点2入度1）
[v for v in in_degree if in_degree[v] == 0]：
列表推导式，遍历字典所有键（顶点），筛选出入度值为0的顶点
deque(...)：将筛选结果转换为双端队列，优化队首弹出操作（O(1)时间复杂度）
‌算法意义‌
在拓扑排序中，只有入度为0的顶点才能作为当前可处理的节点（没有前置依赖），该操作确保算法从正确的起点开始处理14。示例：若in_degree = {1:0, 2:1, 3:0}，则生成的队列为deque([1, 3])。

edges = [tuple(map(int, input().split())) for _ in range(m) ] 这句代码解释

这句Python代码是用于从标准输入读取m条边的数据，并将其转换为元组列表的列表推导式。具体解析如下：‌功能分解‌：input().split()：读取一行输入并按空格分割成字符串列表
map(int, ...)：将分割后的字符串转换为整数
tuple(...)：将转换后的整数包装成元组（适用于表示边的两个顶点）
for _ in range(m)：循环执行m次（对应m条边）
‌典型输入场景‌：
当输入为：1 2
3 4
代码会生成：[(1, 2), (3, 4)]
‌在图算法中的应用‌：
该写法常见于图论问题初始化阶段，用于快速获取边的集合。例如拓扑排序、最短路径等算法中，这种简洁的写法能高效处理标准格式的输入数据。

方法二：深度优先搜索DFS

‌递归遍历‌：
- 对每个顶点进行深度优先搜索，标记顶点状态为未访问、访问中或已完成。
- 在访问一个顶点时，递归访问其所有邻接顶点。
‌回溯加入结果序列‌：
- 在回溯过程中（即访问完一个顶点的所有邻接顶点后），将该顶点加入结果序列的逆序位置。
‌检查环‌：
- 如果在DFS过程中发现某个顶点已经被标记为“访问中”，则说明图中存在环，输出 −1−1。
- 否则，将所有顶点按逆序输出作为拓扑序（注意要逆序，因为DFS是后序遍历）。

以下是基于Kahn算法的拓扑排序代码运行过程演示，结合具体案例说明算法执行步骤和中间状态变化：

案例演示

‌输入数据‌（5个顶点，4条边）： 5 为孤立点没有边连接

图结构： 5 为孤立点没有边连接

1 → 2 → 4↘ 3 ↗5

运行过程分解

‌初始化阶段‌
- 构建邻接表：
```
adj = { 1: [2, 3], 2: [4], 3: [4], 4: [] }
```
- 计算入度：
```
in_degree = {1:0, 2:1, 3:1, 4:2, 5:0}
```
- 初始队列：[1, 5]（入度为0的顶点）

‌第一轮处理‌取出顶点1，加入结果序列[1]
删除边1→2和1→3：
顶点2入度减1 → in_degree[2] = 0 → 加入队列[5, 2]
顶点3入度减1 → in_degree[3] = 0 → 加入队列[5, 2, 3]28
‌第二轮处理‌取出顶点5，加入结果序列[1, 5]
顶点5无出边，队列剩余[2, 3]612
‌第三轮处理‌取出顶点2，加入结果序列[1, 5, 2]
删除边2→4：
顶点4入度减1 → in_degree[4] = 1（不加入队列）37
‌第四轮处理‌取出顶点3，加入结果序列[1, 5, 2, 3]
删除边3→4：
顶点4入度减1 → in_degree[4] = 0 → 加入队列[4]515
‌第五轮处理‌取出顶点4，加入结果序列[1, 5, 2, 3, 4]
顶点4无出边，队列空1013
‌终止检测‌结果序列长度=5，等于顶点数 → 成功输出拓扑序：1 5 2 3 4
（注：1 5 3 2 4也是合法拓扑序）