图的深度广度遍历和最小生成树PRIM和KRUSCAL算法的实现

求无向图的最小生成树算法——Prim与Kruskal一.Prim算法1.算法思想对于图G=(V,E)，用Prim算法求最小生成树T=(S,TE)的流程如下① 初始化：设S、TE为空集，任选节点K加入S。

② 选取一条权值最小的边（X,Y），其中X∈S，且not (Y∈S）即，选取一条权值最小的、连接着S中一点与S外一点的边。

将Y加入S中，边（X，Y）加入TE中重复② 直到V=S即所有G中的点都在S中，此时的T为G的最小生成树。

由此流程可见，Prim算法求最小生成树时任何时候的T都是一颗树。

2.实现显然，Prim算法的主要运行时间花在过程②的选边中。

看起来复杂度是O(VE)=O(V^3)不是么，效率也太低了吧……为了比较快速地选边，我们用两个数组lowcost、closest动态地维护每一个点到S的最短距离。

在某一状态下，lowcost[i]表示所有与i相连且另一端点在S中的边中的权值最小值，closest[i]表示在S中且与i相连的点中与i之间距离最小的点。

显然，lowcost[i]=w(i,closest[i])。

需要注意的是两个数组记录的都是边而不是路径。

若i没有边直接连向S，则lowcost[i]=∞。

另外，若i已在S 中，则lowcost[i]=0。

设出发点为x。

初始时对于任意k∈V，closest[k]=x，lowcost[k]=w（k,x）【w（i，j）表示i、j间的距离。

初始化时，若两点间没有边则w（i，j）赋为一个足够大的整数（如maxint），并且所有点到自身的距离赋为0，即w（i，i）=0】每一次找出lowcost中不为0的最小值lowcost[i]，然后把i加入S（即lowcost[i]:=0），然后对于图中所有点k，若w(k,i)<lowcost[k]，则把lowcost[k]赋为w(k,i)，把closest[k]赋为i。

【由于s中所有点的lowcost都为0，所以只影响到s以外的点】以上操作重复|V|-1次结束。

最⼩⽣成树问题---Prim算法与Kruskal算法实现（MATLAB语⾔实现） 2015-12-17晚，复习，甚是⽆聊，阅《复杂⽹络算法与应⽤》⼀书，得知最⼩⽣成树问题（Minimum spanning tree）问题。

记之。

何为树：连通且不含圈的图称为树。

图T=(V,E),|V|=n,|E|=m,下列关于树的说法等价：T是⼀个树。

T⽆圈，且m=n-1。

T连通，且m=n-1。

T⽆圈，但每加⼀新边记得到唯⼀⼀个圈。

T连通，但任舍去⼀边就不连通。

T中任意两点，有唯⼀道路相连。

何为⽣成树：若图G=(V,E)的⽣成⼦图是⼀棵树，则称该树为图G的⽣成树，也称⽀撑树，简称为图G的数。

图G中属于⽣成树的边称为数枝（Branch）。

何为最⼩⽣成树：连通图G=(V,E),每条边上有⾮负权L(e)。

⼀棵树上所有树枝权的总和，称为这个⽣成树的权。

具有最⼩权的⽣成树称为最⼩⽣成树，也就是说最⼩⽀撑树，简称最⼩树。

私以为，两种算法其实都是贪⼼，所以需要严格的证明。

由于最近时间零散、数学久置未学、对算法领域没有系统了解。

所以不进⾏深⼊探讨（也就是说证明），仅以⼀个简单实例做⼀个⼊门级的了解。

Prim算法： 给定连通赋权图G=(V,E,W)，其中W为邻接矩阵，设两个集合P和Q，其中P⽤于存放G的最⼩⽣成树中的节点，集合Q存放G的最⼩G的最⼩⽣成树中的边。

另集合P的初值为P={v1}(假设构造最⼩⽣成树时从v1出发)，集合Q的初值为P={空集}。

（1）P = {v1},Q = {空集}； （2）while P ~= Q 找到最⼩边pv,其中p∈P,v∈V-P; P = P + {v}; Q = Q + {pv}; end Kruskal算法 （1）选e1∈E(G)，使得w(e1) = min（选e1的权值最⼩）。

（2）e1,e2,...,e i已选好，则从E(G)-{e1,e2,...,e i}中选取e i+1,使得G[{e1,e2,...,e i,e i+1}]中⽆圈，且，w(e i+1) = min。

的最小生成树算法Prim与Kruskal算法的比较Prim算法和Kruskal算法都是常用的最小生成树算法，它们可以在给定的加权连通图中找到连接所有节点的最小权重边集合。

然而，这两种算法在实现细节和时间复杂度上有所不同。

本文将对Prim算法和Kruskal算法进行比较，并讨论它们的优缺点以及适用场景。

一、Prim算法Prim算法是一种贪心算法，它从一个起始节点开始，逐步扩展最小生成树的边集合，直到包含所有节点为止。

具体步骤如下：1. 选取一个起始节点作为最小生成树的根节点。

2. 在最小生成树的边集合中寻找与当前树集合相连的最小权重边，并将这条边添加到最小生成树中。

3. 将新添加的节点加入到树集合中。

4. 重复步骤2和3，直到最小生成树包含所有节点为止。

Prim算法的时间复杂度为O(V^2)，其中V是节点的个数。

这是因为在每轮迭代中，需要从树集合以外的节点中找到与树集合相连的最小权重边，而在最坏情况下，可能需要检查所有的边。

二、Kruskal算法Kruskal算法是一种基于边的贪心算法，它按照边的权重从小到大的顺序依次选择边，并判断是否加入最小生成树中。

具体步骤如下：1. 初始化一个空的最小生成树。

2. 将所有边按照权重从小到大进行排序。

3. 依次检查每条边，如果这条边连接了两个不同的树（即不会形成环），则将这条边加入到最小生成树中。

4. 重复步骤3，直到最小生成树包含所有节点为止。

Kruskal算法使用并查集数据结构来快速判断连通性，时间复杂度为O(ElogE)，其中E是边的个数。

排序边的时间复杂度为O(ElogE)，而对每条边进行判断和合并操作的时间复杂度为O(E)。

三、比较与总结1. 时间复杂度：Prim算法的时间复杂度为O(V^2)，而Kruskal算法的时间复杂度为O(ElogE)。

因此，在边的数量较大的情况下，Kruskal 算法的效率优于Prim算法。

2. 空间复杂度：Prim算法需要维护一个大小为V的优先队列和一个大小为V的布尔数组，而Kruskal算法需要维护一个大小为V的并查集。

最⼩⽣成树的Prim算法以及Kruskal算法的证明Prime算法的思路：从任何⼀个顶点开始，将这个顶点作为最⼩⽣成树的⼦树，通过逐步为该⼦树添加边直到所有的顶点都在树中为⽌。

其中添加边的策略是每次选择外界到该⼦树的最短的边添加到树中（前提是⽆回路）。

Prime算法的正确性证明：引理1：对于连通图中的顶点vi，与它相连的所有边中的最短边⼀定是属于最⼩⽣成树的。

引理2：证明：假设最⼩⽣成树已经建成；(vi, vj)是连接到顶点vi的最短边，在最⼩⽣成树中取出vi，断开连接到vi的边，则⽣成树被拆分成1、顶点vi2、顶点vj所在的连通分量（单独⼀个顶点也看作⼀个独⽴的连通分量）3、其余若⼲个连通分量（个数⼤于等于0）三个部分现在要重建⽣成树，就要重新连接之前被断开的各边虽然不知道之前被断开的都是哪⼏条边，但是可以通过这样⼀个简单的策略来重建连接：将vi分别以最⼩的成本逐个连接到这若⼲个互相分离的连通分量；具体来说，就是要分别遍历顶点vi到某个连通分量中的所有顶点的连接，然后选择其中最短的边来连接vi和该连通分量；⽽要将vi连接到vj所在的连通分量，显然通过边(vi, vj)连接的成本最低，所以边(vi, vj)必然属于最⼩⽣成树（如果连接到vi的最短边不⽌⼀条，只要任意挑选其中的⼀条(vi, vj)即可，以上的证明对于这种情况同样适⽤）。

这样我们就为原来只有⼀个顶点vi的⼦树添加了⼀个新的顶点vj及新边(vi, vj)；接下来只要将这棵新⼦树作为⼀个连通⼦图，并且⽤这个连通⼦图替换顶点vi重复以上的分析，迭代地为⼦树逐个地添加新顶点和新边即可。

Kruskal算法：通过从⼩到⼤遍历边集，每次尝试为最⼩⽣成树加⼊当前最短的边，加⼊成功的条件是该边不会在当前已构建的图中造成回路，当加⼊的边的数⽬达到n-1，遍历结束。

Kruskal算法的正确性证明：Kruskal算法每次为当前的图添加⼀条不会造成回路的新边，其本质是逐步地连接当前彼此分散的各个连通分量（单个顶点也算作⼀个连通分量），⽽连接的策略是每次只⽤最⼩的成本连接任意两个连通分量。

采用普里姆算法和克鲁斯卡尔算法,求最小生成树-回复普里姆算法和克鲁斯卡尔算法是求解最小生成树问题的两种重要方法。

本文将详细介绍这两种算法的原理和步骤，并比较它们的优缺点和适用场景。

一、普里姆算法普里姆算法（Prim's Algorithm）是一种贪心算法，用于求解带权无向连通图的最小生成树。

它的基本思想是从一个起始顶点开始，逐步向最小代价的边添加顶点，直到生成一颗包含所有顶点的最小生成树。

下面是普里姆算法的具体步骤：1. 随机选择一个顶点作为起始顶点，并将其添加到最小生成树集合中。

2. 从最小生成树集合中已有的顶点出发，寻找与其相连的边中具有最小权值的顶点，将该顶点添加到最小生成树集合中。

3. 重复第二步，直到最小生成树集合包含所有顶点为止。

普里姆算法的时间复杂度为O(V^2)，其中V为顶点数。

它的优点是简单易懂、容易实现，并且适用于稠密图。

然而，普里姆算法对于稀疏图的效率较低，因为需要频繁地搜索和更新权值最小的边。

二、克鲁斯卡尔算法克鲁斯卡尔算法（Kruskal's Algorithm）是一种基于边的贪心算法，用于求解带权无向连通图的最小生成树。

它的基本思想是通过选择代价最小的边，并判断是否会形成环路，最终构建出一颗最小生成树。

下面是克鲁斯卡尔算法的具体步骤：1. 将图中的所有边按照权值从小到大进行排序。

2. 依次选择权值最小的边，判断如果添加该边会形成环路，则将其舍弃；否则将其添加到最小生成树的边集合中。

3. 重复第二步，直到最小生成树的边数等于顶点数减一为止。

克鲁斯卡尔算法的时间复杂度为O(ElogE)，其中E为边数。

相比普里姆算法，克鲁斯卡尔算法适用于稀疏图，并且对于大规模图的求解效率更高。

然而，克鲁斯卡尔算法的缺点是在构建最小生成树时需要尝试的边较多，因此在边数较多的情况下，算法的效率可能不高。

三、比较与总结普里姆算法和克鲁斯卡尔算法都是求解最小生成树问题的经典算法，它们各自具有不同的优点和适用场景。

最⼩⽣成树---普⾥姆算法（Prim算法）和克鲁斯卡尔算法（Kruskal算法）最⼩⽣成树的性质：MST性质（假设N=(V,{E})是⼀个连通⽹，U是顶点集V的⼀个⾮空⼦集，如果（u，v）是⼀条具有最⼩权值的边，其中u属于U，v属于V-U，则必定存在⼀颗包含边（u，v）的最⼩⽣成树）普⾥姆算法（Prim算法)思路：以点为⽬标构建最⼩⽣成树1.将初始点顶点u加⼊U中，初始化集合V-U中各顶点到初始顶点u的权值；2.根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩。

