无向图深度优先遍历序列、广度优先遍历序列

### 无向图的深度优先遍历和广度优先遍历 #### 深度优先遍历 (Depth First Search, DFS) 深度优先搜索是一种用于遍历或搜索树或图的算法。其核心思想是从起始节点开始，沿着一条路径尽可能深入地探索下去，直到无法继续前进为止。此时回溯到最近的一个可以扩展的新节点，并重复这一过程，直到所有可达节点都被访问完毕。 以下是基于递归实现的深度优先遍历伪代码： ```python def dfs(graph, vertex, visited): visited[vertex] = True # 标记当前顶点已访问 print(vertex, end=" ") # 输出当前顶点 for neighbor in graph[vertex]: # 遍历当前顶点的所有邻居 if not visited[neighbor]: # 如果邻居未被访问 dfs(graph, neighbor, visited) # 对邻居进行递归调用 ``` 对于无向图而言，假设输入图为邻接表表示形式 `graph`，其中每个键对应于一个顶点，而对应的值是一个列表，存储与其相连的所有其他顶点。通过上述方法可以从任意指定的起始顶点开始执行深度优先遍历[^1]。 --- #### 广度优先遍历 (Breadth First Search, BFS) 广度优先搜索则采用另一种方式来处理图结构中的数据——按照层次顺序逐层展开。具体来说就是先将根结点加入队列中；接着取出队首元素并将其子代全部入队；最后不断循环直至整个队列为空即完成操作流程。 下面是利用队列机制实现的标准版本之一: ```python from collections import deque def bfs(graph, start_vertex): visited = set() # 创建集合记录已经访问过的节点 queue = deque([start_vertex]) # 初始化队列并将起点压入队列 while queue: vertex = queue.popleft() # 取出队头元素作为当前要处理的对象 if vertex not in visited: # 若该对象尚未被标记为已查看状态的话... visited.add(vertex) # 添加至visited集表明已被读取过了 print(vertex, end=' ') # 打印这个位置的信息 # 将与vertex相连接但还未进入过队列里的那些成员逐一追加进去 queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited) ``` 这里同样假定传入参数`graph`代表的是以字典形式呈现出来的关联关系网络模型，而且每一个key所映射得到的那个list里面包含了指向其它各个关联实体的名字字符串或者编号整数等等类型的标识符[^2]。 --- ### 示例分析 考虑如下简单的无向图及其可能产生的两种不同类型的遍历结果示例： 给定一张具有四个节点 {0, 1, 2, 3} 的连通无向图 G ，它的边集 E={(0,1),(0,2),(1,2),(2,3)} 。如果选取源点 s=0 进行分别应用DFS 和 BFS 方法计算可得相应次序分别为 ： - **DFS Sequence**: 假设总是优先选择较小索引号的方向移动，则最终获得的一条合法路径可能是 `[0 -> 1 -> 2 -> 3]`. - **BFS Sequence**: 同样条件下得出的结果应表现为水平方向逐步延展的形式:`[0 -> 1 -> 2 -> 3]`. 值得注意的是实际运行过程中由于存在多种分支可能性所以确切数值可能会有所差异取决于具体编码细节以及内部随机因素影响等因素共同决定最终输出形态[^3]. ---