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')
现在我们已经了解了两种基本的图遍历算法，我们将在接下来的页面中了解其他算法如何在图数据结构上运行。
