无向连通图的广度遍历序列和深度遍历序列的输出。输入描述 顶点个数,边的条数,边的信息(每条边只输入一次)。 输出描述 从V0出发的广度遍历序列和深度遍历序列 的代码
时间: 2023-07-24 18:14:57 浏览: 156
以下是一个简单的无向连通图的广度遍历和深度遍历的 Python 代码实现,输入格式为:第一行为顶点个数和边的条数,接下来的每一行为一条边的信息,包括起点和终点。
广度遍历使用了队列(Queue)数据结构,深度遍历使用了递归。
```python
from collections import defaultdict, deque
# 读取输入
n, m = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
# 广度遍历
visited = [False] * n
queue = deque([0])
bfs_order = []
while queue:
node = queue.popleft()
if not visited[node]:
visited[node] = True
bfs_order.append(node)
for neighbor in graph[node]:
queue.append(neighbor)
# 深度遍历
visited = [False] * n
dfs_order = []
def dfs(node):
visited[node] = True
dfs_order.append(node)
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor)
dfs(0)
# 输出结果
print("BFS order:", bfs_order)
print("DFS order:", dfs_order)
```
注意:这里默认起点为 V0,如果需要更改起点,只需将 `queue` 中的初始值改为其他节点即可。
阅读全文