背景：
描述：为促进全球更好互联互通，亚投行拟在一带一路沿线国家建设高铁运输网，请查阅相关资料
画出沿线国家首都或某些代表性城市的连通图，为其设计长度最短或造价最低的高铁建设方案。 要求：抽象出的图中顶点不少于10个，边不少于15条，边的权值代表各国家城市间的高铁长度或造价（假设1公里高铁的造价为人民币1亿元）
操作提示：：
（1）抽象出无向网：画出代表各个国家城市名、城市之间连通线路及其造价的无向网； （2）输入初始数据：首先从终端分别输入顶点及边的总数，然后输入各顶点名（各个国家城市的名 称），再输入顶点之间的连通线路及其权值(相关城市名、长度或造价），建立无线网（建议：为节省
输入时间和测试数据准确性，采用读入文本文件的方式输入原始数据）；
(3）求解最小生成树：利用普里姆（Prim）算法或克鲁斯卡尔(Kruskal)算法求解连通图的最小生
成树; （4）输出最小生成树：以<城市名1，城市名2,长度或造价>方式依次输出连通所有城市的高铁网最短长度或最低造价的建设方案。
界面展示：
我们使用下图标出地点进行模拟
过程分析：
-
最小生成树简介 最小生成树是一张连通图的所有顶点构成的树，它包含了图中所有顶点，并且边的权值之和最小。最小生成树的一个重要性质是它不包含任何形成环路的边，因此可以保证生成树的连通性。
-
Prim算法原理 Prim算法采用贪心策略，从一个起始顶点开始，逐步扩展生成树，直到所有顶点都被加入。其基本思想是每次选择一个与当前已选中的顶点集合相邻且权值最小的边，将其加入生成树中。具体步骤如下：
- 任选一个起始顶点，将其加入生成树中。
- 找到与生成树中的顶点相邻的所有边，并筛选出其中权值最小的边。
- 将上一步中找到的边所连接的顶点加入生成树中。
- 重复第2步和第3步，直到所有顶点都被加入。
-
Prim算法实例演示 以一个简单的图为例，我们来演示Prim算法的执行过程。假设有如下图所示的带权无向连通图：
-
从顶点A开始，我们将它加入生成树。然后选取与A相邻且权值最小的边(AB权值为5)，将顶点B加入生成树。继续选择与生成树相邻且权值最小的边(CA权值为7)，将顶点C加入生成树。接着选择CD边(权值为2)，将顶点D加入生成树。最后选择DE边(权值为4)，将顶点E加入生成树。此时所有顶点都已经加入，生成树构建完毕。
5.Prim算法的适用性和效率分析 Prim算法适用于解决稠密图的最小生成树问题，因为其时间复杂度为O(n^2)，其中n为顶点数。在稠密图中，顶点之间的边比较多，因此Prim算法相对高效。而对于稀疏图，Kruskal算法可能更加适用，因为Kruskal算法的时间复杂度为O(eloge)，其中e为边数。在实际应用中，可以根据具体问题的特点选择合适的算法。
总结：
Prim算法是一种常用的贪心算法，用于求解最小生成树问题。通过选择与当前已选中的顶点集合相邻且权值最小的边，逐步扩展生成树，并保证生成树的连通性和权值最小。希望本文能够帮助读者更好地理解和运用Prim算法，解决实际问题中的最小生成树需求。
源码获取：
void Prim(MGraph g,int v) { //传入一个邻接矩阵，和起始顶点
int lowcost[MAXV];
int closest[MAXV];
int min;
int i,j,k = 0;
for (i=0; i<g.n; i++) { //给lowcost[]和closest[]置初值
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
inMST[u] = true;
for (int v = 0; v < V; v++) {
if (adjMatrix[u][v] != INF && !inMST[v] && adjMatrix[u][v] < key[v]) {
key[v] = adjMatrix[u][v];
pq.push(make_pair(key[v], v));
parent[v] = u;
}
}
