最小生成树(Prim、Kruskal算法)整理版
一、树及生成树的基本概念
树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述：
(1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。
例如：已知有六个城市，它们之间要架设电话线，要求任
意两个城市均可以互相通话，并且电话线的总长度最短。若用
六个点v1…v6代表这六个城市，在任意两个城市之间架设电话
线，即在相应的两个点之间连一条边。这样，六个城市的一个
电话网就作成一个图。任意两个城市之间均可以通话，这个图
必须是连通图，且这个图必须是无圈的。否则，从圈上任意去
掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是
一个不含圈的连通图，代表了一个电话线网。
生成树（支撑树）
定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。
定理：一个图G有生成树的条件是G是连通图。
证明:必要性显然；
充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子
图G K，且不含圈，从而G K是一个生成树。
寻找连通图生成树的方法：
破圈法：从图中任取一个圈，去掉一条边。再对剩下的图
重复以上步骤，直到不含圈时为止，这样就得到一个生成树。
取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图
中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3）
中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7，
这样，剩下的图不含圈，于是得到一个支撑树，如图所示。
避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。
二、最小生成树
概念：设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v,w]。所有生成树G’上各边权的总和最小的生成树称为G的最小生成树。
应用：如在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v，w]表示建立城市v、w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络最经济的方案。
性质：设G=(V,E)是连通带权图，U是V的真子集。若(u,v)∈E，且u∈U，v∈V-U，且在所有这样的边中，(u,v)的权c[u，v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质也称为MST性质。
算法：
经典方法有两种：kruskal、prim算法（贪心思想）：一次生成一条最短边。
【Prim算法】：
算法思想：任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。按结点来贪，因此适用于稠密图的处理.
算法内容：
①设置顶点集合V和边集E，它们的初始状态为空集。
②任意选取一个顶点A加入V中。
③重复以下过程直到V中已经包含原图的所有节点：
1、选一条权值最小的边(u,v)，并使其满足u,v两节点只有一个在点集V中。
2、将两个节点中不在V的那个点加入集合V中，并将边(u,v)加入边集E中。
④所得的子图G’=(V,E)即为所求的最小生成树。
关键：找出当前最优得一条边,穷举每一条不在集合E中的边，找出符合条件且最优的边。时间复杂度：O（V*E），即顶点数乘以边数。
代码：
var
n,i,j,k,min,sum:longint;
a:array[1..1000,1..1000]of longint;
b,d:array[1..1000]of longint;
procedure prim;
begin
sum:=0;
for i:=1 to n do d[i]:=a[1,i];
for j:=2 to n do
begin
min:=maxlongint;
for i:=1 to n do
if (d[i]
begin
min:=d[i]; k:=i;
end;
sum:=sum+d[k]; d[k]:=0;
for i:=1 to n do
if (a[k,i]
end;
end;
begin
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
if (i<>j) and (a[i,j]=0) then a[i,j]:=maxlongint;
end;//初始化
prim;
writeln(sum);
end.
Prim算法：
初始状态A包含任意一个顶点r，从r开始，每次都向A中添加一条连接树A和G=（V,A）中某个孤立顶点的轻边，直至生成树A包含了图中所有的顶点。
有效实现该算法的关键是设法较容易地选择一条轻边。我们可以借助最小优先级队列。
图中的顶点可以分为两类，一类是在A中的，已经纳入最小生成树了，另一种是不在A 中的，记为B，对于这些顶点，我们需要保存它们与A中的某个顶点相连的边中的最小权值。最小优先级队列保存的就是B（尚未纳入最小生成树）中的顶点以及它们与A中某个顶点相连的边中的最小权值。每次队首出队，设新加入A的顶点为V，那么我们要修改V的邻接点中尚未在A中（在最小优先级队列）的且与A中顶点相连的边的最小权值（比较拗口）。Prim+heapy优化：
*优化：在选择权值最小的可行边时可以使用堆。(nlogn) 堆优化的Prim算法适用于稀疏图，而不优化的Prim算法适用于稠密图。
代码：
var
n,i,j,k,sum:longint;
a:array[0..1000,0..1000]of longint;
b,d,heap,pos:array[0..10000]of longint;
procedure swap(var i,j:longint);{交换整数i和j}//省略
procedure heapify(p:longint);{向下调整堆的过程}
var best:longint;
begin
best:=p;//下面两个if是分别判断根和左、右孩子最短距离的大小
if (p*2<=j-1) and (key[heap[p*2]] if (p*2+1<=j-1) and (key[heap[p*2+1]] if best<>p then//若根有所变动，即跟比左右孩子都大（最短距离） begin swap(pos[heap[p]],pos[heap[best]]);//互换节点heap[p]、heap[best]在堆的位置swap(heap[p],heap[best]);//互换堆中元素p、best heapify(best);//继续调整互换后的元素best end; end; procedure modify(id,new_d:longint); {判断new_d与d[id]大小，并修改key[id]大小} var p:longint; begin if (new_d begin//修改 d[id]:=new_d;//更新最短距离 p:=pos[id];//结点id在堆中的位置 while (p>1) and (key[heap[p]] begin swap(pos[heap[p]],pos[heap[p div 2]]); swap(heap[p],heap[p div 2]); p:=p div 2;//更上一层 end; end; end; procedure extract（抽出）(var id:longint);{读取堆中最小元素的节点编号} begin id:=heap[1];//堆顶 swap(pos[heap[1]],pos[heap[j]]);// 堆顶的元素和第j个元素换位置 swap(heap[1],heap[j]);//把堆顶的元素扔到j后面去， heapify(1);//此时堆顶不一定是最小的~扔到下面去，把最小的搞上来。 end; procedure prim; begin d[1]:=0; for j:=n downto 1 do begin extract(k); sum:=sum+d[k]; for i:=1 to n do if (pos[i] end; begin readln(n); for i:=1 to n do for j:=1 to n do begin read(a[i,j]); if (i<>j) and (a[i,j]=0) then a[i,j]:=maxlongint; end;//初始化 for i:=1 to n do begin heap[i]:=i; pos[i]:=i; d[i]:=maxlongint; end; prim; writeln(sum); end. 【Kruskal算法】 算法内容： 初始时把每个顶点看作一个集合 ①将所有边以长度为关键词从小到大排序。 ②将每个顶点都加入一个集合中，即N个顶点共N个集合。 ③设置边集E，初始状态为空。 ④从小到大访问每条边，若边连接的两个顶点属于不同集合，则合并两个顶点所在的集合，并将该边加入到边集E中。 ⑤所得的子图TG=(V,E)即为所求的最小生成树，其中顶点集V就是原图的所有顶点。 **关键：集合的合并。我们可以采用路径压缩的算法，用树结构作为集合的结构，对于每个点只记录它的父亲，集合的代表元素即为树的根。在判断两个节点是否属于同一集合时，递归查找节点所在树的根，同时压缩路径。合并集合只需将集合B的根的父亲记为集合A 的根即可。 时间复杂度：O（eloge） x,j,tot,i,n:longint; l,a,b:array[1 ..10000] of longint; f:array[1 ..100] of longint; procedure qs(low,high:longint); //以每条边的长度排序；function find(x:longint):longint;//找集合的根结点、 var tmp: longint; begin if f[x]=x then exit(x) else exit(find(f[x])); end; procedure union(u,v:longint); //合并子集 var fu,fv:longint; begin fu:=find(u); fv:=find(v); f[fv]:=fu; end; procedure kruskal; var cnt,i,ans:longint; begin for i:=1 to n do f[i]:=i;//初始子集，都是自己； cnt:=0; ans:=0; for i := 1 to tot do if (find(a)<>find(b)) then//判断是否属于同一子集 begin union(a,b); inc(ans); inc(cnt); if cnt=n-1 then break; //n个结点，连接n-1条边end; writeln(ans); end; begin tot:= 0; readln(n); for i:=1 to n do for j := 1 to n do begin read(x); if (i<>j) then begin inc(tot); a[tot]:= i; b[tot] := j; l[tot]:= x; end; end; qsort(1,tot); kruskal; end. 1.Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。 2.Prim+Heap在任何时候都有令人满意的的时间复杂度，但是代价是空间消耗极大。【以及代码很复杂>_<】 3.时间复杂度并不能反映出一个算法的实际优劣。 竞赛题大多数是稀疏图，所以尽可能地使用Prim+Heap，在稀疏图中这是无敌的。如果一定要在朴素Prim和Kruskal里选一个的话那就用Kruskal吧。当然Prim的代码比较简单，对付水题用Prim也无所谓，只要不是极稀疏图两者相差不大 习题： 1、最优布线问题（wire） [问题描述] 学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。 当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。 现在由你负责连接这些计算机，使任意两台计算机都连通（不管是直接的或间接的）。[输入格式] 输入文件wire.in，第一行为整数n（2<=n<=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。[输出格式] 输出文件wire.out，一个整数，表示最小的连接费用。 [样例输入] 3 0 1 2 1 0 1 2 1 0 [样例输出] 2（注：表示连接1和2，2和3，费用为2） [问题分析] 这道题是典型的求最小生成树的题目，可以运用上文所讲的两种算法进行处理。 2、【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？ 【输入】 第一行两个数v(v<=200),e，分别代表城市数和边数，以下e行，每行为两个顶点和它们之间的边权w(w<1000)。 【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 2 10 2 3 5 2 4 6 2 6 11 4 5 18 3、例题 农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。 输入格式 Input Format (1)采用邻接矩阵存储 第一行为农场的个数，N（3<=N<=100）。接下去为一个N*N的矩阵,表示每个农场之间的距离。(农场之间的距离小于999，0路线表示无法直接到达)。 (2)图采用边目录方式存储。 第一行N为农场的个数,M为农场与农场之间共有M条可以搭设光纤路线。接下去的M 行为中每行有3个数A，B，C。分别表示农场A到农场B的距离为B。 输出格式 Output Format 输出连接所有农场并所用光纤最短的方案。 样例输入 Sample Input (1)采用邻接矩阵存储。 (2)采用边目录方式存储。 6 6 7 0 3 0 0 0 2 1 2 3 3 0 5 0 2 0 2 3 5 0 5 0 1 0 0 3 4 1 0 0 1 0 4 0 4 5 4 0 2 0 4 0 1 2 5 2 2 0 0 0 1 0 6 5 1 1 6 2 样例输出 Sample Output 10 算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日 题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。 最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。 对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。 求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。 例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)； 将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE） 编号： 审定成绩： 重庆邮电大学研究生堂下考试答卷 2013-2014学年第1 学期论文题目：最小生成树在旅游路线选择中的应用 学院名称： 学生姓名： 专业： 学号： 指导教师： 重庆邮电大学教务处制 摘要 随着生活节奏的加快，人民生活水平的提高，人们越来越热衷于四处旅游，同时，大家也不愿意将大部分的时间花费在路途上，人们旅游目的在于放松、赏景、游玩，旅游公司就不得不根据游客要求做出相应的旅游路线安排。很多旅游景点之间都相隔一定的距离，那么如何在众多旅游景点路线中选择最近的一条呢？因此，如何做到即保证游览各个景点又确保路途最近地从众多可行路线中选出最优路线成为了解决此问题的关键。 图论最小生成树理论常用于交通线路选择中，本文将其运用于旅游交通优化与线路组织上，即在赋权图中找出一颗最优树，以满足以最短路径最小连接各旅游目的城市和最小的建设成本。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法。本文涉及的抽象图形结构较为简单，使用各类算法的差别在此并无明显体现，一般来说，Kruskal 算法应用较为普遍，因此本文采用Kruskal 算法实现最优路径求取。 文中通过一个例子应用，将最小生成树的Kruskal 算法实际化，通过算法步骤分析，以及在VC++6.0中程序的运行，最终求出的最小生成树与实际相符，该算法思想成立，并具有一般性，能够增删节点、修改权值，也可运用到其他问题的解决中。 关键词：旅游路线问题 Kruskal算法最优路线最小生成树 一、引言 旅游交通是为旅游者由客源地到旅游目的地的往返，以及在旅游目的地各处旅游活动而提供的交通设施及服务，其便利程度，是衡量旅游业发达程度的重要标志。与一般交通不同，旅游交通过程本身也是旅游体验过程，对于游客来说，立足于最小的时间与经济成本获得最多的旅游体验，对于旅游组织者来说，则立足于最小的建设成本与最大的社会、经济、生态效益。道路是交通的载体，具有高度通达性、完善的旅游服务功能和景观化、生态化、人性化的道路是区域旅游交通完善的重要标志，基于此，有学者提出“风景道”、“旅游交通干道”等规划建设理念与原则。其中，旅游交通系统的优化很大程度取决于合理的道路布局，而如何使道路通达性与建设成本之间获得平衡，达到性价比最优，成为道路系统优化的重要指标。因此，其实质上可以简化为最短距离连接各旅游目的地最优解问题[1]。 旅游路线组织是旅游地理学研究的重要内容，其研究主要以游客的行为空间模式为导向，旅游路线是旅游产品的组成部分，作为产品就必须满足游客的需求，因此游客的行为模式就成为旅游路线设计的重要依据。 二、背景知识 1、图和树 图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。树是无圈连通无向图，如果树T的节点数为n，那么树的边数为n-1。 2、生成树 连通图G 上的一个子图，该子图连通，无回路且包含图G 的所有节点，称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。 3、最小生成树 对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因此这些生成树的各边权值之和也不一定相同，其中权值最小的生成树被称为该带权连通图的最小生成树[4]。 三、最小生成树的求解方法 构造最小生成树可以有多种算法。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。 #include { printf("请输入有边的2个顶点\n"); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf("输入的数字不符合要求请重新输入:\n"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf("请输入%d与%d之间的权值:\n", n, m); scanf("%d",&G->arc[n][m].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); } } void sort(edge edges[],MGraph *G)//对权值进行排序{ int i, j; for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("权排序之后的为:\n"); for (i = 1; i < G->arcnum; i++) { 最小生成树的两种经典算法的分析及实现 摘要：数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM和KRUSKAL的两种经典算法的算法思想，对两者进行了详细的比较，最后用这两种经典算法实现了最小生成树的生成。 关键词：连通图，赋权图，最小生成树，算法，实现 1 前言 假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n （n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。一棵生成树的代价就是树上各边的代价之和。 2图的概念 2.1 定义 无序积 在无序积中， 无向图，其中为顶点(结点)集，为边集，，中元素为无向边，简称边。 有向图，其中为顶点(结点)集，为边集，，中元素为有向边，简称边。 有时，泛指有向图或无向图。 2.2 图的表示法 有向图，无向图的顶点都用小圆圈表示。 无向边——连接顶点的线段。 有向边——以为始点，以为终点的有向线段。 2.3 概念 (1)有限图——都是有限集的图。 阶图——的图。 零图——的图。特别，若又有，称平凡图。 (2)关联 (边与点关系)——设边(或)，则称与(或)关联。 无环 孤立点——无边关联的点。 环——一条边关联的两个顶点重合，称此边为环 (即两顶点重合的边)。 悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。 (3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。 简单图——不含平行边和环的图。 2.4 完全图 设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则 称为阶无向完全图，记作。 若有向图的任一对顶点，既有有向边，又有有向边，则 称为有向完全图。 例如： 课程设计报告 课程名称：数据结构课程设计 设计题目：克鲁斯卡尔算法求最小生成树 系别：计算机系 专业：软件技术 学生姓名：陈浩学号:2011304040133 日期: 2013年1月5日-2013年1月11日 目录 1. 需求分析 (2) 1.1 设计题目 (2) 1.2 设计任务及要求 (2) 1.3课程设计思想 (2) 1.4 程序运行流程: (2) 1.5软硬件运行环境及开发工具 (2) 2.概要设计 (2) 2.1流程图 (2) 2.2抽象数据类型MFSet的定义 (3) 2.3主程序 (3) 2.4抽象数据类型图的定义 (4) 2.5抽象数据类型树的定义 (6) 3. 详细设计 (8) 3.1程序 (8) 4.调试与操作说明 (11) 4.1测试结果 (11) 4.2调试分析 (12) 5.课程设计总结与体会 (12) 5.1总结 (12) 5.2体会 (12) 6. 致谢 (13) 7. 参考文献 (13) 1.需求分析 1.1 设计题目：最小生成树 1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。 1.4程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； 1.5 软硬件运行环境及开发工具：VC 2.概要设计 一、树及生成树的基本概念 树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述： (1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。 例如：已知有六个城市，它们之间要架设电话线，要求任 意两个城市均可以互相通话，并且电话线的总长度最短。若用 六个点v1…v6代表这六个城市，在任意两个城市之间架设电话 线，即在相应的两个点之间连一条边。这样，六个城市的一个 电话网就作成一个图。任意两个城市之间均可以通话，这个图 必须是连通图，且这个图必须是无圈的。否则，从圈上任意去 掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是 一个不含圈的连通图，代表了一个电话线网。 生成树（支撑树） 定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。 定理：一个图G有生成树的条件是G是连通图。 证明:必要性显然； 充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子 图G K，且不含圈，从而G K是一个生成树。 寻找连通图生成树的方法： 破圈法：从图中任取一个圈，去掉一条边。再对剩下的图 重复以上步骤，直到不含圈时为止，这样就得到一个生成树。 取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图 中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3） 中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7， 这样，剩下的图不含圈，于是得到一个支撑树，如图所示。 避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。 武 夷 学 院 课程设计报告 课程名称： 数据结构（C 言语版本） 设计题目： 最小生成树的应用 学生班级： 10计科1班 学生姓名： 陈娟，谢贤根，黄伟伟，陈开槟 指导教师： 林丽惠 完成日期： 2012-01-05 课程设计项目研究报告 目录 一、问题描述及基本要求....................................................................................... - 1 - 二、实现本程序需要解决的问题如下................................................................. - 1 - 三、测试数据......................................................................................................... - 2 - 四、算法思想......................................................................................................... - 3 - 五、模块划分............................................................................ 错误！未定义书签。 六、算法设计与分析............................................................................................. - 7 - 七、源程序........................................................................................................... - 11 - 八、测试数据....................................................................................................... - 14 - 九、课程设计项目进度表及任务分配表及任务分配表................................... - 15 - 十、设计心得....................................................................................................... - 16 -十一参考文献....................................................................................................... - 17 - 实验5 最小生成树算法的设计与实现 一、实验目的 1、根据算法设计需要, 掌握连通图的灵活表示方法； 2、掌握最小生成树算法，如Prim、Kruskal算法； 3、基本掌握贪心算法的一般设计方法； 4、进一步掌握集合的表示与操作算法的应用。 二、实验内容 1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法； 2、设计Kruskal算法实验程序。 有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。 三、Kruskal算法的原理方法 边权排序: 1 3 1 4 6 2 3 6 4 1 4 5 2 3 5 3 4 5 2 5 6 1 2 6 3 5 6 5 6 6 1. 初始化时：属于最小生成树的顶点U={} 不属于最小生成树的顶点V={1，2，3，4，5，6} 2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树 的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6} 3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5} 4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5} 5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5} 6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成 xx学院 《数据结构与算法》课程设计 报告书 课程设计题目 PRIM算法求最小生成树 院系名称计算机科学与技术系 专业（班级） 姓名（学号） 指导教师 完成时间 一、问题分析和任务定义 在该部分中主要包括两个方面：问题分析和任务定义； 1 问题分析 本次课程设计是通过PRIM（普里姆）算法，实现通过任意给定网和起点，将该网所对应的所有生成树求解出来。 在实现该本设计功能之前，必须弄清以下三个问题： 1．1 关于图、网的一些基本概念 1．1．1 图图G由两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。通常，V（G）和E（G）分别表示图G的顶点集合和边集合。E（G）也可以为空集。则图G只有顶点而没有边。1．1．2 无向图对于一个图G，若边集E（G）为无向边的集合，则称该图为无向图。1．1．3 子图设有两个图G=（V，E）G’=（V’，）,若V’是V的子集，即V’?V ，且E’是E的子集，即E’?E，称G’是G的子图。 1．1．4 连通图若图G中任意两个顶点都连通，则称G为连通图。 1．1．5 权和网在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。把边上带权的图称为网。如图1所示。 1．2 理解生成树和最小生成树之间的区别和联系 1．2．1 生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：V（G’）= V（G）和E（G’）?E（G），若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。 1．2．2 最小生成树图的生成树不是唯一的，把具有权最小的生成树称为图G的最小生成树，即生成树中每条边上的权值之和达到最小。如图1所示。 图1．网转化为最小生成树 1．3 理解PRIM（普里姆）算法的基本思想 1．3．1 PRIM算法（普里姆算法）的基本思想假设G =（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取V0），将它并入U中，此时U={V0}，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（i,j），其中V i∈U,V j∈(V-U),并把该边（i,j）和顶点j分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组 开题报告 信息与计算科学 最小生成树算法及其应用 一、综述本课题国内外研究动态, 说明选题的依据和意义 最小生成树(minimum spanning tree,MST)是计算机学科中一重要内容, 其算法也是重要的计算方法, 是现代科学中比较热门的研究方向. 一个有个结点的连通图的生成树是原图的极小连通子图, 且包含原图中的所有个n n 结点, 并且有保持图联通的最少的边. 许多应用问题都是一个求五项连通图的最小生成树问题. 例如: 要在个城市之间铺设n 光缆, 主要目标是要使这个城市的任意两个之间都可以通信, 但铺设光缆的费用很高, n 且各个城市之间铺设光缆的费用不同; 另一个目标是要使铺设光缆的总费用最低. 这就需要找到带权的最小生成树. MST 性质: 最小生成树性质: 设是一个连通网络, 是顶点集的一个真(,)G V E =U V 子集. 若是中一条“一个端点在中(例如: ), 另一个端点不在中”的边(,)n u v G U u U ∈U (例如:), 且具有最小权值, 则一定存在的一棵最小生成树包括此边v V U ∈-(,)u v G . (,)u v 求MST 的一般算法可描述为: 针对图, 从空树开始, 往集合中逐条选择并G T T 加入条安全边, 最终生成一棵含条边的MST. 1n -(,)u v 1n -当一条边加入时, 必须保证仍是MST 的子集, 我们将这样的边称(,)u v T {}(,)T u v 为的安全边. 其中主要有两种算法: Prim 算法和Kruskal 算法. T Prim 算法: 该算法由Prim 提出, 但事实上Jarnik 于1930年更早提出. 用于求无向图的最小生成树. 设图 . (),G V E =步骤1: 取一个顶点, 则, . 1v {}1V v ={}E = Kruskal算法求最小生成树（JA V A） 代码： package homework; import java.util.Scanner; import java.util.Arrays; import java.util.ArrayList; class Edge { public int start;//始边 public int end;//终边 public double cost;//权重 } public class MinSpanningTree_Kruskal{ private static int MAX = 100; private ArrayList 实验报告六月 18 2015 姓名：陈斌学号：E 专业：13计算机科学与技术数据结构第八次实验 学号E专业计算机科学与技术姓名陈斌 实验日期教师签字成绩 实验报告 【实验名称】最小生成树和最短路径 【实验目的】 (1)掌握最小生成树以及最短路径的相关概念； (2)掌握Prim算法和Kruskal算法； (3)掌握Dijkstra算法 【实验内容】 采用普里姆算法求最小生成树 (1)编写一个算法，对于教材图(a)所示的无向带权图G采用普里姆算法输出从顶点 V1出发的最小生成树。图的存储结构自选。 (2)对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。（提示：a.先对边按 权值从小到大排序，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶点所处的连通分量，初始时各不相同。b. 依次从E中取出一条边(i,j)，检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset 值都修改为与i的相同。c.重复b步直至输出n-1条边。） 源代码： : #include<> #include<> #include<> dj=INFINITY; /* 网 */ } printf("请输入%d条边的顶点1 顶点2 权值(用空格隔开): \n",; for(k=0;k<;++k) { scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */ i=LocateVex(G,va); j=LocateVex(G,vb); [i][j].adj=[j][i].adj=w; /* 无向 */ } =AN; return OK; } typedef struct { /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */ VertexType adjvex; VRType lowcost; }minside[MAX_VERTEX_NUM]; int minimum(minside SZ,MGraph G) { /* 求的最小正值 */ int i=0,j,k,min; while(!SZ[i].lowcost) i++; min=SZ[i].lowcost; /* 第一个不为0的值 */ k=i; for(j=i+1;j<;j++) if(SZ[j].lowcost>0) 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：最小生成树Kruskal算法 院（系）： 专业： 班级： 学号： 姓名： 指导教师： 目录 1 课程设计介绍 (1) 1.1课程设计内容 (1) 1.2课程设计要求 (1) 2 课程设计原理 (2) 2.1课设题目粗略分析 (2) 2.2原理图介绍 (4) 2.2.1 功能模块图 (4) 2.2.2 流程图分析 (5) 3 数据结构分析 (11) 3.1存储结构 (11) 3.2算法描述 (11) 4 调试与分析 (13) 4.1调试过程 (13) 4.2程序执行过程 (13) 参考文献 (16) 附录（关键部分程序清单） (17) 1 课程设计介绍 1.1 课程设计内容 编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。 1.2 课程设计要求 1.顶点信息用字符串，数据可自行设定。 2.参考相应的资料，独立完成课程设计任务。 3.交规范课程设计报告和软件代码。 2 课程设计原理 2.1 课设题目粗略分析 根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析： 1.要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 2.Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。 3.Dijkstra算法。算法的基本思路是：假设每个点都有一对标号（d j,p j）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；p j则是从s到j 的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下： 1）初始化。起源点设置为：①d s=0,p s为空；②所有其它点：d i=∞,p i=？； ③标记起源点s，记k=s，其他所有点设为未标记的。 2）k到其直接连接的未标记的点j的距离，并设置： d j=min[d j, d k+l kj] 数据结构与算法 课程设计报告 课程名称：数据结构与算法课程设计 题目：改进的最小生成树算法 专业：计算机科学与技术 班级：（一）班 学号：1362810118，1362810107，1362810108 学生姓名：王洪，汪妍，罗林芳 一、目录 一、问题描述 (1) 二、需求分析 (1) 1. 性能需求 (1) 2. 功能需求 (2) 3. 问题假设 (2) 三、准备知识 (2) 1. 欧拉图定义： (2) 2. 欧拉图相关定理：......................................................................... 错误！未定义书签。 3. 欧拉图应用：................................................................................. 错误！未定义书签。 四、算法和数据结构设计 (5) 1. 算法分析 (5) 2. 建立模型 (5) 1) 前期准备................................................................................. 错误！未定义书签。 2) 确定模型................................................................................. 错误！未定义书签。 3. 具体算法实现................................................................................. 错误！未定义书签。 4. 时间复杂度分 (6) 5.题目拓展 (8) 五、程序测试......................................................................................... 错误！未定义书签。 1. 测试1（测试没有度数为奇数的顶点） (9) 2. 测试2（测试度数为奇数的定点有4个） (9) 六、总结 (11) 1. 已完成部分 (11) 2. 后期设想 (11) 3. 课程设计思考与体会............................................................. 错误！未定义书签。 七、参考文献 (11) 目录 1.需求分析 (2) 1.1 设计题目 (2) 1.2 设计任务及要求 (2) 1.3课程设计思想 (2) 1.4 程序运行流程 (2) 1.5软硬件运行环境及开发工具 (2) 2.概要设计 (2) 2.1流程图 (2) 2.2抽象数据类型MFSet的定义 (3) 2.3主程序 (4) 2.4抽象数据类型图的定义 (4) 2.5抽象数据类型树的定义 (5) 3.详细设计 (7) 3.1程序 (7) 4.调试与操作说明 (10) 4.1测试结果 (10) 4.2调试分析 (11) 5.课程设计总结与体会 (11) 5.1总结 (11) 5.2体会 (11) 6. 致谢 (12) 7. 参考文献 (12) 1.需求分析 1.1 设计题目：最小生成树 1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。 1.4程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； 1.5 软硬件运行环境及开发工具：VC 2.概要设计 2.1流程图 图1流程图 2.2抽象数据类型MFSet的定义： ADT MFSet { 数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集Si（i = 1,2...,n）构成，每个子集的成员代表在这个子集中的城市。 数据关系： S1 U S2 U S3 U... U Sn = S, Si包含于S（i = 1,2,...n） Init (n): 初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank 数组初始化0 Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。 Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。 } 最小生成树的算法 王洁 引言： 求连通图的最小生成树是数据结构中讨论的一个重要问题．在现实生活中，经常遇到如何得到连通图的最小生成树，求最小生成树不仅是图论的基本问题之一 ,在实际工作中也有很重要的意义，,人们总想寻找最经济的方法将一个终端集合通过某种方式将其连接起来 ,比如将多个城市连为公路网络 ,要设计最短的公路路线;为了解决若干居民点供水问题 ,要设计最短的自来水管路线等.而避开这些问题的实际意义 ,抓住它们的数学本质 ,就表现为最小生成树的构造。下面将介绍几种最小生成树的算法。 一，用“破圈法”求全部最小生成树的算法 1 理论根据 1.1 约化原则 给定一无向连通图 G =（V ,E ）（ V 表示顶点，E 表示边），其中 V={ 1v , 2v ,3v …… n v },E= { 1e , 2e , 3e …… n e }对于 G 中的每条边 e ∈ E 都赋予权ω（i e ）>0，求生成树 T = （V ,H ），H ? E ，使生成树所有边权最小，此生成树称为最小生成树． （1） 基本回路 将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝．将任一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为()cf e 。 基本回路是由 T 中的树枝和一条连枝构成的回路． （2） 基本割集 设无向图 G 的割集 S （割集是把连通图分成两个分离部分的最少支路集合） ，若 S 中仅包含有T 中的一条树枝，则称此割集为基本割集，记为()S e 。 基本割集是集合中的元素只有一条是树枝，其他的为连枝． （3） 等长变换 设T=(V,H),为一棵生成树，e ∈ H, 'e ∈ E, 'e ? H,当且仅当'e ∈()cf e ，也就是说 e ∈()S e ，则'T =T ⊕{e, ' e }也是一棵生成树。当()e ω='()e ω时，这棵生成树叫做等长变换。 等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树． 根据以上定理得出2个结论：①若在某个回路C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；②若在某个边 e 的割集中有一条唯一最短边，则每棵生成树中都必须含这条边．由上面结论可以得到唯一性：若图 G 中的生成树T = （V ,H ）是唯一的一棵最小生成树，当且仅当任意一连枝e ∈ H, ' e ∈ E 都是其基本回路中唯一最长边，任意一条树边 e 都是其基本割集()S e 中的唯一最短边．最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
最小生成树算法分析
最小生成树在旅游路线选择中的应用概况
最小生成树的Kruskal算法实现
最小生成树经典算法
课程设计---克鲁斯卡尔算法求最小生成树
最小生成树(Prim、Kruskal算法)整理版
最小生成树的应用
(完整word版)实验5 最小生成树算法的设计与实现(报告)
PRIM算法求最小生成树
【开题报告】最小生成树算法及其应用
Kruskal算法求最小生成树(java)
最小生成树和最短路径数据结构实验
数据结构课程设计报告最小生成树Kruskal算法[1]4545
改进的最小生成树算法.
克鲁斯卡尔算法求最小生成树
最小生成树的算法
相关文档
- 最小生成树的Kruskal算法
- 最小生成树算法分析
- 最小生成树(Kruskal算法)
- 最小生成树算法详解ppt课件
- 算法合集之《最小生成树问题的拓展》
- 最小生成树的几个算法
- 最小生成树(Prim、Kruskal算法)整理版
- 最小生成树的算法
- 数学建模-最小生成树-kruskal算法及各种代码
- 算法合集之《最小生成树算法及其应用》
- 最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
- Kruskal算法求最小生成树(java)
- 一种基于二进制编码的最小生成树算法
- 最小生成树算法
- 最小生成树及其算法
- 最小生成树经典算法
- c语言实现最小生成树算法
- 改进的最小生成树算法.
- 最小生成树算法(一)
- 最小生成树算法