有向图邻接表的广度优先搜索与深度优先遍历完整代码
时间: 2023-06-21 17:20:13 浏览: 68
好的,下面是有向图邻接表的广度优先搜索和深度优先遍历的完整代码:
```python
from collections import deque
class Graph:
def __init__(self, n):
self.adj_list = [[] for _ in range(n)]
self.n = n
def add_edge(self, u, v):
self.adj_list[u].append(v)
def bfs(self, start):
visited = [False] * self.n
q = deque()
q.append(start)
visited[start] = True
while q:
v = q.popleft()
print(v, end=' ')
for u in self.adj_list[v]:
if not visited[u]:
q.append(u)
visited[u] = True
def dfs(self, v, visited):
visited[v] = True
print(v, end=' ')
for u in self.adj_list[v]:
if not visited[u]:
self.dfs(u, visited)
def dfs_traversal(self):
visited = [False] * self.n
for v in range(self.n):
if not visited[v]:
self.dfs(v, visited)
```
其中,Graph 类表示一个有向图,构造函数需要传入顶点的数量 n。add_edge 方法用于添加一条从顶点 u 到顶点 v 的有向边。bfs 方法实现了广度优先搜索,dfs 方法实现了深度优先遍历,dfs_traversal 方法用于遍历整个图。在 dfs 方法中,visited 列表用于记录每个顶点是否被访问过,v 表示当前访问的顶点。在 dfs_traversal 方法中,首先初始化 visited 列表,然后从每个未被访问过的顶点开始执行 dfs。