拓扑排序精讲
from collections import dequedef bfs(degrees):nodes = deque()for j in range(n):if degrees[j]==0:nodes.append(j)result = [] while nodes:idx = nodes.popleft()result.append(str(idx))if depend[idx]:for file in depend[idx]:degrees[file]-=1if degrees[file]==0:nodes.append(file)if len(result)==n:print((' ').join(result))else:print(-1)if __name__=="__main__":n,m = map(int, input().split())degrees = [0]*ndepend = [[] for _ in range(n)]for i in range(m):a,b = map(int, input().split())depend[a].append(b)degrees[b]+=1bfs(degrees)
dijkstra（朴素版）精讲
def dijkstra(graph, n):min_dist = [float('inf')]*nvisited = [False]*nmin_dist[0]=0for i in range(n):min_val = float('inf')cur = -1for j in range(n):if not visited[j] and min_dist[j]<min_val:min_val = min_dist[j]cur = jvisited[cur]=Truefor k in range(n):if not visited[j] and min_dist[cur]+graph[cur][k]<min_dist[k]:min_dist[k]=graph[cur][k]+min_dist[cur]if min_dist[-1] == float('inf'):print(-1)else:print(min_dist[-1])if __name__=='__main__':n,m = map(int, input().split())graph = [[float('inf')]*n for _ in range(n)]for i in range(m):s,e,v = map(int, input().split())graph[s-1][e-1]=vdijkstra(graph, n)
prim和dijkstra的区别
- prim是求非访问节点到最小生成树的最小距离，而dijkstra是求非访问节点到源点的最小距离。
- prim算法可以有负权值，dijkstra算法不可以有负权值
- prim 更新 minDist数组的写法：
for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}
}
- dijkstra 更新 minDist数组的写法：
for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}
}
