编写一段代码要求对建立的图进行深度优先搜索和广度优先搜索所得的遍历序列
时间: 2024-02-25 07:51:49 浏览: 73
掌握图的两种遍历算法深度优先搜索和广度优先搜索算.docx
好的,以下是一个无向图的深度优先搜索和广度优先搜索的 Python 代码示例:
```python
from collections import defaultdict
# 定义一个无向图类
class Graph:
def __init__(self):
self.graph = defaultdict(list)
# 添加边
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# 深度优先搜索遍历
def dfs(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbor in self.graph[v]:
if neighbor not in visited:
self.dfs(neighbor, visited)
# 广度优先搜索遍历
def bfs(self, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for neighbor in self.graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 测试
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("深度优先搜索遍历序列:")
g.dfs(2, set())
print("\n广度优先搜索遍历序列:")
g.bfs(2)
```
输出结果如下:
```
深度优先搜索遍历序列:
2 0 1 3
广度优先搜索遍历序列:
2 0 3 1
```
希望这可以帮到您!
阅读全文