递归算法进行无向图的深度优先搜索法
时间: 2024-03-30 13:15:05 浏览: 18
无向图的深度优先搜索算法可以使用递归来实现。具体步骤如下:
1.从任一顶点开始遍历,将该顶点标记为已访问。
2.遍历该顶点的所有邻接顶点,如果邻接顶点未被访问,则以该邻接顶点为起点继续递归遍历。
3.重复步骤2,直到所有邻接顶点都被访问过。
4.如果还存在未被访问的顶点,则返回步骤1,否则结束遍历。
下面是使用递归实现无向图深度优先搜索的示例代码:
```python
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 测试代码
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 4],
3: [1, 5],
4: [1, 2, 5],
5: [3, 4]
}
visited = [False] * (len(graph))
dfs(graph, 0, visited)
```
在上面的代码中,我们首先定义了一个dfs函数,dfs函数接收三个参数,分别是图graph、当前遍历顶点v和访问标记visited。在dfs函数中,我们首先将当前顶点v标记为已访问,然后将该顶点输出。接下来,我们遍历该顶点的所有邻接顶点i,如果邻接顶点i未被访问,则以该邻接顶点i为起点继续递归遍历。最后,在测试代码中,我们定义了一个图,并对该图进行深度优先搜索遍历。
希望能对你有所帮助!