循环n-1次如下操作：（1）从数组lowcost[k]中找到vk到集合U的最⼩权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标(2)打印此边，并将vk加⼊U中。

（3）通过查找邻接矩阵Vk⾏的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中以下图为例#include<bits/stdc++.h>using namespace std;#define MAXVEX 100#define INF 65535typedef char VertexType;typedef int EdgeType;typedef struct {VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numVertexes, numEdges;}MGraph;void CreateMGraph(MGraph *G) {int m, n, w; //vm-vn的权重wscanf("%d %d", &G->numVertexes, &G->numEdges);for(int i = 0; i < G->numVertexes; i++) {getchar();scanf("%c", &G->vexs[i]);}for(int i = 0; i < G->numVertexes; i++) {for(int j = 0; j < G->numVertexes; j++) {if(i == j) G->arc[i][j] = 0;else G->arc[i][j] = INF;}}for(int k = 0; k < G->numEdges; k++) {scanf("%d %d %d", &m, &n, &w);G->arc[m][n] = w;G->arc[n][m] = G->arc[m][n];}}void MiniSpanTree_Prim(MGraph G) {int min, j, k;int arjvex[MAXVEX]; //最⼩边在 U集合中的那个顶点的下标int lowcost[MAXVEX]; // 最⼩边上的权值//初始化,从点 V0开始找最⼩⽣成树Tarjvex[0] = 0; //arjvex[i] = j表⽰ V-U中集合中的 Vi点的最⼩边在U集合中的点为 Vjlowcost[0] = 0; //lowcost[i] = 0表⽰将点Vi纳⼊集合 U ，lowcost[i] = w表⽰ V-U中 Vi点到 U的最⼩权值for(int i = 1; i < G.numVertexes; i++) {lowcost[i] = G.arc[0][i];arjvex[i] = 0;}//根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩for(int i = 1; i < G.numVertexes; i++) {min = INF, j = 1, k = 0;//寻找 V-U到 U的最⼩权值minfor(j; j < G.numVertexes; j++) {// lowcost[j] != 0保证顶点在 V-U中，⽤k记录此时的最⼩权值边在 V-U中顶点的下标if(lowcost[j] != 0 && lowcost[j] < min) {min = lowcost[j];k = j;}}}printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min);lowcost[k] = 0; //表⽰将Vk纳⼊ U//查找邻接矩阵Vk⾏的各个权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中for(int i = 1; i < G.numVertexes; i++) {if(lowcost[i] != 0 && G.arc[k][i] < lowcost[i]) {lowcost[i] = G.arc[k][i];arjvex[i] = k;}}}int main() {MGraph *G = (MGraph *)malloc(sizeof(MGraph));CreateMGraph(G);MiniSpanTree_Prim(*G);}/*input:4 5abcd0 1 20 2 20 3 71 2 42 3 8output:V[0]-V[1] weight = 2V[0]-V[2] weight = 2V[0]-V[3] weight = 7最⼩总权值: 11*/时间复杂度O(n^2)克鲁斯卡尔算法（Kruskal算法）思路：以边为⽬标进⾏构建最⼩⽣成树在边集中依次寻找最⼩权值边，若构建是不形成环路（利⽤parent数组记录各点的连通分量），则将其添加到最⼩⽣成树中。

