图的最小生成树算法
‘壹’ 图所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树.
•普里姆（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的最小生成树。
注意：1.最小生成树不唯一。
2.该图从节点最小开始。
‘贰’ 克鲁斯卡尔算法求最小生成树
克鲁斯卡尔算法的基本思想，这是我自己结合教材理解的，难免有误，谨慎参考：
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：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：
‘叁’ 怎么求一幅图像的最小生成树
两种算法：
举例说明：给出下图计算其最小生成树。
‘肆’ C语言（关于图最小生成树方法）
/*
邻接矩阵存储图
测试数据
610
126
131
145
235
253
345
356
364
462
566
*/
#include<stdio.h>
#include<limits.h>
#defineN100
intp[N],key[N],tb[N][N];
voidprim(intv,intn)
{
inti,j;
intmin;
for(i=1;i<=n;i++)
{
p[i]=v;
key[i]=tb[v][i];
}
key[v]=0;
for(i=2;i<=n;i++)
{
min=INT_MAX;
for(j=1;j<=n;j++)
if(key[j]>0&&key[j]<min)
{
v=j;
min=key[j];
}
printf("%d%d",p[v],v);
key[v]=0;
for(j=1;j<=n;j++)
if(tb[v][j]<key[j])
p[j]=v,key[j]=tb[v][j];
}
}
intmain()
{
intn,m;
inti,j;
intu,v,w;
while(scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
tb[i][j]=INT_MAX;
}
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
tb[u][v]=tb[v][u]=w;
}
prim(1,n);
printf(" ");
}
return0;
}
‘伍’ 最小生成树怎么求
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。
求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。
当一条边（u，v）加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。
伪代码
GenerieMST(G){//求G的某棵MST
T〈-￠； //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算法
procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i];
closest[i]:=v0;
end;
for i:=1 to n-1 do begin
{寻找离生成树最近的未加入顶点 k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k 加入生成树}
{生成树中增加一条新的边 k 到 closest[k]}
{修正各点的 lowcost 和 closest 值}
for j:=1 to n do
if cost[k,j]<lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;
Kruskal算法
按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点 v 所在的集合}
var i:integer;
begin
i:=1;
while (i<=n) and (not v in vset) do inc(i);
if i<=n then find:=i else find:=0;
end;
procere kruskal;
var
tot,i,j:integer;
begin
for 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 begin
i:=find(e[q].v1）;j:=find(e[q].v2）;
if i<>j then begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
C语言代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#defineMAX_VERTEX_NUM20
#defineOK1
#defineERROR0
#defineMAX1000
typedefstructArcell
{
doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
charvexs[MAX_VERTEX_NUM];//节点数组
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;//图的当前节点数和弧数
}MGraph;
typedefstructPnode//用于普利姆算法
{
charadjvex;//节点
doublelowcost;//权值
}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义
typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
charch1;//节点1
charch2;//节点2
doublevalue;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
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[i];
for(i=0;i<G.vexnum;++i)//初始化数组
{
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=MAX;
}
}
cout<<"请输入一条边依附的定点及边的权值："<<endl;
for(k=0;k<G.arcnum;++k)
{
cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
i=LocateVex(G,dgevalue[k].ch1）;
j=LocateVex(G,dgevalue[k].ch2）;
G.arcs[i][j].adj=dgevalue[k].value;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
returnOK;
}
intLocateVex(MGraphG,charch)//确定节点ch在图G.vexs中的位置
{
inta;
for(inti=0;i<G.vexnum;i++)
{
if(G.vexs[i]==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[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
k=Minimum(G,closedge);
cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
{
if(G.arcs[k][j].adj<closedge[j].lowcost)
{
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
}
intMinimum(MGraphG,Closedgeclosedge)//求closedge中权值最小的边，并返回其顶点在vexs中的位置
{
inti,j;
doublek=1000;
for(i=0;i<G.vexnum;i++)
{
if(closedge[i].lowcost!=0&&closedge[i].lowcost<k)
{
k=closedge[i].lowcost;
j=i;
}
}
returnj;
}
voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克鲁斯卡尔算法求最小生成树
{
intp1,p2,i,j;
intbj[MAX_VERTEX_NUM];//标记数组
for(i=0;i<G.vexnum;i++)//标记数组初始化
bj[i]=i;
Sortdge(dgevalue,G);//将所有权值按从小到大排序
for(i=0;i<G.arcnum;i++)
{
p1=bj[LocateVex(G,dgevalue[i].ch1）];
p2=bj[LocateVex(G,dgevalue[i].ch2）];
if(p1!=p2）
{
cout<<"("<<dgevalue[i].ch1<<","<<dgevalue[i].ch2<<","<<dgevalue[i].value<<")"<<endl;
for(j=0;j<G.vexnum;j++)
{
if(bj[j]==p2）
bj[j]=p1;
}
}
}
}
voidSortdge(Dgevalue&dgevalue,MGraphG)//对dgevalue中各元素按权值按从小到大排序
{
inti,j;
doubletemp;
charch1,ch2;
for(i=0;i<G.arcnum;i++)
{
for(j=i;j<G.arcnum;j++)
{
if(dgevalue[i].value>dgevalue[j].value)
{
temp=dgevalue[i].value;
dgevalue[i].value=dgevalue[j].value;
dgevalue[j].value=temp;
ch1=dgevalue[i].ch1;
dgevalue[i].ch1=dgevalue[j].ch1;
dgevalue[j].ch1=ch1;
ch2=dgevalue[i].ch2;
dgevalue[i].ch2=dgevalue[j].ch2;
dgevalue[j].ch2=ch2;
}
}
}
}
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[i][j].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;
var
a:array[0..100000] of record
s,t,len:longint;
end;
fa,r:array[0..10000] of longint;
n,i,j,x,y,z:longint;
tot,ans:longint;
count,xx:longint;
procere quick(l,r:longint);
var
i,j,x,y,t:longint;
begin
i:=l;j:=r;
x:=a[(l+r) div 2].len;
repeat
while x>a[i].len do inc(i);
while x<a[j].len do dec(j);
if i<=j then
begin
y:=a[i].len;a[i].len:=a[j].len;a[j].len:=y;
y:=a[i].s;a[i].s:=a[j].s;a[j].s:=y;
y:=a[i].t;a[i].t:=a[j].t;a[j].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;
begin
if fa[x]<>x then fa[x]:=find(fa[x]);
find:=fa[x];
end;
procere union(x,y:longint);{启发式合并}
var
t:longint;
begin
x:=find(x);
y:=find(y);
if r[x]>r[y] then
begin
t:=x;x:=y;y:=t;
end;
if r[x]=r[y] then inc(r[x]);
fa[x]:=y;
end;
begin
readln(xx,n);
for i:=1 to xx do fa[i]:=i;
for i:=1 to n do
begin
read(x,y,z);
inc(tot);
a[tot].s:=x;
a[tot].t:=y;
a[tot].len:=z;
end;
quick（1,tot);{将边排序}
ans:=0;
count:=0;
i:=0;
while count<=x-1 do{count记录加边的总数}
begin
inc(i);
with a[i] do
if find(s)<find(t) then
begin
union(s,t);
ans:=ans+len;
inc(count);
end;
end;
write(ans);
end.
Prim
var
m,n:set of 1..100;
s,t,min,x,y,i,j,k,l,sum,p,ii:longint;
a:array[1..100,1..100]of longint;
begin
readln(p);
for ii:=1 to p do
begin
k:=0; sum:=0;
fillchar(a,sizeof(a),255);
readln(x);
m:=[1];
n:=[2..x];
for i:=1 to x do
begin
for j:=1 to x do
begin
read(a[i,j]);
if a[i,j]=0
then a[i,j]:=maxlongint;
end;
readln;
end;
for l:=1 to x-1 do
begin
min:=maxlongint;
for i:=1 to x do
if i in m
then begin
for j:=1 to x do
begin
if (a[i,j]<min)and(j in n)
then begin
min:=a[i,j];
s:=i;
t:=j;
end;
end;
end;
sum:=sum+min;
m:=m+[t];
n:=n-[t];
inc(k);
end;
writeln(sum);
end;
end.
‘陆’ 怎么求最小生成树 （离散数学 图论）
1） 树是无回路的连通图。
2）对于某个图，求它的最小生成树，比较简单的方法，先画出图中所有节点，从权值最小的边开始依次连接顶点，注意不要形成回路，最后得到的图就是最小生成树。
‘柒’ 图的最小生成树算法
图的生成树和最小生成树生成树(SpanningTree):如果一个图的子图是一个包含图所有节点的树,那这个子图就称为生成树.
‘捌’ 求图的生成树的算法有哪些
在图论中，对于这种权值固定且为正的连通图来说，有比较成熟的最小生成树算法。如着名的Prim算法和Kruskal算法，这两个算法都是贪心算法的例子Prim算法的时间复杂度为 ，适合求边稠密的网络图的最小生成树；Kruskal算法的时间复杂度为 ，适合求边稀疏的网络图的最小生成树。
‘玖’ 数据结构（十）：最小生成树
最小生成树是带权无向连通图中权值最小的生成树，根据 图 中生成树定义可知， 个顶点的连通图中，生成树中边的个数为 ，向生成树中添加任意一条边，则会形成环。生成树存在多种，其中权值之和最小的生成树即为最小生成树。
若 为最小生成树 的一个真子集，即 的顶点集合和边集合都是 的顶点和边集合的子集，构造最小生成树过程为向 中添加顶点和边，添加的原则有两种：
kruskal 算法即为上述第一种原则，通过选择图中的最小权值边来构造最小生成树，过程中需要注意避免形成环。
step 1：
最小权值边为顶点 7、8 形成的边
step 2：
最小权值边为顶点 3、9 形成的边
step 3：
最小权值边为顶点 6、7 形成的边
step 4：
最小权值边为顶点 3、6 形成的边
step 5：
最小权值边为顶点 1、2 形成的边
step 6：
最小权值边为顶点 3、4 形成的边
step 7：
最小权值边为顶点 1、8 形成的边
step 8：
最小权值边为顶点 4、5 形成的边
最小生成树的权值之和为 37
这里使用邻接表作为图的存储结构
这里使用 getEdgesFromAdjacencyList 函数完成邻接表到边集合的转换，使用快排 sort 完成对边集合的排序，使用 origin 函数返回每个子图的根。
该函数返回顶点 index 所属子图的根顶点，其中 vertices[index] 位置上存储的是顶点 index 的上一个顶点，每个子图中，根顶点的上一个顶点为自身。
kruskal 算法中使用 getEdgesFromAdjacencyList 函数完成邻接表向边集合的转换，函数内部存在两层循环，访问邻接表中每个顶点的相邻顶点，复杂度为 。使用快排对边集合进行排序，时间复杂度为 ，因为 ，所以快排时间复杂度可以表述为 。 kruskal 算法中 while 循环取最小权值边，并对边的两个顶点执行 origin 函数判断是否属于同一个子图，时间复杂度为 。所以 kruskal 算法的时间复杂度为 。
kruskal 算法的过程为不断对子图进行合并，直到形成最终的最小生成树。 prim 算法的过程则是只存在一个子图，不断选择顶点加入到该子图中，即通过对子图进行扩张，直到形成最终的最小生成树。
step 1：
距离子图的最近顶点为 4
step 2：
距离子图的最近顶点为 3
step 3：
距离子图的最近顶点为 9
step 4：
距离子图的最近顶点为 6
step 5：
距离子图的最近顶点为 7
step 6：
距离子图的最近顶点为 8
step 7：
距离子图的最近顶点为 2
step 8：
距离子图的最近顶点为 1
最小生成树的权值之和为 37
这里使用邻接表作为图的存储结构
这里使用 vertices 列表存储每个顶点元素，每个元素包括两个属性， index 为顶点下标， weight 为顶点距离子图的大小。算法中使用 verticesIndex 列表存储每个顶点元素在 vertices 列表中的下标位置。使用 heapSort 堆排序对每个顶点到子图的距离进行排序，即对 vertices 列表进行排序，使用堆排序内的 transformToHeap 函数调整 vertices 列表为小顶堆。当添加新顶点到子图后，使用 updateVertices 函数完成对相邻顶点的距离更新。
当 vertices 列表调整为小顶堆之后，将列表首、尾元素交换，则列表尾元素即为距离子图最近的顶点元素。
对每一个相邻顶点，如果不在子图中，则判断是否更新到子图的距离。更新距离后的 while 循环操作，目的为调整堆结构为小顶堆。
prim 算法中构造顶点列表的时间复杂度为 。使用堆排序对顶点列表进行排序，时间复杂度为 。 prim 算法中 while 循环取最近顶点元素，并调整元素取出后列表的堆结构，所以调整复杂度为 ；同时，循环结构内执行 updateVertices 函数，更新每个取出顶点的相邻顶点距离值，所以更新顶点数为 ，因为每个顶点更新距离后，需要调整堆结构为小顶堆，所以更新复杂度为 。所以 prim 算法的总时间复杂度为 。
‘拾’ 最小生成树的两种算法
主要有两个：
1.普里姆（Prim)算法
特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法
特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。