㈠ 最小生成树的定义以及有关算法
Kruskal算法和Prim算法
任何只由G的边构成,并包含G的所有顶点的树称为G的生成树(G连通).
加权无向图G的生成树的代价是该生成树的所有边的代码(权)的和.
最小代价生成树是其所有生成树中代价最小的生成树.
参考代码:
(仅为主程序,更多代码在
http://www.supcoder.cn/bbs/dispbbs.asp?boardID=1&ID=69&page=1
解压密码:www.supcoder.cn )
#include "Sets.h"
#include "themap.h"
#include "windows.h"
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
/*
功能:
演示Kruskal算法和Prim算法
集合的并,元素查找的操作及应用
说明:
代码均在vc++6.0环境下编译均通过
在非VC++6.0环境下编译请去掉头文件 windows.h 和函数 end()
如果NULL未定义请自定义
#define NULL 0 或
#define NULL ((void*)0)
作者:
hacker
时间:
2007.2.3
*/
const VSIZE = 7;//7个顶点
const INFINITY = 10000;//10000作为无穷大来处理
void LoadData(int cost[][VSIZE+1], Edge edge[]);
void end();
/*
函数名:
Kruskal 和 Prim
参数:
边,代价,边数,顶点数,最小代价生成树的顶点
返回值:
返回值为-1,不存在最小代价生成树
返回值大于0时为最小代价生成树的代价
最小代价生成树的边在vector<Edge>& t
*/
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);
int Prim (Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);
int main()
{
int cost[VSIZE+1][VSIZE+1];//0不用
Edge edge[9];//9条边
vector<Edge> t;//用来存储最小代价生成树的顶点
int mincost;//最小代价
LoadData(cost, edge);
if ( (mincost = Kruskal(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代价是:"<<mincost<<endl<<"边是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}
t.clear();
if ( (mincost = Prim(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代价是:"<<mincost<<endl<<"边是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}
end();
return 1;
}
void LoadData(int cost[][VSIZE+1], Edge edge[])
{
edge[0].u = 1; edge[0].v = 2; edge[0].weight = 28;
edge[1].u = 1; edge[1].v = 6; edge[1].weight = 10;
edge[2].u = 2; edge[2].v = 3; edge[2].weight = 16;
edge[3].u = 2; edge[3].v = 7; edge[3].weight = 14;
edge[4].u = 3; edge[4].v = 4; edge[4].weight = 12;
edge[5].u = 4; edge[5].v = 5; edge[5].weight = 22;
edge[6].u = 4; edge[6].v = 7; edge[6].weight = 18;
edge[7].u = 5; edge[7].v = 6; edge[7].weight = 25;
edge[8].u = 5; edge[8].v = 7; edge[8].weight = 24;
for (int i=1;i<=7;i++)
for (int j=1;j<=i;j++)
cost[i][j] = cost[j][i] = INFINITY;
for (i=0;i<9;i++)
cost[edge[i].u][edge[i].v] =
cost[edge[i].v][edge[i].u] = edge[i].weight;
}
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t)
{
Sets s(esize);
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
int mincost = 0;
for (int i = 0;i<esize;i++)
//把所有的边放入优先队列
pq.push(edge[i]);
i = 0;
while (i<vsize-1 && !pq.empty())
{
Edge temp = pq.top();//取出当前权最小的边
pq.pop();
int j = s.SimpleFind(temp.u);
int k = s.SimpleFind(temp.v);
if (j!=k)//如果不构成环
{
i++;
t.push_back(temp);
mincost +=cost[temp.u][temp.v];
s.SimpleUnion(j, k);
}
}
if (i!=vsize-1)
{
t.clear();
return -1;
}
else
{
return mincost;
}
}
int Prim(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t)
{
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
vector<Edge> sortededge;
int i;
for (i =0;i<esize;i++)
pq.push(edge[i]);
for (i =0;i<esize;i++)
{//对边进行从小到大排列,放到sortededge中
sortededge.push_back(pq.top());
pq.pop();
}
int distance[VSIZE+1];
int j;
int mincost = sortededge[0].weight;
Edge temp = sortededge[0];
t.push_back(temp);
for (i=1;i<=vsize;i++)
distance[i] = 1;//每个点都不在已生成树里
distance[temp.u] = distance[temp.v] = 0;//最短的边的两个点放到生成树里
for (i=2;i<=vsize-1;i++)
{//寻找另外的边
int exist = 0;//设置是否找到符合条件的边的状态标志为未找到
for (j=1;j<esize;j++)
if (distance[sortededge[j].u] ^ distance[sortededge[j].v] == 1)
{//由于边是排序好了的,所以从小边向大边找,找到的第一个符合条件的边可以
//加到生成树里
int k = (distance[sortededge[j].u] == 0) ? sortededge[j].v :\
sortededge[j].u;
distance[k] = 0;
mincost += sortededge[j].weight;
t.push_back(sortededge[j]);
exist = 1;
break;
}
if (!exist)
{
t.clear();
return -1;
}
}
return mincost;
}
void end()
{
if (MessageBox(NULL,\
"欢迎到http://www.supcoder.cn学习交流(源代码在论坛下载)\n\t\t(确定后自动访问论坛)",\
"supcoder", IDOK) == IDOK)
{
char cmdLine[] = "iexplore http://www.supcoder.cn/bbs";
char path[256];
char buf[256];
STARTUPINFO si;
ZeroMemory(&si, sizeof(si));
PROCESS_INFORMATION ProcessInformation;
GetSystemDirectory(buf, 256);
sprintf(path, "%c:\\Program Files\\Internet Explorer\\IEXPLORE.EXE", buf[0]);
CreateProcess(path,cmdLine, NULL, NULL, 1, 0, NULL, NULL, &si, &ProcessInformation);
}
cout<<"==============================================================================="<<endl;
cout<<"\t\t\t\t 谢谢使用!"<<endl;
cout<<"\t\t\t http://www.supcoder.cn"<<endl;
Sleep(1000);
}
㈡ 数据结构（十）：最小生成树
最小生成树是带权无向连通图中权值最小的生成树，根据 图 中生成树定义可知， 个顶点的连通图中，生成树中边的个数为 ，向生成树中添加任意一条边，则会形成环。生成树存在多种，其中权值之和最小的生成树即为最小生成树。
若 为最小生成树 的一个真子集，即 的顶点集合和边集合都是 的顶点和边集合的子集，构造最小生成树过程为向 中添加顶点和边，添加的原则有两种：
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 算法的总时间复杂度为 。
㈢ 最小生成树怎么求
一个有 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.普里姆（Prim)算法
特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法
特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。
㈤ 最小生成树的两种算法
主要有两个：
1.普里姆（Prim)算法
特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法
特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。
㈥ 图的最小生成树算法
图的生成树和最小生成树生成树(SpanningTree):如果一个图的子图是一个包含图所有节点的树,那这个子图就称为生成树.
㈦ 最小生成树
最小生成树算法.可以用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=0; j<G.vexnum; ++j ) // 辅助数组初始化
if (j!=k)
closedge[j] = { u, G.arcs[k][j] };
closedge[k].Lowcost = 0; // 初始，U＝{u}
for ( i=0; i<G.vexnum; ++i )
{
继续向生成树上添加顶点；
}
k = minimum(closedge); // 求出加入生成树的下一个顶点(k)
printf(closedge[k].Adjvex, G.vexs[k]); // 输出生成树上一条边
closedge[k].Lowcost = 0; // 第k顶点并入U集
for (j=0; j<G.vexnum; ++j) //修改其它顶点的最小边
if ( G.arcs[k][j] < closedge[j].Lowcost )
closedge[j] = { G.vexs[k], G.arcs[k][j] };
}
㈧ 图的相关算法（二）：最小生成树算法
在含有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。