算法训练营day58 图论⑧ 拓扑排序精讲、dijkstra（朴素版）精讲

本篇应该是图论的经典部分了，本篇的内容作为小白没有了解过，但是至少会听说过——拓扑排序精讲、dijkstra（朴素版）精讲。

拓扑排序精讲

本题是拓扑排序的经典题目。一聊到拓扑排序，一些录友可能会想这是排序，不会想到这是图论算法。其实拓扑排序是经典的图论问题。

给出一个有向图，把这个有向图转成线性的排序就叫拓扑排序。当然拓扑排序也要检测这个有向图是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。所以拓扑排序也是图论中判断有向无环图的常用方法。

拓扑排序指的是一种解决问题的大体思路，而具体算法，可能是广搜也可能是深搜。实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS。一般来说我们只需要掌握 BFS （广度优先搜索）就可以了，清晰易懂，如果还想多了解一些，可以再去学一下 DFS 的思路，但 DFS 不是本篇重点。

当我们做拓扑排序的时候，应该优先找入度为 0 的节点，只有入度为0，它才是出发节点。 理解以上内容很重要！

接下来我给出拓扑排序的过程，其实就两步：

找到入度为0 的节点，加入结果集
将该节点从图中移除（从头开始循环）

结果集的顺序，就是我们想要的拓扑排序顺序（结果集里顺序可能不唯一）

判断有环

那么如果我们发现结果集元素个数不等于图中节点个数，我们就可以认定图中一定有有向环！这也是拓扑排序判断有向环的方法。

代码实现

并不需要一定要把节点删除，重点在于节点入度的判断，只要相关节点入度-1即可，重点在于对于节点入度的处理，以及通过队列结构对于节点的遍历，类似我们之前做到过的二叉树的层序遍历

# 导入必要的模块
# deque：用于实现队列（高效的弹出左侧元素操作）
# defaultdict：用于构建邻接表（默认值为列表，简化键不存在时的处理）
from collections import deque, defaultdictdef topological_sort(n, edges):"""拓扑排序函数：对有向无环图(DAG)进行拓扑排序，常用于解决依赖关系问题（如文件依赖、任务调度）参数：n: 节点总数（如文件数量）edges: 边的列表，每个元素为 tuple(s, t)，表示存在一条从 s 到 t 的有向边（s 依赖 t 或 t 依赖 s，根据场景而定）功能：输出拓扑排序结果；若图中存在环，则输出 -1"""# inDegree 数组：记录每个节点的入度（即有多少个前置依赖）# 索引代表节点编号，值代表入度数量inDegree = [0] * n# umap：邻接表，记录节点间的依赖关系# key 是起始节点，value 是 key 指向的所有节点（列表）umap = defaultdict(list)# 构建图（邻接表）和入度表for s, t in edges:# s -> t 表示：要完成 t 必须先完成 s（或 t 依赖 s）# 因此 t 的入度 +1（增加一个前置依赖）inDegree[t] += 1# 在邻接表中记录 s 指向 t（s 完成后可处理 t）umap[s].append(t)# 初始化队列：将所有入度为 0 的节点加入队列# 入度为 0 表示该节点没有前置依赖，可以直接开始处理queue = deque([i for i in range(n) if inDegree[i] == 0])# 存储拓扑排序的结果result = []# 队列不为空时，循环处理节点while queue:# 取出队列左侧的节点（当前可处理的节点）cur = queue.popleft()# 将当前节点加入结果列表result.append(cur)# 遍历当前节点指向的所有节点（即依赖当前节点的节点）for file in umap[cur]:# 依赖当前节点的节点，其入度减 1（少了一个前置依赖）inDegree[file] -= 1# 若入度减为 0，说明该节点的所有前置依赖都已处理完，可加入队列等待处理if inDegree[file] == 0:queue.append(file)# 若结果列表长度等于节点总数，说明所有节点都被处理（图无环），输出排序结果if len(result) == n:print(" ".join(map(str, result)))# 否则，说明图中存在环（部分节点因入度无法减为 0 而未被处理），输出 -1else:print(-1)if __name__ == "__main__":"""程序入口：读取输入并调用拓扑排序函数"""# 读取节点总数 n 和边数 mn, m = map(int, input().split())# 读取 m 条边，每条边为 (s, t) 的元组edges = [tuple(map(int, input().split())) for _ in range(m)]# 执行拓扑排序topological_sort(n, edges)

