输入数据为多组,每组数据包含多行,第一行为2个整数n,e,n为图的顶点数,e为边数,接下来是e行,每行3个整数,前两个整数是一个顶点对,代表一条边所依附的两个顶点,第3个整数是边的权值。 所有值不超过20。请使用prim算法生成一棵生成树(从顶点1出发,权值相同时从编号较小的顶点开始扩展),并输出为生成树的各条边及其权值。
时间: 2024-03-14 14:47:16 浏览: 20
好的,这是一个经典的最小生成树问题,prim算法可以解决这个问题。以下是示例代码:
```python
import heapq
while True:
try:
# 读入数据
n, e = map(int, input().split())
edges = [[] for _ in range(n)] # 存储图的边信息
for _ in range(e):
u, v, w = map(int, input().split())
edges[u-1].append((v-1, w))
edges[v-1].append((u-1, w))
# prim算法
heap = [(0, 0)] # (权值, 顶点编号)
visited = set() # 已经访问过的顶点
tree = [] # 存储生成树的边信息
while heap:
w, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
if u != 0:
tree.append((min(u+1, w+1), max(u+1, w+1), w))
for v, w in edges[u]:
if v not in visited:
heapq.heappush(heap, (w, v))
# 输出结果
for u, v, w in sorted(tree):
print(u, v, w)
except:
break
```
算法的主要思想是维护一个小根堆,堆中存储的是到已访问过的顶点集合的距离最小的未访问过的顶点及其距离。每次从堆中取出距离最小的顶点,将其加入到已访问过的顶点集合中,并将与该顶点相邻的未访问过的顶点加入到堆中。在加入堆的时候,可以将边的信息存储下来,最后输出即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)