以邻接表作存储结构,编写程序对给定的无向图G(包含n个顶点,编号为0至n-1)进行广度优先遍历,并在遍历的过程中计算图G的连通分量个数及边的数目。 本题限定在遍历过程中,如果同时出现多个待访问的顶点,则优先选择编号最小的一个进行访问,以顶点0为遍历起点。
时间: 2023-06-13 14:04:35 浏览: 215
以下是基于邻接表的广度优先遍历算法的Python实现:
```python
from queue import Queue
def bfs(adj_list):
n = len(adj_list)
visited = [False] * n
components = 0
edges = 0
q = Queue()
q.put(0)
visited[0] = True
components += 1
while not q.empty():
u = q.get()
for v in adj_list[u]:
edges += 1
if not visited[v]:
q.put(v)
visited[v] = True
components += 1
return components, edges // 2
```
其中,adj_list是邻接表,表示图G的每个顶点的邻居。visited记录每个顶点是否已经被访问过。components表示图G的连通分量个数,初始化为1,因为我们从顶点0开始遍历。edges表示图G的边的数目,每次访问一个顶点的邻居时,都将edges加1,最后要除以2,因为每条边都被算了两次。
代码中,我们使用了Python自带的队列Queue来实现广度优先遍历。我们首先将顶点0加入队列,并将visited[0]设为True,表示已经访问过。然后进入while循环,每次从队列中取出一个顶点u,遍历它的邻居v。如果v还没有被访问过,就将v加入队列,并将visited[v]设为True。此外,每次访问一个顶点的邻居时,都将edges加1。最后返回components和edges // 2即可。
完整代码:
阅读全文