采用普里姆算法和克鲁斯卡尔算法,求最小生成树什么是最小生成树？最小生成树是图论中的一个重要概念，它是指在一个给定的无向连通图中，找到一棵树，使得这棵树连接图中的所有顶点，并且具有最小的权值总和。

最小生成树在很多实际问题中有着广泛的应用，比如城市规划、电力网络规划等。

普里姆算法：普里姆算法又称为“加点法”，它从一个初始随机点开始，逐渐往图中加入新的点，直到能够生成一棵包含所有节点的最小生成树。

1. 首先选择一个任意节点作为起始节点，加入最小生成树中。

2. 从已经加入最小生成树的节点中，选择一个与之相邻的节点并且不在最小生成树中的边，找到权值最小的边，将其加入最小生成树。

3. 重复第二步，直到最小生成树包含了所有的节点，即生成了一棵最小生成树。

克鲁斯卡尔算法：克鲁斯卡尔算法又称为“加边法”，它从原图的边集中选择权值最小的边，逐步加入生成树的边集中，直到遍历完所有的边，同时生成一棵最小生成树。

1. 首先把图中的所有边按照权值从小到大进行排序。

2. 依次遍历排序后的边，判断每一条边的两个顶点是否属于同一个连通分量。

3. 如果不属于同一个连通分量，将该边加入最小生成树的边集中，并将两个顶点所在的连通分量合并。

4. 重复第二步和第三步，直到遍历完所有的边或者最小生成树的边数达到图中节点数减一。

两种算法的比较：普里姆算法是从一个初始点开始，每次加入一个与最小生成树相连的具有最小权值的点，直到生成一棵最小生成树。

这种算法的时间复杂度为O(V^2)，其中V表示图中的顶点数。

因此，普里姆算法适用于顶点数较少的情况。

克鲁斯卡尔算法是将边按照权值排序后逐步加入最小生成树的边集中。

这种算法的时间复杂度为O(ElogE)，其中E表示图中的边数。

因此，克鲁斯卡尔算法适用于边数较少的情况。

从时间复杂度的角度来看，克鲁斯卡尔算法在边数较少的情况下更为高效，而普里姆算法在顶点数较少的情况下更为高效。

总结：最小生成树是一个在图论中非常重要且常用的概念，可以用于解决很多实际问题。

的最小生成树算法Prim和Kruskal算法Prim和Kruskal算法是求解最小生成树的两种常用算法。

最小生成树指的是在一个连通图中，找到一棵包含所有顶点的生成树，使得树上边的权重之和最小。

