6-14 最小生成树（普里姆算法）pta

### 关于最小生成树普里姆算法的PTA题目解析

#### 一、题目描述
假设在一个无向图中有多个城市，每两个相邻的城市之间有一条道路连接，并且道路上有修建成本。现在要在这几个城市间建立通信网络，使得任意两座城市都能通过这些道路互相到达，同时使总建设费用最低。

#### 二、解决方案——普里姆算法实现
对于上述问题可以采用普里姆算法来求解最小生成树，从而得到最优方案。该方法的核心是从任选的一个起点出发，逐步加入最近邻接节点直到覆盖所有顶点为止[^1]。

import heapq

def prim_algorithm(graph, start_vertex):
    mst = []
    total_weight = 0
    
    visited = set([start_vertex])
    
    edges = [(weight, start_vertex, to) for to, weight in graph[start_vertex].items()]
    heapq.heapify(edges)

    while edges:
        (weight, from_vertex, to_vertex) = heapq.heappop(edges)
        
        if to_vertex not in visited:
            visited.add(to_vertex)
            
            mst.append((from_vertex, to_vertex, weight))
            total_weight += weight
            
            for next_to, next_weight in graph[to_vertex].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_weight ,to_vertex, next_to))

    return mst, total_weight

此段代码实现了基于优先队列优化版本的普里姆算法，在处理稀疏图时效率更高。给定一个表示各城市间路径及其权重关系的数据结构`graph`以及起始位置`start_vertex`作为输入参数，函数返回构建完成后的最小生成树边列表和总的权值之和[^2]。

#### 三、具体实例分析
考虑如下简单案例：

| 城市 | A | B | C |
|------|-------|--------|---------|
| **A**| - | 7 | 5 |
| **B**| 7 | - | 8 |
| **C**| 5 | 8 | - |

从表格可以看出这是一个完全图，其中包含了三个城市的相互距离信息。应用上面提到的方法计算得出的结果应当是选择AC这条最短路加上AB构成整个系统的最小花费路线。