克鲁斯卡尔算法求最小生成树（最小生成树的两种算法）

本文目录

• 最小生成树的两种算法
• 图所示是一个无向带权图,请分别按Prim算法和Kr***al算法求最小生成树.
• 已知一个如图所示的带权网络图，使用克鲁斯卡尔算法构造该图的最小生成树
• c加加提问，克鲁斯卡尔算法是什么
• 克鲁斯卡尔算法求最小生成树
• 图的相关算法（二）：最小生成树算法
• kr***al算法是什么
• 最小生成树
• 最小生成树怎么求
• 图的最小生成树算法(Prim和Kr***al)

最小生成树的两种算法

主要有两个：1.普里姆（Prim)算法特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。2.克鲁斯卡尔（Kr***al)算法特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。

图所示是一个无向带权图,请分别按Prim算法和Kr***al算法求最小生成树.

•普里姆（Prim）算法

基本思想

假设N=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是所求的最小生成树，其中U是T的顶点集，TE是T的边集。

（1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U,v∈V-U的边中选一条代价最小的边（u0，v0）并入集合TE，同时将v0并入U；

（3）重复（2），直到U=V为止。

此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。

克鲁斯卡尔（Kr***al）算法

基本思想

假设N=(V,E)是一个具有n个顶点的连通网，

（1）将n个顶点看成n个集合；

（2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；

（3）重复（2），直到所有的顶点都在同一个顶点集合内。  

注意：1.最小生成树不唯一。

2.该图从节点最小开始。

已知一个如图所示的带权网络图，使用克鲁斯卡尔算法构造该图的最小生成树

将原图中所有的边按权值从小到大排序；从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中；重复3，直至图G中所有的节点都在同一个连通分量中。第一步，连（1，2）第二步，连（3，4）第三步，连（2，4）第四步，连（3，6）或者（1，5）这两条权重都一样先后无所谓

c加加提问，克鲁斯卡尔算法是什么

克鲁斯卡尔算法，从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：

• 生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；

• 对于具有 n 个顶点的连通网，其生成树中只能有 n-1 条边，这 n-1 条边连通着 n 个顶点。

连接 n 个顶点在不产生回路的情况下，只需要 n-1 条边。

• 所以克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。

• 假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。

图 1 连通网

请点击输入图片描述

• 例如，使用克鲁斯卡尔算法找图 1 的最小生成树的过程为：
• 首先，在初始状态下，对各顶点赋予不同的标记（用颜**别），如下图所示：

（1）

请点击输入图片描述

• 对所有边按照权值的大小进行排序，按照从小到大的顺序进行判断，首先是（1，3），由于顶点 1 和顶点 3 标记不同，所以可以构成生成树的一部分，遍历所有顶点，将与顶点 3 标记相同的全部更改为顶点 1 的标记，如（2）所示：

（2）

请点击输入图片描述

• 其次是（4，6）边，两顶点标记不同，所以可以构成生成树的一部分，更新所有顶点的标记为：

（3）

请点击输入图片描述

• 其次是（2，5）边，两顶点标记不同，可以构成生成树的一部分，更新所有顶点的标记为：

（4）

请点击输入图片描述

• 然后最小的是（3，6）边，两者标记不同，可以连接，遍历所有顶点，将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记：

（5）

请点击输入图片描述

• 继续选择权值最小的边，此时会发现，权值为 5 的边有 3 个，其中（1，4）和（3，4）各自两顶点的标记一样，如果连接会产生回路，所以舍去，而（2，3）标记不一样，可以选择，将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记：

（6）

请点击输入图片描述

• 当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为（6）所示。
• 实现代码：#include "stdio.h"#include "stdlib.h"#define MAX_VERtEX_NUM 20#define VertexType inttypedef struct edge{VertexType initial;VertexType end;VertexType weight;}edge.end);}return 0;}
• 测试数据：

输入连通网的边数：6 10输入连通网的顶点：123456输入各边的起始点和终点及权重：1,2,61,3,11,4,52,3,52,5,33,4,53,5,63,6,44,6,25,6,61,34,62,53,62,3

克鲁斯卡尔算法求最小生成树

