DSA 图遍历
图遍历
遍历图意味着从一个顶点开始，沿着边访问其他顶点，直到所有顶点（或尽可能多）都被访问为止。
结果
了解图如何被遍历对于理解在图上运行的算法如何工作很重要。
图遍历的两种最常见方式是
- 深度优先搜索 (DFS)
- 广度优先搜索 (BFS)
DFS 通常使用 栈 或递归（利用调用栈）来实现，而 BFS 通常使用 队列 来实现。
调用栈 保持函数按正确顺序运行。
例如，如果函数 A 调用函数 B，则函数 B 被放置在调用栈的顶部并开始运行。函数 B 完成后，它将从栈中移除，然后函数 A 恢复其工作。
深度优先搜索遍历
深度优先搜索被称为“深度”搜索，因为它访问一个顶点，然后访问其相邻顶点，然后访问其相邻顶点的相邻顶点，依此类推。以这种方式，从起始顶点的距离在每次递归迭代中增加。
工作原理
- 从一个顶点开始 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 数组像这样被传递作为参数时，它实际上只是一个指向 visited 数组的引用，该引用被传递给 dfs_util() 方法，而不是实际的数组及其内部值。因此，我们的程序中始终只有一个 visited 数组，并且 dfs_util() 方法可以对它进行更改，因为节点被访问（第 25 行）。
第 28-30 行： 对于当前顶点 v，如果所有相邻节点尚未被访问，则递归调用它们。
广度优先搜索遍历
广度优先搜索在访问相邻顶点的相邻顶点之前，访问一个顶点的所有相邻顶点。这意味着距离起始顶点相同的顶点将在距离起始顶点更远的顶点之前被访问。
工作原理
- 将起始顶点放入队列中。
- 对于从队列中取出的每个顶点，访问该顶点，然后将所有尚未被访问过的相邻顶点放入队列中。
- 只要队列中还有顶点，就继续执行。
运行下面的动画，看看广度优先搜索 (BFS) 遍历如何在特定图上运行，从顶点 D 开始。
结果
正如你在上面的动画中看到的，BFS 遍历在访问距离起始顶点更远的顶点之前，访问距离起始顶点相同的顶点。因此，例如，在访问顶点 A 之后，顶点 E 和 C 会在访问顶点 B、F 和 G 之前被访问，因为这些顶点距离更远。
广度优先搜索遍历通过将所有相邻顶点放入队列（如果它们尚未被访问）然后使用队列来访问下一个顶点，从而以这种方式工作。
广度优先搜索遍历的代码示例与上面的深度优先搜索代码示例相同，除了 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')
现在我们已经研究了两种基本的图遍历算法，接下来我们将看到其他算法如何在图数据结构上运行。
