使用邻接表建立图,并实现BFS,DFS
时间: 2023-12-18 09:07:18 浏览: 24
邻接表是一种图的表示方法,它使用一个数组存储所有顶点,每个顶点对应一个链表,链表中存储该顶点的所有邻接点。使用邻接表可以有效地存储稀疏图。
下面是使用邻接表建立图的代码:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, u, v):
# 添加无向边
self.adj_list[u].append(v)
self.adj_list[v].append(u)
```
上面的代码定义了一个`Graph`类,它有两个属性:`num_vertices`表示图中顶点的数量,`adj_list`是邻接表,是一个长度为`num_vertices`的列表,每个元素是一个列表,表示该顶点的所有邻接点。
`add_edge`方法用于添加无向边,它将边的两个端点分别添加到彼此的邻接列表中。
接下来是BFS和DFS的实现:
```python
from collections import deque
def bfs(graph, start):
visited = [False] * graph.num_vertices
queue = deque([start])
visited[start] = True
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in graph.adj_list[vertex]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
def dfs(graph, start):
visited = [False] * graph.num_vertices
stack = [start]
while stack:
vertex = stack.pop()
if not visited[vertex]:
visited[vertex] = True
print(vertex, end=' ')
for neighbor in graph.adj_list[vertex]:
stack.append(neighbor)
```
`bfs`方法使用队列实现广度优先遍历,从起点开始遍历,将其加入队列,然后依次取出队列中的元素,访问其邻接点,将未访问的邻接点加入队列。使用`visited`数组记录每个顶点是否被访问过,避免重复访问。
`dfs`方法使用栈实现深度优先遍历,从起点开始遍历,将其加入栈,然后依次取出栈顶元素,访问其邻接点,将未访问的邻接点加入栈。同样使用`visited`数组记录每个顶点是否被访问过。
可以通过以下方式测试上述代码:
```python
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(2, 4)
print('BFS:')
bfs(g, 0)
print()
print('DFS:')
dfs(g, 0)
print()
```
输出结果如下:
```
BFS:
0 1 2 3 4
DFS:
0 2 4 3 1
```