普里姆算法程序讲解,设有无向图g,要求给出用普里姆算法

w；for(i1；一、什么是Pliem 算法一种最小生成树算法？具体流程请参考数据结构书。为了帮助你更好的理解这个算法，Prim算法:是一个图的最小生成树的构造算法，最著名的有prim 算法和kruskal 算法，什么是Prim 算法？许多算法被设计，并且在随后的算法实现中。

如果要建立n个城市之间的通信网络，只需要架设n1条线路。如何以最低的经济成本构建这个通信网络，就是一个网络的最小生成树问题。(1)建立一个图，其存储方式可以是邻接矩阵的形式。需要定义两个数组，一个存储顶点，一个存储边，存储边的数组表示节点之间的连通性和边的权重；(2)用普里 M 算法和Kruskar 算法求网络的最小生成树；(3)依次输出生成树中的边及其权重。

在我们正式讲解Prime和Kruskal 算法之前，我们需要了解什么是最小生成树，在了解最小生成树的概念之前，我们先介绍一些名词。连通图:在一个无向图中，如果任意两个顶点和之间至少有一条路，这个无向图称为连通图。生成树:如果连通图连通子图包含图中的所有顶点，且任意两个顶点之间只有一条路，则该连通子图称为连通图的生成树；最小生成树:在连通图的所有生成树中，边的权重之和最小的生成树称为最小生成树。

假设有一个连通图，其中所有的顶点集都是，集合表示已经添加到生成树中的顶点集，集合表示还没有添加到生成树中的顶点集。首先，随机分配一个顶点添加到集合中。然后，从由该集合和该集合的顶点形成的所有边中选择具有最小权重的边作为生成树的边，并且将该集合的该顶点处的边添加到该集合中，以此类推，直到该集合中的所有顶点都添加到该集合中，以获得最小生成树。

prim 算法最小生成树是图在数据结构中的一个重要应用。它的要求是从一个带权的无向完全图中选择n-1条边，并使该图仍然连通(即得到一棵生成树)，同时使树的权值最小。为了得到最小生成树，人们设计了很多算法，最著名的有prim 算法和kruskal 算法。教材里有介绍Prim 算法，但不够详细，无法理解。为了帮助您更好地理解这一点算法，

希望能帮到大家。假设V是图中顶点的集合，E是图中边的集合，TE是最小生成树中边的集合，那么prim 算法可以通过以下步骤得到最小生成树:1 .初始化:u {u0}，te {}。在该步骤中，将仅具有节点u0和空边集TE的节点集U设置为最小生成树的初始行状态，并且该行状态将在算法的后续执行中不断变化，直到获得最小生成树。

1)普里M算法Idea从图中随机取一个顶点，将其视为一棵树，然后从与这棵树相连的边中选择最短的边(权重最小)，将这条边及其相连的顶点合并到这棵树中，此时就得到一棵有两个顶点的树。然后从与这棵树相连的边中选择最短的边，将这条边及其相连的顶点合并到当前树中，得到一棵有三个顶点的树。依此类推，直到图中的所有顶点都合并到树中，得到的生成树就是最小生成树。

重复该过程，直到检测到所有边缘。需要注意的是，Kruskar 算法需要使用并集来判断接下来要合并的边是否会与合并后的边形成环。普里 m和Kruskar生成的最小生成树如图所示。需要注意的是，当接下来要合并的最小权重不唯一时，可以选择的边也不唯一，所以最小生成树也不唯一。(纯手，望采纳，谢谢。

在具有n个顶点的连通图中选择n1条边组成最小连通子图，使连通子图中n1条边的权之和最小，称为连通网络的最小生成树。例如，对于上图中的连接网络，可以有多个不同权重的生成树。Kruskal 算法用于求加权连通图的最小生成树算法。基本思路:按照权重从小到大的顺序选择n1条边，保证这n1条边不形成环。

以G4为例(详见算法 Introduction p367)，演示Kruskal(假设最小生成树结果由数组R保存)。第一步:在r上加一条边，这条边的权重最小，所以加到最小生成树结果r上第二步:在r上加这条边，经过前面的运算，这条边的权重最小，所以加到最小生成树结果r上第三步:把这条。