BFS、DFS和dijkstra演算法-python - IT閱讀

BFS、DFS和dijkstra演算法-python ... bfs演算法，寬度優先搜尋演算法。

def bfs(graph,start): queue,visited = [start],[start] ... BFS、DFS和dijkstra演算法-python 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search BFS、DFS和dijkstra演算法-python 2018-11-16254 bfs演算法，寬度優先搜尋演算法。

defbfs(graph,start): queue,visited=[start],[start] whilequeue: vertex=queue.pop() foriingraph[vertex]: ifinotinvisited: visited.append(i) queue.append(i) returnvisited G={"A":{"B","D"}, "B":{"C","E"}, "C":{"E","F"}, "D":{"G"}, "E":{"D","F","G","H"}, "F":{"H"}, "G":{"H"}, "H":{}} print(bfs(G,'A')) 【'A','B','D','E','C','G','H','F'】 DFS演算法：深度優先搜尋演算法 defdfs(graph,vertex,queue=[]): queue.append(vertex) foriingraph[vertex]: ifinotinqueue: queue=dfs(graph,i,queue) returnqueue graph={1:[2,3],2:[4,5], 3:[5],4:[6],5:[6], 6:[7],7:[]} print(dfs(graph,1,)) 執行結果[1,2,3,4,5,6,7] dijkstra演算法：求訪問完所有節點的最短路徑 G={1:{2:5,4:2,5:7}, 2:{3:4}, 3:{}, 4:{2:1,3:10}, 5:{3:3}} defdijkstra(graph,source): visited=set() distance=dict((k,float("inf"))forkinG.keys()) distance[source]=0 whilelen(G)!=len(visited): visited.add(source) fornext_nodeingraph[source]: ifdistance[next_node]>distance[source]+graph[source][next_node]: distance[next_node]=distance[source]+graph[source][next_node] INF=float("inf") fornodeindistance.keys(): ifnodenotinvisitedanddistance[node]