dijkstra（朴素版）精讲

dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

需要注意两点：

dijkstra 算法可以同时求起点到所有节点的最短路径
权值不能为负数

dijkstra三部曲：

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）

与prim算法基本一致，区别在于 dijkstra算法是一个积累的过程对数组赋值，而prim是当下节点的值没有累加。即：prim是求非访问节点到最小生成树的最小距离，而 dijkstra是求非访问节点到源点的最小距离。

prim算法可以有负权值吗？当然可以！prim算法只需要将节点以最小权值和链接在一起，不涉及到单一路径。

对于负值

该算法不能接受权值为负数（对应算法为Bellman-Ford 算法，后续讲），因为权值存在负数会对节点循环造成影响，需要多次遍历已经访问过的节点（之前是每个节点只会遍历一次），会造成循环结构的困扰

import sysdef dijkstra(n, m, edges, start, end):"""Dijkstra算法实现：求解从起点到终点的最短路径参数:n: 节点总数m: 边的数量edges: 边的列表，每个元素为元组(p1, p2, val)，表示从p1到p2的有向边，权重为valstart: 起点编号end: 终点编号返回:起点到终点的最短路径长度；若无法到达，返回-1"""# 初始化邻接矩阵，用于存储节点间的距离# 初始值设为无穷大(float('inf'))，表示初始时节点间不可达# 矩阵大小为(n+1)x(n+1)，因为节点编号从1开始grid = [[float('inf')] * (n + 1) for _ in range(n + 1)]# 填充邻接矩阵：根据边的信息设置节点间的距离for p1, p2, val in edges:grid[p1][p2] = val  # 有向边，仅设置p1到p2的距离# minDist数组：记录从起点到每个节点的最短距离# 初始值设为无穷大，表示尚未确定距离minDist = [float('inf')] * (n + 1)# visited数组：标记节点是否已被访问（即是否已确定最短路径）visited = [False] * (n + 1)# 起点到自身的距离为0minDist[start] = 0# Dijkstra算法主循环：需要遍历所有节点（最多n次）for _ in range(1, n + 1):# 1. 找到当前未访问且距离起点最近的节点minVal = float('inf')  # 暂存当前最小距离cur = -1               # 暂存选中的节点# 遍历所有节点，寻找符合条件的节点for v in range(1, n + 1):# 条件：未被访问 且 距离起点更近if not visited[v] and minDist[v] < minVal:minVal = minDist[v]  # 更新最小距离cur = v              # 更新选中的节点# 如果找不到可访问的节点（所有可达节点已处理），提前结束循环if cur == -1:break# 2. 标记当前节点为已访问（其最短路径已确定）visited[cur] = True# 3. 更新所有未访问节点通过当前节点到达起点的距离for v in range(1, n + 1):# 条件：# - 节点v未被访问# - 当前节点cur到v存在路径（距离不为无穷大）# - 通过cur到达v的距离比当前已知距离更短if not visited[v] and grid[cur][v] != float('inf') and minDist[cur] + grid[cur][v] < minDist[v]:# 更新最短距离minDist[v] = minDist[cur] + grid[cur][v]# 返回结果：若终点不可达（距离仍为无穷大），返回-1；否则返回最短距离return -1 if minDist[end] == float('inf') else minDist[end]if __name__ == "__main__":"""程序入口：读取输入并调用Dijkstra算法计算结果"""# 一次性读取所有输入数据input = sys.stdin.readdata = input().split()  # 按空白字符分割成列表# 解析节点总数和边数n, m = int(data[0]), int(data[1])# 解析所有边的信息edges = []index = 2  # 从第三个元素开始是边的信息for _ in range(m):p1 = int(data[index])p2 = int(data[index + 1])val = int(data[index + 2])edges.append((p1, p2, val))  # 将边信息存入列表index += 3  # 移动到下一条边的起始位置# 设定起点为1，终点为n（可根据实际需求修改）start = 1end = n# 调用Dijkstra算法计算最短路径并输出结果result = dijkstra(n, m, edges, start, end)print(result)