邻接表和邻接矩阵的广度和深度优先遍历

邻接表和邻接矩阵中的广度优先遍历（BFS）
对于图结构而言，在实现广度优先遍历时，无论是采用邻接表还是邻接矩阵表示法，都需要利用队列数据结构来确保节点按照层次顺序被访问[^1]。
使用邻接列表进行BFS
当基于邻接表执行BFS时，程序会初始化一个队列并将起始顶点加入其中。接着进入循环处理阶段，每次从未标记过的邻居结点中选取并入队直到所有可达节点都被探索完毕：
from collections import deque

def bfs_adj_list(graph, start_vertex):
visited = set()
queue = deque([start_vertex])

while queue:
vertex = queue.popleft()

if vertex not in visited:
print(vertex)
visited.add(vertex)

for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
登录后复制
此段代码展示了如何通过Python语言构建一个简单的函数bfs_adj_list()用于对给定的邻接表形式的无向图实施广度优先搜索操作[^2]。
使用邻接矩阵进行BFS
如果使用的是邻接矩阵，则可以通过检查对应位置上的布尔值或权重判断两个顶点间是否存在边连接关系。同样地，这里也需要借助于队列完成逐层扩展过程:
def bfs_adj_matrix(matrix, num_vertices, start_vertex):
visited = [False] * num_vertices
queue = []

queue.append(start_vertex)
visited[start_vertex] = True

while queue:
s = queue.pop(0)
print(s, end=" ")

for i in range(num_vertices):
if matrix[s][i] and visited[i] == False:
queue.append(i)
visited[i] = True
登录后复制
上述例子说明了怎样针对由二维数组构成的有向/无向加权图运用广搜策略。

邻接表和邻接矩阵中的深度优先遍历（DFS）
相比之下，深度优先遍历更倾向于递归方式实现，并且不需要额外的数据容器支持像栈这样的辅助工具；不过也可以显式创建一个LIFO类型的存储空间来进行迭代式的深搜流程管理。
基于邻接表的DFS
下面给出了一种C风格伪码版本的dfs()函数定义，它