Prim算法基于贪心思想，从一个起始顶点开始，逐步向其他顶点扩展，每次选择权重最小的边连接已经选中的顶点和未选中的顶点。

具体步骤如下：1. 初始化一个空的集合S，用于存放已经选中的顶点。

2. 从图中任选一个顶点作为起始顶点，并将其加入集合S。

3. 重复以下步骤，直到集合S包含了所有顶点：a. 在未加入集合S的顶点中，找到与集合S中顶点相连的边中权重最小的边。

b. 将该边加入生成树中，并将与该边相连的顶点加入集合S。

4. 生成的树即为最小生成树。

Kruskal算法是基于边的权重排序的思想。

具体步骤如下：1. 初始化一个空的集合S，用于存放已经选中的边。

2. 将图中的所有边按照权重从小到大排序。

3. 重复以下步骤，直到生成的树中包含了所有顶点-1条边（其中顶点的数量为n）：a. 从排序后的边列表中选取一条最小权重的边。

b. 若该边的两个顶点不在同一连通分量中，将该边加入生成树中。

c. 否则，舍弃该边，继续选择下一条边。

4. 生成的树即为最小生成树。

值得注意的是，在构建最小生成树时，如果图不是连通图，那么最小生成树就不存在。

Prim算法的时间复杂度为O(V^2)，其中V表示顶点的数量。

在稠密图中效果较好。

而Kruskal算法的时间复杂度为O(ElogE)，其中E表示边的数量。

在稀疏图中效果较好。

这两种算法在实际应用中都有一定的局限性。

Prim算法适合处理边稠密、顶点稀疏的图，而Kruskal算法适合处理边稀疏、顶点稀疏的图。

在选择使用算法时，需要根据具体问题的特点进行权衡。

最小生成树算法Prim和Kruskal算法在图论领域具有重要的地位，广泛应用于网络设计、电路布线、城市规划等领域。

通过构建最小生成树，可以在保证连通性的前提下，选择最经济、最高效的路径和连接方式，节约资源并提高效率。

prim和克鲁斯卡尔算法
Prim算法和Kruskal算法是两类思想完全不同的最小生成树（MST）算法，它们分别具有独特的优缺点。

Prim算法采用贪心策略和建模方法，被认为是一种比较容易实现的方法。

在每一步中，它会选择离已经选择的节点最近的未选择节点作为新的节点，然后根据具体实施情况选择一条最短的边连接这两个节点。

换句话说，Prim算法根据节点之间的距离以局部选择的方式构建最小生成树。

Kruskal算法根据边的权重选择最小生成树，它着重于整体最优，是一种比较复杂但更有效的方法。

它会将所有节点以及它们之间的边按照权重排序，然后每次从最短边中选择一条边，直到所有节点都被连接。

这种算法有时也称作贪心策略，它通过每一步中查找最短边来尽量减少最终最小生成树的总费用。

由于Prim算法主要的重点是局部最优，它比较容易实现，因此是比较常用的一种算法，而Kruskal算法则着重于整体最优，它的实施通常需要非常复杂的算法，但最终的结果更加优秀。

要想确定适合给定特定问题的最佳算法，一般来说，必须对这两种算法进行详细分析，以便选择更有效的算法实施，并确保最小生成树构建的总成本最低。

最⼩⽣成树---Prim算法和Kruskal算法Prim算法1.概览普⾥姆算法（Prim算法），图论中的⼀种算法，可在加权连通图⾥搜索最⼩⽣成树。

意即由此算法搜索到的边⼦集所构成的树中，不但包括了连通图⾥的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最⼩。

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普⾥姆（英语：Robert C. Prim）独⽴发现；1959年，艾兹格·迪科斯彻再次发现了该算法。

因此，在某些场合，普⾥姆算法⼜被称为DJP算法、亚尔尼克算法或普⾥姆－亚尔尼克算法。

2.算法简单描述1).输⼊：⼀个加权连通图，其中顶点集合为V，边集合为E；2).初始化：V new = {x}，其中x为集合V中的任⼀节点（起始点），E new = {},为空；3).重复下列操作，直到V new = V：a.在集合E中选取权值最⼩的边<u, v>，其中u为集合V new中的元素，⽽v不在V new集合当中，并且v∈V（如果存在有多条满⾜前述条件即具有相同权值的边，则可任意选取其中之⼀）；b.将v加⼊集合V new中，将<u, v>边加⼊集合E new中；4).输出：使⽤集合V new和E new来描述所得到的最⼩⽣成树。

⽰例图演⽰:下⾯对算法的图例描述:3.简单证明prim算法反证法：假设prim⽣成的不是最⼩⽣成树1).设prim⽣成的树为G02).假设存在G min使得cost(G min)<cost(G0) 则在G min中存在<u,v>不属于G03).将<u,v>加⼊G0中可得⼀个环，且<u,v>不是该环的最长边(这是因为<u,v>∈G min)4).这与prim每次⽣成最短边⽭盾5).故假设不成⽴，命题得证.Kruskal算法1.概览Kruskal算法是⼀种⽤来寻找最⼩⽣成树的算法，由Joseph Kruskal在1956年发表。

Prim算法和Kruskal算法Prim算法和Kruskal算法都能从连通图找出最小生成树。

区别在于Prim算法是挨个找，而Kruskal是先排序再找。

一、Prim算法：Prim算法实现的是找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。

(强调的是树，树是没有回路的)。

Prim算法是这样来做的：首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。

加入之后如果产生回路则跳过这条边，选择下一个结点。

当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。

Prim算法最小生成树查找过程：注意：若候选轻边集中的轻边不止一条，可任选其中的一条扩充到T中。

连通网的最小生成树不一定是惟一的，但它们的权相等。

【例】在上图(e)中，若选取的轻边是(2，4)而不是(2，1)时，则得到如图(h)所示的另一棵MST。

