本文主要是介绍day58-graph theory-part08-8.29，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
tasks for today：
1. 拓扑排序 117.软件构建
2. dijkstra算法 47.参加科学大会
---------------------------------------------------------------------------------
1. 拓扑排序 117.软件构建
In this practice, it involves mainly the BFS method, which iteratively searching the current graph for current nodes which have the inDegree 0, signifying that it is currently the files that should be taken before proceeding any other files that should be executed based on it. Then after this file is added to the result list, the files it points to has to reduce the inDegree by 1, until all the files are selcted. Or, it will output the -1 signifying there is no doable paln.
from collections import defaultdict, dequedef main():n, m = map(int, input().split())inDegree = [0] * npointTo = defaultdict(list)for _ in range(m):s, t = map(int, input().split())inDegree[t] += 1pointTo[s].append(t)bfsQueue = deque()for i in range(n):if inDegree[i] == 0:bfsQueue.append(i)result = []while bfsQueue:curNode = bfsQueue.popleft()result.append(curNode)curPointTo = pointTo[curNode]if curPointTo:for i in range(len(curPointTo)):inDegree[curPointTo[i]] -= 1if inDegree[curPointTo[i]] == 0:bfsQueue.append(curPointTo[i])if len(result) == n:print(' '.join(map(str, result)))else:print(-1)returnif __name__ == "__main__":main()2. dijkstra算法 47.参加科学大会
The idea of dijkstra is similar to prim algorithm in day 57.
After going through the entire process, each entry of the minDis records the minimum distance from the start point to current point.
def main():n, m = map(int, input().split())graph = [[float('inf')] * (n+1) for _ in range(n+1)]for _ in range(m):s, e, v = map(int, input().split())graph[s][e] = vvisited = [False] * (n+1)minDis = [float('inf')] * (n+1)start = 1end = nminDis[1] = 0for i in range(1, n+1):curMin = float('inf')curNode = 1for j in range(1, n+1):if not visited[j] and minDis[j] < curMin:curMin = minDis[j]curNode = jvisited[curNode] = Truefor k in range(1, n+1):if not visited[k] and graph[curNode][k] != float('inf') and minDis[k] > curMin + graph[curNode][k]:minDis[k] = curMin + graph[curNode][k]if minDis[n] == float('inf'): print(-1)else:print(minDis[n])returnif __name__ == "__main__":main()
这篇关于day58-graph theory-part08-8.29的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
