本文實例講述了Python數據結構與算法之圖的廣度優先與深度優先搜索算法。分享給大家供大家參考，具體如下：

根據維基百科的偽代碼實現：

廣度優先BFS：

使用隊列，集合

標記初始結點已被發現，放入隊列

每次循環從隊列彈出一個結點

將該節點的所有相連結點放入隊列，并標記已被發現

通過隊列，將迷宮路口所有的門打開，從一個門進去繼續打開里面的門，然后返回前一個門處

""" procedure BFS(G,v) is   let Q be a queue   Q.enqueue(v)   label v as discovered   while Q is not empty    v ← Q.dequeue()    procedure(v)    for all edges from v to w in G.adjacentEdges(v) do      if w is not labeled as discovered        Q.enqueue(w)        label w as discovered"""def procedure(v):  passdef BFS(G,v0):  """ 廣度優先搜索 """  q, s = [], set()  q.extend(v0)  s.add(v0)  while q:  # 當隊列q非空    v = q.pop(0)    procedure(v)    for w in G[v]:   # 對圖G中頂點v的所有鄰近點w      if w not in s: # 如果頂點 w 沒被發現        q.extend(w)        s.add(w)  # 記錄w已被發現

深度優先DFS

使用 棧，集合

初始結點入棧

每輪循環從棧中彈出一個結點，并標記已被發現

對每個彈出的結點，將其連接的所有結點放到隊列中

通過棧的結構，一步步深入挖掘

""""Pseudocode[edit]Input: A graph G and a vertex v of GOutput: All vertices reachable from v labeled as discoveredA recursive implementation of DFS:[5]1 procedure DFS(G,v):2   label v as discovered3   for all edges from v to w in G.adjacentEdges(v) do4     if vertex w is not labeled as discovered then5       recursively call DFS(G,w)A non-recursive implementation of DFS:[6]1 procedure DFS-iterative(G,v):2   let S be a stack3   S.push(v)4   while S is not empty5      v = S.pop()6      if v is not labeled as discovered:7        label v as discovered8        for all edges from v to w in G.adjacentEdges(v) do9          S.push(w)"""def DFS(G,v0):  S = []  S.append(v0)  label = set()  while S:    v = S.pop()    if v not in label:      label.add(v)      procedure(v)      for w in G[v]:        S.append(w)

更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》

希望本文所述對大家Python程序設計有所幫助。