DSA 圖形遍歷
圖形遍歷
遍歷圖意味著從一個頂點開始，沿著邊訪問其他頂點，直到所有頂點或儘可能多的頂點都被訪問。
結果
理解如何遍歷圖對於理解在圖上執行的演算法的工作原理很重要。
遍歷圖的兩種最常見方式是
- 深度優先搜尋 (DFS)
- 廣度優先搜尋 (BFS)
DFS 通常使用棧或遞迴（利用呼叫棧）來實現，而 BFS 通常使用佇列來實現。
呼叫棧以正確的順序保持函式執行。
例如，如果 FunctionA 呼叫 FunctionB，FunctionB 被放置在呼叫棧的頂部並開始執行。一旦 FunctionB 完成，它就會從棧中移除，然後 FunctionA 繼續其工作。
深度優先搜尋遍歷
深度優先搜尋被認為是“深入”的，因為它訪問一個頂點，然後是一個相鄰頂點，然後是該相鄰頂點的一個相鄰頂點，依此類推，透過這種方式，每次遞迴迭代都會增加與起始頂點的距離。
工作原理
- 在頂點上開始 DFS 遍歷。
- 對每個相鄰頂點進行遞迴 DFS 遍歷，只要它們尚未被訪問。
執行下面的動畫，檢視深度優先搜尋 (DFS) 遍歷如何在特定圖上執行，從頂點 D 開始（與上一個動畫相同）。
結果
DFS 遍歷從頂點 D 開始，將頂點 D 標記為已訪問。然後，對於每個新訪問的頂點，遞迴呼叫遍歷方法以訪問所有尚未訪問的相鄰頂點。因此，當動畫中訪問頂點 A 時，頂點 C 或頂點 E（取決於實現）是遍歷繼續的下一個頂點。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
def dfs_util(self, v, visited):
visited[v] = True
print(self.vertex_data[v], end=' ')
for i in range(self.size):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)
def dfs(self, start_vertex_data):
visited = [False] * self.size
start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0) # D - A
g.add_edge(0, 2) # A - C
g.add_edge(0, 3) # A - D
g.add_edge(0, 4) # A - E
g.add_edge(4, 2) # E - C
g.add_edge(2, 5) # C - F
g.add_edge(2, 1) # C - B
g.add_edge(2, 6) # C - G
g.add_edge(1, 5) # B - F
g.print_graph()
print("\nDepth First Search starting from vertex D:")
g.dfs('D')
第 60 行：當呼叫 dfs() 方法時，DFS 遍歷開始。
第 33 行：visited 陣列最初對所有頂點設定為 false，因為此時還沒有頂點被訪問。
第 35 行：visited 陣列作為引數傳送到 dfs_util() 方法。當 visited 陣列這樣作為引數傳送時，它實際上只是傳送到 dfs_util() 方法的 visited 陣列的引用，而不是實際包含值的陣列。因此，我們的程式中始終只有一個 visited 陣列，並且 dfs_util() 方法可以在訪問節點時對其進行更改（第 25 行）。
第 28-30 行：對於當前頂點 v，如果所有相鄰節點尚未被訪問，則遞迴呼叫它們。
廣度優先搜尋遍歷
廣度優先搜尋在訪問相鄰頂點的鄰居頂點之前，會訪問一個頂點的所有相鄰頂點。這意味著與起始頂點距離相同的頂點會在距離起始頂點更遠的頂點之前被訪問。
工作原理
- 將起始頂點放入佇列。
- 對於從佇列中取出的每個頂點，訪問該頂點，然後將所有未訪問的相鄰頂點放入佇列。
- 只要佇列中有頂點，就繼續執行。
執行下面的動畫，檢視廣度優先搜尋 (BFS) 遍歷如何在特定圖上執行，從頂點 D 開始。
結果
如上圖所示，BFS 遍歷會在訪問距離更遠的頂點之前，訪問距離起始頂點相同的頂點。因此，例如，在訪問頂點 A 之後，在訪問 B、F 和 G 之前，會訪問頂點 E 和 C，因為這些頂點距離更遠。
廣度優先搜尋遍歷透過將所有相鄰頂點（如果它們尚未被訪問）放入佇列，然後使用佇列訪問下一個頂點來工作。這種方式確保了首先訪問距離起始頂點最近的頂點。
此廣度優先搜尋遍歷的程式碼示例與上面的深度優先搜尋程式碼示例相同，除了 bfs() 方法
示例
Python
def bfs(self, start_vertex_data):
queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * self.size
visited[queue[0]] = True
while queue:
current_vertex = queue.pop(0)
print(self.vertex_data[current_vertex], end=' ')
for i in range(self.size):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True第 2-4 行：bfs() 方法首先建立一個包含起始頂點的佇列，建立一個 visited 陣列，並將起始頂點設定為已訪問。
第 6-13 行：BFS 遍歷透過從佇列中取出一個頂點，列印它，並將相鄰的未訪問頂點新增到佇列中，然後以這種方式繼續從佇列中取出頂點。當佇列中的最後一個元素沒有未訪問的相鄰頂點時，遍歷結束。
有向圖的 DFS 和 BFS 遍歷
深度優先和廣度優先遍歷實際上只需很少的更改即可實現在有向圖（而不是無向圖）上工作。
執行下面的動畫，檢視有向圖如何使用 DFS 或 BFS 進行遍歷。
結果
要從遍歷無向圖變為遍歷有向圖，我們只需刪除 add_edge() 方法中的最後一行即可
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
在構建圖時，我們還必須小心，因為邊現在是有向的。
以下程式碼示例包含動畫中所示有向圖的 BFS 和 DFS 遍歷
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
#self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
def dfs_util(self, v, visited):
visited[v] = True
print(self.vertex_data[v], end=' ')
for i in range(self.size):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)
def dfs(self, start_vertex_data):
visited = [False] * self.size
start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)
def bfs(self, start_vertex_data):
queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * self.size
visited[queue[0]] = True
while queue:
current_vertex = queue.pop(0)
print(self.vertex_data[current_vertex], end=' ')
for i in range(self.size):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0) # D -> A
g.add_edge(3, 4) # D -> E
g.add_edge(4, 0) # E -> A
g.add_edge(0, 2) # A -> C
g.add_edge(2, 5) # C -> F
g.add_edge(2, 6) # C -> G
g.add_edge(5, 1) # F -> B
g.add_edge(1, 2) # B -> C
g.print_graph()
print("\nDepth First Search starting from vertex D:")
g.dfs('D')
print("\n\nBreadth First Search starting from vertex D:")
g.bfs('D')
現在我們已經瞭解了兩種基本的圖遍歷演算法，我們將在接下來的頁面中瞭解其他演算法如何在圖資料結構上執行。
