输入:一个基于邻接表或邻接矩阵存储的无向图 实现:用非递归算法实现深度或广度遍历一个无向图,并输出遍历结果,其中如果图不联通,可能需要多次遍历。
时间: 2023-06-26 18:09:14 浏览: 50
以下是基于邻接表存储的无向图的非递归算法实现深度优先遍历的代码:
```python
def DFS(graph):
visited = set() # 用一个集合记录已经访问过的节点
for start_node in graph.keys(): # 遍历所有节点,防止有不连通的情况
if start_node not in visited:
stack = [start_node] # 用一个栈来实现非递归遍历
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
for neighbor in graph[node]:
stack.append(neighbor)
```
以下是基于邻接矩阵存储的无向图的非递归算法实现广度优先遍历的代码:
```python
from collections import deque
def BFS(graph):
visited = set()
for start_node in graph.keys():
if start_node not in visited:
queue = deque([start_node]) # 用一个双端队列来实现非递归遍历
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
print(node)
for neighbor_idx, is_connected in enumerate(graph[node]):
if is_connected:
queue.append(list(graph.keys())[neighbor_idx])
```
需要注意的是,如果图不连通,需要多次调用遍历函数。具体实现可以在每次调用前判断是否还有未访问过的节点即可。