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)，該演算法使用佇列記住當任何疊代中發生死角時，獲取下一個頂點以開始搜尋。

我們使用之前討論的佇列資料結構在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