算法特点该算法的特点是当前形成的集合T始终是一棵树。

将T中U和TE分别看作红点和红边集，V-U看作蓝点集。

算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。

MST性质保证了此边是安全的。

T从任意的根r开始，并逐渐生长直至U=V，即T 包含了C中所有的顶点为止。

MST性质确保此时的T是G的一棵MST。

因为每次添加的边是使树中的权尽可能小，因此这是一种"贪心"的策略。

算法分析该算法的时间复杂度为O(n2)。

与图中边数无关，该算法适合于稠密图。

算法演示：/sjjg/DataStructure/DS/web/flashhtml/prim.htm二、Kruskal算法：Kruskal算法与Prim算法的不同之处在于，Kruskal在找最小生成树结点之前，需要对所有权重边做从小到大排序。

将排序好的权重边依次加入到最小生成树中，如果加入时产生回路就跳过这条边，加入下一条边。

当所有结点都加入到最小生成树中之后，就找出了最小生成树。

/*分别利用prim算法和kruskal算法实现求图的最小生成树*/ #include<stdio.h>#include<stdlib.h>#define MaxVertexNum 12#define MaxEdgeNum 20#define MaxValue 1000typedef int Vertextype;typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; typedef Vertextype vexlist[MaxVertexNum];int visited[MaxVertexNum]={0};struct edgeElem{int fromvex;int endvex;int weight;};typedef struct edgeElem edgeset[MaxVertexNum];void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e) {int i,j,k,w;printf("输入%d个顶点数据",n);for(i=0;i<n;i++)scanf("%d",&GV[i]);for(i=0;i<n;i++)for(j=0;j<n;j++)if(i==j) GA[i][j]=0;else GA[i][j]=MaxValue;printf("输入%d条无向带权边",e);for(k=0;k<e;k++){scanf("%d%d%d",&i,&j,&w);GA[i][j]=GA[j][i]=w;}}void Creat_edgeset(vexlist GV,edgeset GE,int n,int e) {int i,j,k,w;printf("输入%d个顶点数据",n);for(i=0;i<n;i++)scanf("%d",&GV[i]);printf("输入%d条无向带权边",e);for(k=0;k<e;k++){ scanf("%d%d%d",&i,&j,&w);GE[k].fromvex=i;GE[k].endvex=j;GE[k].weight=w;}}void output_edgeset(edgeset GE,int e){int k;for(k=0;k<e;k++)printf("%d %d %d,",GE[k].fromvex,GE[k].endvex,GE[k].weight); printf("\n");}void prim(adjmatrix GA,edgeset CT,int a,int n){int i,j,t,k,w,min,m;struct edgeElem x;for(i=0;i<n;i++)if(i<a){CT[i].fromvex=a;CT[i].endvex=i;CT[i].weight=GA[a][i];}else if(i>a){CT[i-1].fromvex=a;CT[i-1].endvex=i;CT[i-1].weight=GA[a][i];}for(k=1;k<n;k++){min=MaxValue;m=k-1;for(j=k-1;j<n-1;j++)if(CT[j].weight<min){min=CT[j].weight;m=j;}x=CT[k-1];CT[k-1]=CT[m];CT[m]=x;j=CT[k-1].endvex;for(i=k;i<n-1;i++){t=CT[i].endvex;w=GA[j][t];if(w<CT[i].weight){CT[i].weight=w;CT[i].fromvex=j;}}}}void kruskal(edgeset GE,edgeset C,int n){ int i,j,k,d;int m1,m2;adjmatrix s;for(i=0;i<n;i++){for(j=0;j<n;j++)if(i==j) s[i][j]=1;else s[i][j]=0;}k=1;d=0;while(k<n){for(i=0;i<n;i++){if(s[i][GE[d].fromvex]==1) m1=i;if(s[i][GE[d].endvex]==1) m2=i;}if(m1!=m2){C[k-1]=GE[d];k++;for(j=0;j<n;j++){s[m1][j]=s[m1][j]||s[m2][j];s[m2][j]=0;}}d++;}}void main(){int n,e;vexlist GV;adjmatrix GA;edgeset GE,C;printf("输入图的顶点数和边数：");scanf("%d%d",&n,&e);Creat_adjmatrix( GV, GA, n, e);printf("利用prim算法从0点出发求图的最小生成树：\n");prim(GA,GE,0,n);output_edgeset( GE, n-1);printf("输入图的顶点数和边数:");scanf("%d%d",&n,&e);Creat_edgeset( GV,GE,n, e);printf("利用kruskal算法从0点出发求图的最小生成树：\n");kruskal( GE, C, n);output_edgeset( C, n-1);}最小生成树（prim算法和kruskal算法）收藏最小生成树（prim算法）用最小生成树的解决的经典问题：若要在n个城市间建设通信网路，给出任意两个城市的距离和每米通信网路的造价，问怎样设计网络可以使网路的造价最小。

JS使⽤Prim算法和Kruskal算法实现最⼩⽣成树之前都是看书，⼤部分也是c++的实现，但是搞前端不能忘了JS啊，所以JS实现⼀遍这两个经典的最⼩⽣成树算法。

⼀、权重图和最⼩⽣成树权重图：图的边带权重最⼩⽣成树：在连通图的所有⽣成树中，所有边的权重和最⼩的⽣成树本⽂使⽤的图如下：它的最⼩⽣成树如下：⼆、邻接矩阵邻接矩阵：⽤来表⽰图的矩阵就是邻接矩阵，其中下标表⽰顶点，矩阵中的值表⽰边的权重（或者有⽆边，⽅向等）。

本⽂在构建邻接矩阵时，默认Number.MAX_SAFE_INTEGER表⽰两个节点之间没有边，Number.MIN_SAFE_INTEGER表⽰当前节点没有⾃环。

