实现图的深度优先遍历和广度优先遍历算法。
时间: 2023-10-04 09:07:39 浏览: 73
深度优先遍历算法(DFS):
1. 从图中任意一个顶点开始遍历,将该顶点标记为已访问。
2. 从该顶点出发,遍历与之相邻的顶点,如果相邻的顶点未被访问,则以该顶点为起点递归执行步骤2。
3. 重复步骤2,直到该顶点的所有相邻顶点都被访问过。
Python代码实现:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next_vertex in graph[start] - visited:
dfs(graph, next_vertex, visited)
return visited
```
广度优先遍历算法(BFS):
1. 从图中任意一个顶点开始遍历,将该顶点标记为已访问,并将该顶点入队列。
2. 从队列中取出第一个顶点,并遍历其相邻的顶点,如果相邻的顶点未被访问,则将该顶点标记为已访问,并将该顶点入队列。
3. 重复步骤2,直到队列为空。
Python代码实现:
```python
from collections import deque
def bfs(graph, start):
visited, queue = set(), deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
```
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231044930.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241231044955.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![txt](https://img-home.csdnimg.cn/images/20241231045021.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)