实现图的深度优先遍历和广度优先遍历算法。
时间: 2023-09-04 14:15:13 浏览: 127
以下是Python实现的图的深度优先遍历和广度优先遍历算法:
```python
from collections import deque
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_list = {v: [] for v in vertices}
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def dfs(self, start):
visited = set()
self._dfs(start, visited)
def _dfs(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbor in self.adj_list[v]:
if neighbor not in visited:
self._dfs(neighbor, visited)
def bfs(self, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
v = queue.popleft()
print(v, end=' ')
for neighbor in self.adj_list[v]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
```
上述代码中,Graph类表示一个图,使用邻接表来存储图的信息。add_edge方法用于添加边,dfs方法和_bfs方法分别实现深度优先遍历和广度优先遍历。在dfs方法中,使用递归实现深度优先遍历;在bfs方法中,使用队列实现广度优先遍历。
阅读全文