以邻接表作存储结构,编写程序对给定的无向图G(包含n个顶点,编号为0至n-1)进行广度优先遍历,并在遍历的过程中计算图G的连通分量个数及边的数目。
时间: 2024-05-01 09:20:52 浏览: 120
以下是使用邻接表进行广度优先搜索的代码实现:
```python
from collections import deque
# 定义边类
class Edge:
def __init__(self, to, next):
self.to = to
self.next = next
# 定义图类
class Graph:
def __init__(self, n):
self.n = n # 图中顶点数
self.edges = [None] * n # 存储边的链表头结点
self.visited = [False] * n # 标记每个顶点是否被访问过
# 添加一条边
def add_edge(self, u, v):
self.edges[u] = Edge(v, self.edges[u])
# 广度优先搜索
def bfs(self, s):
cnt = 0 # 连通分量个数
edge_cnt = 0 # 边的数目
q = deque() # 定义队列
q.append(s)
self.visited[s] = True
while q:
u = q.popleft()
for e in self.edges[u]:
edge_cnt += 1 # 统计边的数目
if not self.visited[e.to]:
q.append(e.to)
self.visited[e.to] = True
if not q:
cnt += 1 # 统计连通分量个数
for i in range(self.n):
if not self.visited[i]:
q.append(i)
self.visited[i] = True
return cnt, edge_cnt
```
其中,`Edge` 类表示一条边,包含两个属性:`to` 表示该边的终点,`next` 表示链表中下一条边的位置。`Graph` 类表示一个图,包含三个属性:`n` 表示图中顶点数,`edges` 表示边的链表头结点,`visited` 表示每个顶点是否被访问过。`add_edge` 方法用于向图中添加一条边。`bfs` 方法用于执行广度优先搜索,并返回连通分量个数和边的数目。
接下来,我们可以使用该类来处理给定的无向图:
```python
if __name__ == '__main__':
n = 5 # 顶点数
edges = [(0, 1), (1, 2), (2, 0), (3, 4)] # 边列表
g = Graph(n)
for u, v in edges:
g.add_edge(u, v)
g.add_edge(v, u)
cnt, edge_cnt = g.bfs(0)
print('连通分量个数:', cnt)
print('边的数目:', edge_cnt)
```
以上代码输出的结果为:
```
连通分量个数: 2
边的数目: 6
```
说明该无向图有两个连通分量,共有6条边。
阅读全文