在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
例如，对于上图中的连通网可以有多棵权值总和不相同的生成树。
克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法。
基本思想 ：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法 ：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林中，并使得森林不产生回路，直到森林变成一棵树为止。
以图G4为例（更详细的可以参考《算法导论》p367），对Kruskal进行演示（假设，用数组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。
最小生成树算法.可以用PRIM算法....你简单看看普里姆(Prim)算法
（1）算法思想 通过每次添加一个新节点加入集合，直到所有点加入停止的最小生成树的算法
原理：每次连出该集合到其他所有点的最短边保证生成树的边权总和最小
1. 首先随便选一个点加入集合
2. 用该点的所有边去刷新到其他点的最短路
3. 找出最短路中最短的一条连接（且该点未被加入集合）
4. 用该点去刷新到其他点的最短路
5 重复以上操作n-1次
6 最小生成树的代价就是连接的所有边的权值之和
void MiniSpanTree_P( MGraph G, VertexType u )
{
//用普里姆算法从顶点u出发构造网G的最小生成树
k = LocateVex ( G, u )
for ( j=0j<G.vexnum++j ) // 辅助数组初始化
if (j!=k)
closedge[j] = { u, G.arcs[k][j] }
closedge[k].Lowcost = 0// 初始，U＝{u}
for ( i=0i<G.vexnum++i )
{
继续向生成树上添加顶点；
}
k = minimum(closedge) // 求出加入生成树的下一个顶点(k)
printf(closedge[k].Adjvex, G.vexs[k]) // 输出生成树上一条边
closedge[k].Lowcost = 0// 第k顶点并入U集
for (j=0j<G.vexnum++j) //修改其它顶点的最小边
if ( G.arcs[k][j] <closedge[j].Lowcost )
closedge[j] = { G.vexs[k], G.arcs[k][j] }
}
一个有 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算法
procedure 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
procedure kruskal
var
tot,i,j:integer
begin
for i:=1 to n do vset:=i{初始化定义 n 个集合，第 I个集合包含一个元素 I}
p:=n-1q:=1tot:=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=0i<G.vexnum++i)
cin>>G.vexs[i]
for(i=0i<G.vexnum++i)//初始化数组
{
for(j=0j<G.vexnum++j)
{
G.arcs[i][j].adj=MAX
}
}
cout<<"请输入一条边依附的定点及边的权值："<<endl
for(k=0k<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=0i<G.vexnumi++)
{
if(G.vexs[i]==ch)
a=i
}
returna
}
voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆算法求最小生成树
{
inti,j,k
Closedgeclosedge
k=LocateVex(G,u)
for(j=0j<G.vexnumj++)
{
if(j!=k)
{
closedge[j].adjvex=u
closedge[j].lowcost=G.arcs[k][j].adj
}
}
closedge[k].lowcost=0
for(i=1i<G.vexnumi++)
{
k=Minimum(G,closedge)
cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl
closedge[k].lowcost=0
for(j=0j<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=0i<G.vexnumi++)
{
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=0i<G.vexnumi++)//标记数组初始化
bj[i]=i
Sortdge(dgevalue,G)//将所有权值按从小到大排序
for(i=0i<G.arcnumi++)
{
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=0j<G.vexnumj++)
{
if(bj[j]==p2）
bj[j]=p1
}
}
}
}
voidSortdge(Dgevalue&dgevalue,MGraphG)//对dgevalue中各元素按权值按从小到大排序
{
inti,j
doubletemp
charch1,ch2
for(i=0i<G.arcnumi++)
{
for(j=ij<G.arcnumj++)
{
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=0i<G.vexnumi++)
{
for(j=0j<G.vexnumj++)
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
procedure quick(l,r:longint)
var
i,j,x,y,t:longint
begin
i:=lj:=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].lena[i].len:=a[j].lena[j].len:=y
y:=a[i].sa[i].s:=a[j].sa[j].s:=y
y:=a[i].ta[i].t:=a[j].ta[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
procedure union(x,y:longint){启发式合并}
var
t:longint
begin
x:=find(x)
y:=find(y)
if r[x]>r[y] then
begin
t:=xx:=yy:=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:=0sum:=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.
