采用图的邻接表作为图的存储结构,完成有向图和无向图的DFS和BFS操作。
时间: 2024-05-07 12:22:43 浏览: 17
以下是基于邻接表的有向图和无向图的DFS和BFS操作的Python实现:
```python
from collections import defaultdict, deque
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def add_edge(self, u, v):
self.graph[u].append(v)
if not self.directed:
self.graph[v].append(u)
def dfs(self, start):
visited = set()
self.dfs_util(start, visited)
def dfs_util(self, vertex, visited):
visited.add(vertex)
print(vertex, end=' ')
for neighbor in self.graph[vertex]:
if neighbor not in visited:
self.dfs_util(neighbor, visited)
def bfs(self, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in self.graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 示例
g = Graph(directed=True)
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)
print("DFS traversal:")
g.dfs(2)
print("\nBFS traversal:")
g.bfs(2)
```
输出结果为:
```
DFS traversal:
2 0 1 3
BFS traversal:
2 0 3 1
```
可以看到,DFS和BFS分别从节点2开始遍历了整个有向图。同样的代码也适用于无向图,只需要将`Graph`构造函数中的`directed`参数设置为`False`即可。