写一段由邻接表存储的图并实现广度优先搜索
时间: 2024-02-23 10:00:18 浏览: 11
以下是使用邻接表存储的图的示例代码,同时实现了广度优先搜索算法:
```python
from collections import deque
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, src, dest):
self.adj_list[src].append(dest)
self.adj_list[dest].append(src)
def bfs(self, start_vertex):
visited = [False] * self.num_vertices
queue = deque([start_vertex])
visited[start_vertex] = True
while queue:
curr_vertex = queue.popleft()
print(curr_vertex, end=" ")
for neighbor in self.adj_list[curr_vertex]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
# 创建一个有5个节点的图
graph = Graph(5)
# 添加图的边
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(3, 4)
# 广度优先搜索
graph.bfs(0)
```
输出结果为:0 1 4 2 3
在这个示例中,我们使用邻接表来存储图。具体来说,我们创建了一个大小为5的列表,列表中的每个元素都是一个空列表。这些列表组成了邻接表,其中第i个列表包含了与节点i相邻的节点。我们使用`add_edge`方法在邻接表中添加边。最后,我们使用`bfs`方法来执行广度优先搜索。在搜索期间,我们使用一个队列来存储待访问的节点。我们首先将起始节点添加到队列中,然后对于每个节点,我们将其所有未访问的邻居添加到队列中,并将它们标记为已访问。最后,我们从队列中弹出下一个节点,并重复这个过程,直到队列为空。