代码如下：/*** 邻接矩阵* 值为顶点与顶点之间边的权值，0表⽰⽆⾃环，⼀个⼤数表⽰⽆边(⽐如10000)* */const MAX_INTEGER = Number.MAX_SAFE_INTEGER;//没有的边const MIN_INTEGER = Number.MIN_SAFE_INTEGER;//没有⾃环const matrix= [[MIN_INTEGER, 9, 2, MAX_INTEGER, 6],[9, MIN_INTEGER, 3, MAX_INTEGER, MAX_INTEGER],[2, 3, MIN_INTEGER, 5, MAX_INTEGER],[MAX_INTEGER, MAX_INTEGER, 5, MIN_INTEGER, 1],[6, MAX_INTEGER, MAX_INTEGER, 1, MIN_INTEGER]];这个邻接矩阵表⽰的图如下：三、边的表⽰⼀个边具有权重、起点、重点三个属性，所以可以创建⼀个类(对象)，实现如下：/*** 边对象* */function Edge(begin, end, weight) {this.begin = begin;this.end = end;this.weight = weight;}Edge.prototype.getBegin = function () {return this.begin;};Edge.prototype.getEnd = function () {return this.end;};Edge.prototype.getWeight = function () {return this.weight;};/*class Edge {constructor(begin, end, weight) {this.begin = begin;this.end = end;this.weight = weight;}getBegin() {return this.begin;}getEnd() {return this.end;}getWeight() {return this.weight;}}*/PS：JS这门语⾔没有私有变量的说法，这⾥写get⽅法纯粹是模拟⼀下私有变量。

java实现最⼩⽣成树的prim算法和kruskal算法在边赋权图中，权值总和最⼩的⽣成树称为最⼩⽣成树。

构造最⼩⽣成树有两种算法，分别是prim算法和kruskal算法。

在边赋权图中，如下图所⽰:在上述赋权图中，可以看到图的顶点编号和顶点之间邻接边的权值，若要以上图来构建最⼩⽣成树。

结果应该如下所⽰:这样构建的最⼩⽣成树的权值总和最⼩，为17在构建最⼩⽣成树中，⼀般有两种算法，prim算法和kruskal算法在prim算法中，通过加⼊最⼩邻接边的⽅法来建⽴最⼩⽣成树算法。

⾸先构造⼀个零图，在选⼀个初始顶点加⼊到新集合中，然后分别在原先的顶点集合中抽取⼀个顶点，使得构成的边为权值最⼩，然后将该笔边加⼊到图中，并将抽出的顶点加⼊到新集合中，重复这个过程，知道新集合等于原先的集合。

