用非递归算法实现深度或广度遍历一个基于邻接表或邻接矩阵存储的无向图,并输出遍历结果,其中如果图不联通,可能需要多次遍历。
时间: 2023-06-26 20:09:11 浏览: 78
图的邻接表存储下的遍历算法
4星 · 用户满意度95%
以下是基于邻接表存储的无向图的深度优先遍历和广度优先遍历的非递归实现:
```python
from queue import Queue
# 图的邻接表表示
graph = {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1, 4],
3: [1, 4],
4: [2, 3]
}
# 深度优先遍历
def dfs(graph, start):
visited = set() # 记录已访问过的节点
stack = [start] # 使用栈来实现非递归
while stack:
node = stack.pop()
if node not in visited:
print(node, end=' ')
visited.add(node)
# 将未访问的邻居节点入栈
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
# 广度优先遍历
def bfs(graph, start):
visited = set() # 记录已访问过的节点
q = Queue() # 使用队列来实现非递归
q.put(start)
visited.add(start)
while not q.empty():
node = q.get()
print(node, end=' ')
# 将未访问的邻居节点入队
for neighbor in graph[node]:
if neighbor not in visited:
q.put(neighbor)
visited.add(neighbor)
# 测试
print("DFS:")
for i in range(len(graph)):
if i not in visited:
dfs(graph, i)
print("\nBFS:")
for i in range(len(graph)):
if i not in visited:
bfs(graph, i)
```
对于邻接矩阵存储的无向图,只需要稍微调整一下代码即可:将邻接表的列表改为邻接矩阵的数组,将遍历邻居节点的方式改为遍历该节点所在行的元素。
需要注意的是,如果图不连通,则需要多次遍历。可以在遍历完一个连通分量后,找到一个未访问的节点作为起点,继续遍历下一个连通分量。
阅读全文