克鲁斯卡尔算法的基本思想，这是我自己结合教材理解的，难免有误，谨慎参考：1：将图中的n顶点看成是n个集合。解释为，图中共有6个顶点，那么就有六个集合。即a,b,c,d,e,f各自分别都是一个集合。｛a｝,｛b｝等。2：按权值由小到大的顺序选择边。所选边应满足两个顶点不在同一个顶点集合内。将该边放到生成树边的集合，同时将该边的两个顶点所在的集合合并。这是书上的描述，可能有点难理解，这里解释一下：首先，选择权值最小的边，即为图中的（a,c）边，此时a,c满足不在同一个顶点集合内，将这个边记录下来，然后合并这两个顶点的集合，即此时剩下五个顶点集合了，｛a,c｝,｛b｝,｛d｝,｛e｝，｛f｝3：重复步骤2，直到所有的顶点都在同一个集合内！解释如下：此时剩下的边中权值最小的为（d，f），满足不在同一个顶点集合，所以记录下该边，然后合并这两个顶点集合。新的顶点集合为｛a，c｝ ｛b｝ ｛e｝ ｛d，f｝接着，继续重复，选择边（b，e），满足不在同一个顶点集合内，所以记录下该边，然后再次合并这两个集合，新的集合为｛a,c｝ ｛d,f｝ ｛b,e｝继续，选择边（c,f）,满足不在同一个顶点集合内，所以记录下该边，然后合并这两个顶点所在的集合，新集合为｛a,c,d,f｝ ｛b,e｝再继续，选择权值为15的边，发现边（c,d）和边（a,d）都不满足条件不在同一个顶点集合内，所以只能选择边（b,c），记录下该边，然后合并顶点集合，新集合为｛a,b,c,d,e,f｝，此时所有点都在同一集合内，所以结束！4：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：

图的相关算法（二）：最小生成树算法

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

例如，对于上图中的连通网可以有多棵权值总和不相同的生成树。

克鲁斯卡尔（Kr***al）算法，是用来求加权连通图的最小生成树的算法。

基本思想 ：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。 具体做法 ：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林中，并使得森林不产生回路，直到森林变成一棵树为止。

以图G4为例（更详细的可以参考《算法导论》p367），对Kr***al进行演示（假设，用数组R保存最小生成树结果）。

第1步 ：将边《E,F》加入R中。 边《E,F》的权值最小，因此将它加入到最小生成树结果R中。 第2步 ：将边《C,D》加入R中。 上一步操作之后，边《C,D》的权值最小，因此将它加入到最小生成树结果R中。 第3步 ：将边《D,E》加入R中。 上一步操作之后，边《D,E》的权值最小，因此将它加入到最小生成树结果R中。 第4步 ：将边《B,F》加入R中。 上一步操作之后，边《C,E》的权值最小，但《C,E》会和已有的边构成回路；因此，跳过边《C,E》。同理，跳过边《C,F》。将边《B,F》加入到最小生成树结果R中。 第5步 ：将边《E,G》加入R中。 上一步操作之后，边《E,G》的权值最小，因此将它加入到最小生成树结果R中。 第6步 ：将边《A,B》加入R中。 上一步操作之后，边《F,G》的权值最小，但《F,G》会和已有的边构成回路；因此，跳过边《F,G》。同理，跳过边《B,C》。将边《A,B》加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是： 《E,F》 《C,D》 《D,E》 《B,F》 《E,G》 《A,B》 。

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题： 问题一 对图的所有边按照权值大小进行排序。 问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一用排序算法排序即可。 问题二，处理方式：记录顶点在“最小生成树”中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点"(关于这一点，后面会通过图片给出说明)。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：

在将《E,F》 《C,D》 《D,E》加入到最小生成树R中之后，这几条边的顶点就都有了终点：

关于终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然《C,E》是权值最小的边。但是C和E的重点都是F，即它们的终点相同，因此，将《C,E》加入最小生成树的话，会形成回路。这就是判断回路的方式。

普里姆（Prim）算法，也是求加权连通图的最小生成树的算法。

基本思想 对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有顶点）的边中选取权值最小的边（u，v），将顶点v加入U中，将边（u,v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，此时集合T中包含了最小生成树中的所有边。

以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。

初始状态 ：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！ 第1步 ：将顶点A加入到U中。 此时，U={A}。 第2步 ：将顶点B加入到U中。 上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。 第3步 ：将顶点F加入到U中。 上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。 第4步 ：将顶点E加入到U中。 上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。 第5步 ：将顶点D加入到U中。 上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。 第6步 ：将顶点C加入到U中。 上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。 第7步 ：将顶点G加入到U中。 上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。

kr***al算法是什么

kr***al算法是：克鲁斯卡尔算法。是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）、（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。

克鲁斯卡尔（Kr***al）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。

在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。

复杂度：

克鲁斯卡尔算法的时间复杂度主要由排序方法决定，而克鲁斯卡尔算法的排序方法只与网中边的条数有关，而与网中顶点的个数无关，当使用时间复杂度为O（elog2e）的排序方法时，克鲁斯卡尔算法的时间复杂度即为O（log2e），因此当网的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果较好。

最小生成树