代码⼀：（java）1/**2 * 最⼩⽣成树的prim算法3 * @author liuy4*/5public class Prim {67public static void prim(int num, float[][] weight) { //num为顶点数，weight为权8float[] lowcost = new float[num + 1]; //到新集合的最⼩权910int[] closest = new int[num + 1]; //代表与s集合相连的最⼩权边的点1112boolean[] s = new boolean[num + 1]; //s[i] == true代表i点在s集合中1314 s[1] = true; //将第⼀个点放⼊s集合1516for(int i = 2; i <= num; i++) { //初始化辅助数组17 lowcost[i] = weight[1][i];18 closest[i] = 1;19 s[i] = false;20 }2122for(int i = 1; i < num; i++) {23float min = Float.MAX_VALUE;24int j = 1;25for(int k = 2; k <= num; k++) {26if((lowcost[k] < min) && (!s[k])) {//根据最⼩权加⼊新点27 min = lowcost[k];28 j = k;29 }30 }3132 System.out.println("加⼊点" + j + ". " + j + "---" + closest[j]);//新加⼊点的j和与j相连的点3334 s[j] = true;//加⼊新点j3536for(int k = 2; k <= num; k++) {37if((weight[j][k] < lowcost[k]) && !s[k]) {//根据新加⼊的点j,求得最⼩权38 lowcost[k] = weight[j][k];39 closest[k] = j;40 }41 }42 }43 }4445public static void main(String[] args) {46// ①47// / | /48// 6 1 549// / | /50// ②-5--③--5--④51// / // /52// 3 6 4 253//////54// ⑤--6-⑥55//最⼩⽣成树为：56// ①57// |58// 159// |60// ②-5--③④61// / / /62// 3 4 263// / //64// ⑤⑥65//66float m = Float.MAX_VALUE;67float[][] weight = {{0, 0, 0, 0, 0, 0, 0},68 {0, m, 6, 1, 5, m, m},69 {0, 6, m, 5, m, 3, m},70 {0, 1, 5, m, 5, 6, 4},71 {0, 5, m, 5, m, m, 2},72 {0, m, 3, 6, m, m, 6},73 {0, m, m, 4, 2, 6, m}};//上图的矩阵74 prim(weight.length - 1, weight);75//加⼊点3. 3---176//加⼊点6. 6---377//加⼊点4. 4---678//加⼊点2. 2---379//加⼊点5. 5---280 }81 }View Code代码⼆：（java）1package最⼩⽣成树;2/*3 * 最⼩⽣成树prim算法，加⼊最⼩邻接边⽣成最⼩⽣成树。

一、概述在图论中，prim算法和kruskal算法是两种常用的最小生成树算法。

它们分别以不同的方式来寻找给定图的最小生成树，是解决最小生成树问题的有效方法。

本文将重点介绍prim算法和kruskal算法，并通过例题分析，展示它们的应用及原理。

二、prim算法1. prim算法概述2. prim算法步骤3. 例题分析：通过一个具体图示例，展示prim算法的应用过程，详细阐述每一步的操作及思路。

4. prim算法优缺点三、kruskal算法1. kruskal算法概述2. kruskal算法步骤3. 例题分析：通过一个具体图示例，展示kruskal算法的应用过程，详细阐述每一步的操作及思路。

4. kruskal算法优缺点四、prim算法和kruskal算法的比较1. 时间复杂度2. 空间复杂度3. 适用范围4. 其他特点五、例题分析总结通过对两种算法在具体例题中的应用过程分析，总结prim算法和kruskal算法的异同点，以及在实际问题中应用时的考虑因素。

六、结论根据对prim算法和kruskal算法的介绍及例题分析，总结两种算法的特点和应用场景，为不同情况下的最小生成树问题提供参考指导。

七、参考文献列出本文所参考的相关书籍、文献或全球信息站信息，为读者进一步了解prim算法和kruskal算法提供便利。

八、附录可放置示例代码、补充说明或其他相关内容，以便读者更好地理解prim算法和kruskal算法。

由于当前训练模型对于编程题的掌握有一定限制，可以提供在Prim算法和Kruskal算法方面相关的例题解析和应用案例。

以下是一个基于图的例题及其解析。

假设有一个带权重的无向连通图G，图中的顶点集合为V，边的集合为E，每条边的权重由权重函数w(u, v)给出，其中u, v为边的两个顶点。

现在需要使用Prim算法和Kruskal算法来寻找图G的最小生成树。

首先我们需要给出一个具体的图G，如下所示：顶点集合V = {A, B, C, D, E}边的集合E = {(A, B, 3), (A, C, 1), (A, D, 5), (B, C, 4), (B, D, 6), (B, E, 2), (C, D, 7), (C, E, 8), (D, E, 9)}其中，每个元组表示一条边的起始顶点、终止顶点和权重。

Prim算法和Kruskal算法介绍⼀、Prim算法普利姆(Prim)算法适⽤于求解⽆向图中的(Minimum Cost Spanning Tree)。

下⾯是Prim算法构造最⼩⽣成树的过程图解。

选择⼀个节点开始，⽐如V1进⼊集合U，剩下的集合的V-U包括剩下的节点，然后寻找从集合U到集合V-U最近的路径。

这⾥有三条路径分别是权重为6到V2，权重为5到V4以及权重为1到V3，显然到通过V3连接⽽集合U和集合V-U是最近的，选择V3进⼊集合U。

同样继续选择到V-U的路径，此时有6条可选路径，分别是权为6到V2【从V1】，权为5到V4【从V1】，权为5到V2【从V3】，权为5到V4【从V3】，权为6到V5【从V3】，权为4到V6【从V3】。

选择出从V3到V6的路径并将V6添加⾄集合U中。

按照这种⽅法依次将V4，V2和V5添加到集合U直到U和全体节点结合V相等，或者说V-U集合为空时结束，这时选出的n-1条边即为最⼩⽣成树。

⼆、Kruskal算法克鲁斯卡尔(Kruskal)算法是另⼀种求解最⼩⽣成树的算法。

下⾯是Kruskal算法构造最⼩⽣成树的过程图解。

Kruskal则是采取另⼀种思路，即从边⼊⼿。

⾸先n个顶点分别视为n个连通分量，然后选择⼀条权重最⼩的边，如果边的两端分属于两个连通分量，就把这个边加⼊集合E，否则舍去这条边⽽选择下⼀条代价最⼩的边，依次类推，直到所有节点都在同⼀个连通分量上。

三、对⽐假设⽹中有n个节点和e条边，普利姆算法的时间复杂度是O(n^2)，克鲁斯卡尔算法的时间复杂度是O(eloge)，可以看出前者与⽹中的边数⽆关，⽽后者相反。

因此，普利姆算法适⽤于边稠密的⽹络⽽克鲁斯卡尔算法适⽤于求解边稀疏的⽹。

普里姆算法和克鲁斯卡尔算法普里姆算法和克鲁斯卡尔算法介绍在图论中，最小生成树是一种重要的概念。

最小生成树是指在一个加权连通图中，找到一棵生成树，使得所有边的权值之和最小。

其中，Prim算法和Kruskal算法是两种常用的求解最小生成树的方法。

Prim算法Prim算法是一种贪心算法，它从一个顶点开始构建最小生成树。

具体实现过程如下：1. 选取任意一个顶点作为起始点，并将其标记为已访问。

2. 遍历与该顶点相邻的所有边，并将这些边加入一个优先队列中。

3. 从优先队列中选取一条权值最小的边，并将与之相邻的未被访问过的顶点标记为已访问。

4. 重复步骤2和3，直到所有顶点都被访问过。

代码实现```def prim(graph, start):visited = set()visited.add(start)edges = []min_span_tree_cost = 0while len(visited) != len(graph.keys()):candidate_edges = []for node in visited:for edge in graph[node]:if edge[1] not in visited:candidate_edges.append(edge)sorted_edges = sorted(candidate_edges, key=lambda x:x[2]) min_edge = sorted_edges[0]edges.append(min_edge)min_span_tree_cost += min_edge[2]visited.add(min_edge[1])return edges, min_span_tree_cost```时间复杂度Prim算法的时间复杂度为O(ElogV)，其中E为边数，V为顶点数。

因为每次需要从优先队列中选取一条权值最小的边，所以需要使用堆来实现优先队列。

图的深度广度遍历和最小生成树PRIM和KRUSCAL算法的实现昨天上实验课，偶然看到这个程序，和大家一起共享一下.....//图的遍历和生成树求解实现//（邻接矩阵、邻接表—图的深度广度遍历算法的实现和最小生成树PRIM和KRUSCAL算法的实现）#include <iostream>#include <malloc.h>using namespace std;#define int_max 10000#define inf 9999#define max 20//…………………………………………邻接矩阵定义……………………typedef struct ArcCell{int adj;char *info;}ArcCell,AdjMatrix[max][max];typedef struct{char vexs[max];AdjMatrix arcs;int vexnum,arcnum;}MGraph_L;//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^int localvex(MGraph_L G,char v)//返回V的位置{int i=0;while(G.vexs[i]!=v)++i;return i;}int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示{char v1,v2;int i,j,w;cout<<"…………创建无向图…………"<<endl<<"请输入图G顶点和弧的个数:(4 6)不包括“()”"<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i!=G.vexnum;++i){cout<<"输入顶点"<<i<<endl;cin>>G.vexs[i];}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}for(int k=0;k!=G.arcnum;++k){cout<<"输入一条边依附的顶点和权:(a b 3)不包括“()”"<<endl;cin>>v1>>v2>>w;//输入一条边依附的两点及权值i=localvex(G,v1);//确定顶点V1和V2在图中的位置j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}cout<<"图G邻接矩阵创建成功！"<<endl;return G.vexnum;}void ljjzprint(MGraph_L G) //邻接矩阵的输出{int i,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)cout<<G.arcs[i][j].adj<<" ";cout<<endl;}}int visited[max];//访问标记int we;typedef struct arcnode//弧结点{int adjvex;//该弧指向的顶点的位置struct arcnode *nextarc;//弧尾相同的下一条弧char *info;//该弧信息}arcnode;typedef struct vnode//邻接链表顶点头接点{char data;//结点信息arcnode *firstarc;//指向第一条依附该结点的弧的指针}vnode,adjlist;typedef struct//图的定义{adjlist vertices[max];int vexnum,arcnum;int kind;}algraph;//…………………………………………队列定义……………………typedef struct qnode{int data;struct qnode *next;}qnode,*queueptr;typedef struct{queueptr front;queueptr rear;}linkqueue;//………………………………………………………………………typedef struct acr{int pre;//弧的一结点int bak;//弧另一结点int weight;//弧的权}edg;int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图{int i=0,j=0;arcnode *arc,*tem,*p;for(i=0;i!=G.vexnum;++i){gra.vertices[i].data=G.vexs[i];gra.vertices[i].firstarc=NULL;}for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j){if(gra.vertices[i].firstarc==NULL){if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode *)malloc(sizeof(arcnode));arc->adjvex=j;gra.vertices[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){tem=(arcnode *)malloc(sizeof(arcnode));tem->adjvex=j;gra.vertices[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;}--j;}}else{if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode *)malloc(sizeof(arcnode));arc->adjvex=j;p->nextarc=arc;arc->nextarc=NULL;p=arc;}}}}gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout<<"图G邻接表创建成功！"<<endl;return 1;}void adjprint(algraph gra) //邻接表输出{int i;for(i=0;i!=gra.vexnum;++i){arcnode *p;cout<<i<<" ";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}}int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点//即以V为尾的第一个结点{if(v.firstarc!=NULL)return v.firstarc->adjvex;}int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点{arcnode *p;p=v.firstarc;while(p!=NULL&&p->adjvex!=w){p=p->nextarc;}if(p->adjvex==w&&p->nextarc!=NULL){p=p->nextarc;return p->adjvex;}if(p->adjvex==w&&p->nextarc==NULL)return -10;}int initqueue(linkqueue &q)//初始化队列{q.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)return 0;q.front->next=NULL;return 1;}int enqueue(linkqueue &q,int e)//入队{queueptr p;p=(queueptr)malloc(sizeof(qnode));if(!p)return 0;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return 1;}int dequeue(linkqueue &q,int &e)//出队{queueptr p;if(q.front==q.rear)return 0;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return 1;}int queueempty(linkqueue q)//判断队为空{if(q.front==q.rear) return 1;return 0;}void bfstra(algraph gra)//广度优先遍历{int i,e;linkqueue q;for(i=0;i!=gra.vexnum;++i)visited[i]=0;initqueue(q);for(i=0;i!=gra.vexnum;++i)if(!visited[i]){ visited[i]=1;cout<<gra.vertices[i].data;enqueue(q,i);while(!queueempty(q)){dequeue(q,e);for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gr a,gra.vertices[e],we)){if(!visited[we]){visited[we]=1;cout<<gra.vertices[we].data;enqueue(q,we);}}}}}int dfs(algraph gra,int i){visited[i]=1;int we1;cout<<gra.vertices[i].data;for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.v ertices[i],we)){we1=we;if(visited[we]==0)dfs(gra,we);we=we1;}return 1;}int dfstra(algraph gra){int i,j;for(i=0;i!=gra.vexnum;++i){visited[i]=0;}for(j=0;j!=gra.vexnum;++j){if(visited[j]==0)dfs(gra,j);}return 0;}int bfstra_fen(algraph gra)//求连通分量{int i,j;for(i=0;i!=gra.vexnum;++i)visited[i]=0;for(j=0;j!=gra.vexnum;++j){if(visited[j]==0){dfs(gra,j);cout<<endl;}}return 0;}typedef struct{int adjvex;int lowcost;}closedge;int prim(int g[][max],int n) //最小生成树PRIM算法{int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径//prevex []存储最短路径在U中的结点int i,j,k,min;for(i=2;i<=n;i++) //n个顶点，n-1条边{lowcost[i]=g[1][i]; //初始化prevex[i]=1; //顶点未加入到最小生成树中}lowcost[1]=0; //标志顶点1加入U集合for(i=2;i<=n;i++) //形成n-1条边的生成树{min=inf;k=0;for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边 if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);lowcost[k]=0; //顶点k加入Ufor(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];prevex[j]=k;}printf("\n");}return 0;}int acrvisited[100];//kruscal弧标记数组int find(int acrvisited[],int f){while(acrvisited[f]>0)f=acrvisited[f];return f;}void kruscal_arc(MGraph_L G,algraph gra) {edg edgs[20];int i,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=G.arcs[i][j].adj;++k;}}int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;++i)acrvisited[i]=0;for(j=0;j!=G.arcnum;++j){m=10000;for(i=0;i!=G.arcnum;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}buf=find(acrvisited,x);edf=find(acrvisited,y);edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}int main(){algraph gra;MGraph_L G;int i,d,g[20][20];char a='a';d=creatMGraph_L(G);creatadj(gra,G);vnode v;cout<<endl<<"……####注意：若该图为非强连通图(含有多个连通分量)时"<<endl<<" 最小生成树不存在,则显示为非法值。