邻接表深度优先遍历和广度优先遍历的代码
时间: 2023-06-23 07:59:15 浏览: 119
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
以下是邻接表深度优先遍历和广度优先遍历的 Python 代码实现:
```python
from collections import deque
# 定义邻接表
graph = {
0: [1, 4],
1: [0, 2, 3, 4],
2: [1, 3],
3: [1, 2, 4],
4: [0, 1, 3]
}
# 深度优先遍历
def dfs(graph, start):
visited = set() # 用集合记录已经访问过的节点
stack = [start] # 用栈记录需要遍历的节点
while stack:
node = stack.pop() # 取出栈顶节点
if node not in visited:
visited.add(node) # 标记为已访问
print(node, end=" ")
# 将未访问过的相邻节点加入栈中
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
# 广度优先遍历
def bfs(graph, start):
visited = set() # 用集合记录已经访问过的节点
queue = deque([start]) # 用队列记录需要遍历的节点
while queue:
node = queue.popleft() # 取出队首节点
if node not in visited:
visited.add(node) # 标记为已访问
print(node, end=" ")
# 将未访问过的相邻节点加入队列中
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
# 测试
dfs(graph, 0) # 输出:0 1 2 3 4
print()
bfs(graph, 0) # 输出:0 1 4 2 3
```
注意,以上代码中使用了集合和队列来记录已经访问过的节点和需要遍历的节点。在 Python 中,集合可以使用 set 类型来实现,队列可以使用 deque 类型来实现。
阅读全文