使用邻接表建立图,并实现BFS,DFS的完整代码
时间: 2023-12-18 14:07:18 浏览: 29
邻接表是一种表示图的数据结构,其中每个节点都与其相邻的节点列表相关联。我们可以使用邻接表来表示无向图和有向图。
下面是使用邻接表实现图,并实现BFS和DFS算法的完整代码(使用Python语言实现):
```python
from collections import defaultdict
# 创建一个类来表示图
class Graph:
def __init__(self):
self.graph = defaultdict(list)
# 添加边
def add_edge(self, u, v):
self.graph[u].append(v)
# BFS算法
def bfs(self, s):
visited = [False] * len(self.graph) # 标记所有节点为未访问
queue = [] # 创建一个队列用来存储待访问的节点
queue.append(s) # 将起始节点加入队列
visited[s] = True # 标记起始节点为已访问
while queue:
s = queue.pop(0) # 从队列中取出一个节点
print(s, end=" ") # 输出节点
for i in self.graph[s]: # 遍历当前节点的所有相邻节点
if not visited[i]: # 如果相邻节点未被访问
queue.append(i) # 将相邻节点加入队列
visited[i] = True # 标记相邻节点为已访问
# DFS算法
def dfs(self, s, visited):
visited[s] = True # 标记当前节点为已访问
print(s, end=" ") # 输出节点
# 遍历当前节点的所有相邻节点
for i in self.graph[s]:
if not visited[i]: # 如果相邻节点未被访问
self.dfs(i, visited) # 递归访问相邻节点
# 创建一个图对象
g = Graph()
# 添加图的边
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
# 输出BFS遍历结果
print("BFS遍历结果:")
g.bfs(2)
# 输出DFS遍历结果
print("\nDFS遍历结果:")
visited = [False] * len(g.graph)
g.dfs(2, visited)
```
输出结果:
```
BFS遍历结果:
2 0 3 1
DFS遍历结果:
2 0 1 3
```
这个代码演示了如何使用邻接表来表示图,并实现了BFS和DFS算法来遍历图。