Python - 圖演算法

圖在解決許多重要的數學挑戰方面是非常有用的資料結構。例如計算機網路拓撲或分析化學化合物的分子結構。它們還用於城市交通或路線規劃，甚至用於人類語言及其語法。所有這些應用都面臨著一個共同的挑戰，即使用其邊遍歷圖並確保訪問圖的所有節點。有兩種常用的成熟方法可以進行這種遍歷，如下所述。

深度優先遍歷

也稱為深度優先搜尋 (DFS)，此演算法以深度優先的方式遍歷圖，並使用棧來記住在任何迭代中發生死衚衕時要開始搜尋的下一個頂點。我們使用集合資料型別在 Python 中實現圖的 DFS，因為它們提供了跟蹤已訪問和未訪問節點所需的函式。

示例

class graph:
   def __init__(self,gdict=None):
      if gdict is None:
         gdict = {}
      self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
   if visited is None:
      visited = set()
   visited.add(start)
   print(start)
   for next in graph[start] - visited:
      dfs(graph, next, visited)
   return visited

gdict = { 
   "a" : set(["b","c"]),
   "b" : set(["a", "d"]),
   "c" : set(["a", "d"]),
   "d" : set(["e"]),
   "e" : set(["a"])
}
dfs(gdict, 'a')

輸出

執行上述程式碼時，會產生以下結果：

a 
b 
d 
e 
c

廣度優先遍歷

也稱為廣度優先搜尋 (BFS)，此演算法以廣度優先的方式遍歷圖，並使用佇列來記住在任何迭代中發生死衚衕時要開始搜尋的下一個頂點。請訪問我們網站上的此連結以瞭解圖的 BFS 步驟的詳細資訊。

我們在 Python 中使用前面討論的佇列資料結構實現圖的 BFS。當我們繼續訪問相鄰的未訪問節點並將其新增到佇列中時。然後，我們只開始出隊那些沒有未訪問節點的節點。當沒有下一個相鄰節點要訪問時，我們停止程式。

示例

import collections
class graph:
   def __init__(self,gdict=None):
      if gdict is None:
         gdict = {}
      self.gdict = gdict
def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
   seen, queue = set([startnode]), collections.deque([startnode])
   while queue:
      vertex = queue.popleft()
      marked(vertex)
      for node in graph[vertex]:
         if node not in seen:
            seen.add(node)
            queue.append(node)

def marked(n):
   print(n)

# The graph dictionary
gdict = { 
   "a" : set(["b","c"]),
   "b" : set(["a", "d"]),
   "c" : set(["a", "d"]),
   "d" : set(["e"]),
   "e" : set(["a"])
}
bfs(gdict, "a")

輸出

執行上述程式碼時，會產生以下結果：

a 
c 
b 
d 
e