代码随想录算法训练营第58天|拓扑排序精讲、dijkstra（朴素版）精讲

1.拓扑排序精讲

题目链接：拓扑排序精讲
文档讲解： 代码随想录

给出一个有向图，把这个有向图转成线性的排序就叫拓扑排序。拓扑排序要检测这个有向图是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。所以拓扑排序是图论中判断有向无环图的常用方法。拓扑排序的过程，有两步，第一步，找到入度为0的节点，加入结果集；第二步，将该节点从图中移除。 循环以上两步，直到所有节点都在图中被移除了。结果集的顺序，就是想要的拓扑排序顺序。

from collections import deque,defaultdict
def topological_sort(n,edges):#统计入度indegree = [0] * (n)#记录依赖关系umap = defaultdict(list)for s,t in edges:indegree[t] += 1 umap[s].append(t)#初始化队列，加入所有入度为0的点que = deque([i for i in range(n) if indegree[i] == 0])res = [] while que:cur = que.popleft()res.append(cur)for file in umap[cur]:#获取该文件指向的文件indegree[file] -= 1 if indegree[file] == 0:que.append(file)if len(res) == n:print(' '.join(map(str,res)))else:print(-1)
if __name__ == '__main__':n,m = map(int,input().split())edges = [] for _ in range(m):edges.append(list(map(int,input().split())))topological_sort(n,edges)

2.dijkstra（朴素版）精讲

题目链接：dijkstra（朴素版）精讲
文档讲解： 代码随想录
这道题是求最短路，最短路是图论中的经典问题，给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。在dijkstra算法中，同样有一个数组很重要，起名为：minDist。minDist数组用来每个节点距离源点的最小距离。dijkstra算法的两个注意点：可以同时求起点到所有节点的最短路径；权值不能是负数。

def dijkstra(n,edges,start,end):#初始化邻接矩阵grid = [[float('inf')] * (n+1) for _ in range(n+1)]for s,e,v in edges:grid[s][e] = v #初始化距离数组和访问数组minDist = [float('inf')] * (n+1)visited = [False] * (n+1)minDist[start] = 0 for _ in range(1,n+1):minval = float('inf')cur = -1 #选择距离源点最近且未访问的节点for j in range(1,n+1):if not visited[j] and minDist[j] < minval:minval = minDist[j]cur = j if cur == -1:break visited[cur] = True #更新minDist数组for j in range(1,n+1):if not visited[j] and grid[cur][j] != float('inf') and minDist[cur] + grid[cur][j] < minDist[j]:minDist[j] = minDist[cur] + grid[cur][j]if minDist[end] == float('inf'):return -1 else:return minDist[end]
if __name__ == "__main__":n,m = map(int,input().split())edges = [] for _ in range(m):edges.append(list(map(int,input().split())))res = dijkstra(n,edges,1,n)print(res)

dijkstra算法与prim算法唯一区别在于更新minDist数组。prim算法是求非访问节点到最小生成树的最小距离，而dijkstra算法是求非访问节点到源点的最小距离。