无向图深度优先搜索遍历
时间: 2023-11-07 21:53:53 浏览: 67
无向图的深度优先搜索遍历是一种用于搜索图的算法。它从给定的起始节点开始,沿着一条路径尽可能深入地搜索,直到到达不能再深入的节点为止,然后返回到前一个节点,继续搜索下一条路径。这个过程会不断重复,直到遍历完所有可以到达的节点。
基于递归的深度优先搜索实现代码如下所示:
```python
def dfs_recursive(graph, start, visited):
visited.add(start) # 标记节点为已访问
print(start) # 访问节点
for end in graph[start]:
if end not in visited:
dfs_recursive(graph, end, visited) # 递归遍历节点
```
基于堆栈的深度优先搜索实现步骤如下:
1. 创建一个堆栈,用于存储待访问的节点。
2. 将起始节点压入堆栈,并将其标记为已访问。
3. 当堆栈不为空时,执行以下步骤:
1) 从堆栈中弹出一个节点作为当前节点。
2) 访问当前节点。
3) 将当前节点的未访问邻居节点压入堆栈,并将其标记为已访问。
4. 重复步骤3,直到堆栈为空。
请注意,无向图深度优先搜索的结果可能因起始节点的选择而不同。
相关问题
无向图的深度优先遍历
无向图的深度优先遍历(Depth First Search,DFS)是一种用于遍历或搜索树或图的算法。在深度优先遍历中,从一个节点开始,尽可能深地探索每个分支,直到无法继续为止,然后回溯到前一个节点,尝试探索其他分支。这个过程一直进行到所有节点都被访问为止。
以下是无向图的深度优先遍历的伪代码:
1. 从起始顶点开始遍历
2. 标记起始顶点为已访问
3. 对于起始顶点的每个未访问的邻居顶点:
1. 递归调用深度优先遍历函数
4. 返回
在实际编程中,可以使用递归或栈来实现深度优先遍历。以下是使用递归实现的 Python 代码示例:
```python
def dfs(graph, vertex, visited):
visited.add(vertex)
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
```
其中,graph 是一个字典,表示无向图的邻接表,vertex 是当前遍历的顶点,visited 是一个集合,用于保存已访问过的顶点。
无向图的深度优先遍历和广度优先遍历
以下是无向图的深度优先遍历和广度优先遍历的介绍和演示:
1.深度优先遍历(DFS):
深度优先遍历是一种用于遍历或搜索树或图的算法。在这种搜索方法中,从根结点开始,尽可能深地搜索每个分支,直到找到目标值或无法继续为止。然后回溯到前一个结点,尝试另一条分支,直到所有结点都被访问为止。
以下是一个无向图的深度优先遍历的Python代码示例:
```python
# 无向图的深度优先遍历
def DFS(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for next in graph[start] - visited:
DFS(graph, next, visited)
return visited
# 无向图的邻接表表示
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
# 从顶点A开始遍历
print("深度优先遍历结果:")
DFS(graph, 'A')
```
输出结果为:A B D E F C
2.广度优先遍历(BFS):
广度优先遍历是一种用于遍历或搜索树或图的算法。在这种搜索方法中,从根结点开始,逐层遍历每个分支,直到找到目标值或无法继续为止。
以下是一个无向图的广度优先遍历的Python代码示例:
```python
# 无向图的广度优先遍历
def BFS(graph, start):
visited, queue = set(), [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for next in graph[vertex] - visited:
visited.add(next)
queue.append(next)
# 无向图的邻接表表示
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
# 从顶点A开始遍历
print("广度优先遍历结果:")
BFS(graph, 'A')
```
输出结果为:A B C D E F
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)