所谓最小生成树，就是在一个具有N个顶点的带权连通图G中，如果存在某个子图G’，其包含了图G中的所有顶点和一部分边，且不形成回路，并且子图G’的各边权值之和最小，则称G’为图G的最小生成树。 由定义我们可得知最小生成树的三个性质： •最小生成树不能有回路。 •最小生成树可能是一个，也可能是多个。 •最小生成树边的个数等于顶点的个数减一。 本文将介绍两种最小生成树的算法，分别为克鲁斯卡尔算法(Kr***al Algorithm)和普利姆算法(Prim Algorithm)。 克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。 克鲁斯卡尔算法的执行步骤： 第一步：在带权连通图中，将边的权值排序； 第二步：判断是否需要选择这条边（此时图中的边已按权值从小到大排好序）。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。 第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。 下面我用图示法来演示克鲁斯卡尔算法的工作流程，如下图：

最小生成树怎么求

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kr***al（克鲁斯卡尔）算法或Prim（普里姆）算法求出。求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。当一条边（u，v）加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。伪代码GenerieMST(G){//求G的某棵MSTT〈-￠； //T初始为空，是指顶点集和边集均空while T未形成G的生成树 do{找出T的一条安全边（u，v）；//即T∪{(u，v)}仍为MST的子集T=T∪{(u，v)}； //加入安全边，扩充T}return T； //T为生成树且是G的一棵MST}注意：下面给出的两种求MST的算法均是对上述的一般算法的求精，两算法的区别仅在于求安全边的方法不同。为简单起见，下面用序号0，1，…，n-1来表示顶点集，即是：V(G)={0，1，…，n-1}，G中边上的权解释为长度，并设T=(U，TE）。求最小生成树的具体算法（pascal):Prim算法procedure prim(v0:integer);varlowcost,closest:array of integer;i,j,k,min:integer;beginfor i:=1 to n do beginlowcost;closest:=v0;end;for i:=1 to n-1 do begin{寻找离生成树最近的未加入顶点 k}min:=maxlongint;for j:=1 to n doif (lowcost《》0) then beginmin:=lowcost;k:=j;end;lowcost:=0; {将顶点k 加入生成树}{生成树中增加一条新的边 k 到 closest}{修正各点的 lowcost 和 closest 值}for j:=1 to n doif cost then beginlowcost;closest:=k;end;end;end;Kr***al算法按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。function find(v:integer):integer; {返回顶点 v 所在的集合}var i:integer;begini:=1;while (i《=n) and (not v in vset) do inc(i);if i《=n then find:=i else find:=0;end;procedure kr***al;vartot,i,j:integer;beginfor i:=1 to n do vset:=i;{初始化定义 n 个集合，第 I个集合包含一个元素 I}p:=n-1; q:=1; tot:=0; {p 为尚待加入的边数，q 为边集指针}sort;{对所有边按权值递增排序，存于 e中，e.v1 与 e.v2 为边 I 所连接的两个顶点的序号，e.len 为第 I条边的长度}while p》0 do begini:=find(e.v2）;if i《》j then begininc(tot,e.len);vset:=vset+vset;dec(p);end;inc(q);end;writeln(tot);end;C语言代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185#include《stdio.h》#include《stdlib.h》#include《iostream.h》#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#defineMAX1000typedefstructArcell{doubleadj;}Arcell,AdjMatrix;typedefstruct{charvexs;//节点数组AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前节点数和弧数}MGraph;typedefstructPnode//用于普利姆算法{charadjvex;//节点doublelowcost;//权值}Pnode,Closedge;//记录顶点集U到V-U的代价最小的边的辅助数组定义typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点{charch1;//节点1charch3;//节点2doublevalue;//权值}Knode,Dgevalue; //-------------------------------------------------------------------------------intCreateUDG(MGraph&G,Dgevalue&dgevalue);intLocateVex(MGraphG,charch);intMinimum(MGraphG,Closedgeclosedge);voidMiniSpanTree_PRIM(MGraphG,charu);voidSortdge(Dgevalue&dgevalue,MGraphG); //-------------------------------------------------------------------------------intCreateUDG(MGraph&G,Dgevalue&dgevalue)//构造无向加权图的邻接矩阵{inti,j,k;cout《《"请输入图中节点个数和边/弧的条数：";cin》》G.vexnum》》G.arcnum;cout《《"请输入节点：";for(i=0;i《G.vexnum;++i)cin》》G.vexs;for(i=0;i《G.vexnum;++i)//初始化数组{for(j=0;j《G.vexnum;++j){G.arcs.adj=MAX;}}cout《《"请输入一条边依附的定点及边的权值："《《endl;for(k=0;k《G.arcnum;++k){cin》》dgevalue.value;i=LocateVex(G,dgevalue.ch1）;j=LocateVex(G,dgevalue.ch3）;G.arcs.value;G.arcs.adj;}returnOK;}intLocateVex(MGraphG,charch)//确定节点ch在图G.vexs中的位置{inta;for(inti=0;i《G.vexnum;i++){if(G.vexs==ch)a=i;}returna;}voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆算法求最小生成树{inti,j,k;Closedgeclosedge;k=LocateVex(G,u);for(j=0;j《G.vexnum;j++){if(j!=k){closedge.adjvex=u;closedge.adj;}}closedge.lowcost=0;for(i=1;i《G.vexnum;i++){k=Minimum(G,closedge);cout《《"("《《closedge.lowcost《《")"《《endl;closedge.lowcost=0;for(j=0;j《G.vexnum;++j){if(G.arcs.lowcost){closedge;closedge.adj;}}}}intMinimum(MGraphG,Closedgeclosedge)//求closedge中权值最小的边，并返回其顶点在vexs中的位置{inti,j;doublek=1000;for(i=0;i《G.vexnum;i++){if(closedge.lowcost《k){k=closedge.lowcost;j=i;}}returnj;}voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克鲁斯卡尔算法求最小生成树{intp1,p2,i,j;intbj;//标记数组for(i=0;i《G.vexnum;i++)//标记数组初始化bj=i;Sortdge(dgevalue,G);//将所有权值按从小到大排序for(i=0;i《G.arcnum;i++){p1=bj;p2=bj;if(p1!=p2）{cout《《"("《《dgevalue.value《《")"《《endl;for(j=0;j《G.vexnum;j++){if(bj==p2）bj=p1;}}}}voidSortdge(Dgevalue&dgevalue,MGraphG)//对dgevalue中各元素按权值按从小到大排序{inti,j;doubletemp;charch1,ch3;for(i=0;i《G.arcnum;i++){for(j=i;j《G.arcnum;j++){if(dgevalue.value){temp=dgevalue.value;dgevalue.value;dgevalue.value=temp;ch1=dgevalue.ch1;dgevalue.ch1;dgevalue.ch1=ch1;ch3=dgevalue.ch3;dgevalue.ch3;dgevalue.ch3=ch3;}}}}voidmain(){inti,j;MGraphG;charu;Dgevaluedgevalue;CreateUDG(G,dgevalue);cout《《"图的邻接矩阵为："《《endl;for(i=0;i《G.vexnum;i++){for(j=0;j《G.vexnum;j++)cout《《G.arcs.adj《《"";cout《《endl;}cout《《"=============普利姆算法===============\n";cout《《"请输入起始点：";cin》》u;cout《《"构成最小代价生成树的边集为：\n";MiniSpanTree_PRIM(G,u);cout《《"============克鲁斯科尔算法=============\n";cout《《"构成最小代价生成树的边集为：\n";MiniSpanTree_KRSL(G,dgevalue);}pascal算法program didi;vara:array of records,t,len:longint;end;fa,r:array of longint;n,i,j,x,y,z:longint;tot,ans:longint;count,xx:longint;procedure quick(l,r:longint);vari,j,x,y,t:longint;begini:=l;j:=r;x:=a.len;repeatwhile x》a.len do inc(i);while x《a.len do dec(j);if i《=j thenbeginy:=a.len:=y;y:=a.s:=y;y:=a.t:=y;inc(i);dec(j);end;until i》j;if i《r then quick(i,r);if l《j then quick(l,j);end;function find(x:longint):longint;beginif fa);find:=fa;end;procedure union(x,y:longint);{启发式合并}vart:longint;beginx:=find(x);y:=find(y);if r thenbegint:=x;x:=y;y:=t;end;if r);fa:=y;end;beginreadln(xx,n);for i:=1 to xx do fa:=i;for i:=1 to n dobeginread(x,y,z);inc(tot);a.s:=x;a.t:=y;a.len:=z;end;quick（1,tot);{将边排序}ans:=0;count:=0;i:=0;while count《=x-1 do{count记录加边的总数}begininc(i);with a doif find(s)《find(t) thenbeginunion(s,t);ans:=ans+len;inc(count);end;end;write(ans);end.Primvarm,n:set of 1..100;s,t,min,x,y,i,j,k,l,sum,p,ii:longint;a:arrayof longint;beginreadln(p);for ii:=1 to p dobegink:=0; sum:=0;fillchar(a,sizeof(a),255);readln(x);m:=;n:=;for i:=1 to x dobeginfor j:=1 to x dobeginread(a);if a=0then a:=maxlongint;end;readln;end;for l:=1 to x-1 dobeginmin:=maxlongint;for i:=1 to x doif i in mthen beginfor j:=1 to x dobeginif (a《min)and(j in n)then beginmin:=a;s:=i;t:=j;end;end;end;sum:=sum+min;m:=m+;n:=n-;inc(k);end;writeln(sum);end;end.

图的最小生成树算法(Prim和Kr***al)