邻接表深度优先遍历和广度优先遍历的代码
时间: 2023-06-23 11:59:15 浏览: 118
以下是邻接表深度优先遍历和广度优先遍历的 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 类型来实现。
阅读全文