最小生成树算法

㈠ 最小生成树算法源程序

#include <stdio.h>
#include <stdlib.h>typedef struct{
int vexnum;//点数量
int arcnum;//边数量
int **arcs;//边指针
char *vexs;//点名称
}iGraph;
typedef struct close{
int adjvex;//
int endvex;//
int lowcost;//最小权值
}*closedge,closedges;void CreateUDN(iGraph &G);//创建无向图
int LocateVex(iGraph G,char v);//节点的顶点向量中的下标
void PrintUDN(iGraph G);//输出存储结构示意图
void MiniSpanTree_PRIM(iGraph G,closedge &minedge);//求最小生成树的算法
void PrintMinEdge(iGraph G,closedge minedge);//输出最小生成树的边
int main()
{iGraph G;<br>closedge minedge;</p><p> CreateUDN(G);<br> printf("\n");<br> MiniSpanTree_PRIM(G,minedge);<br> PrintMinEdge(G,minedge);<br> printf("\n");<br> return 0;<br>}void CreateUDN(iGraph &G)
{int i,j,k,l,cost;<br> char name1,name2;</p><p> printf("请输入顶点数和边数，且边数大于或等于顶点数，用空格符隔开：\n");<br> scanf("%d %d",&G.vexnum,&G.arcnum);<br> getchar();<br> G.vexs=(char *)malloc(G.vexnum*sizeof(char));//开辟空间<br> for(i=0;i<G.arcnum;i++)<br> G.arcs=(int **)malloc(G.arcnum*sizeof(int *));<br> for(i=0;i<G.arcnum;i++)<br> G.arcs[i]=(int *)malloc(G.arcnum*sizeof(int));<br> printf("请输入各顶点名字，回车确认：\n");<br> for(i=0;i<G.vexnum;i++)<br> {scanf("%c",&G.vexs[i]);<br> getchar();}
printf("请输入图中各边。按回车结束一条边的输入，输入结束后按回车执行，输入格式为：“端点1-端点2-权值”：\n"); for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=100000; //使边的权值初始化为最大

for(i=0;i<G.arcnum;i++)
{
scanf("%c-%c-%d",&name1,&name2,&cost);
getchar();
for(j=0;j<G.vexnum;j++)//在表中查找点
{ if(name1==G.vexs[j])
k=j;
if(name2==G.vexs[j])
l=j;
}
if(k==l)//两个点如果相同，报错
{i--;<br> printf("输入错误的数据,请重新输入\n");<br> continue;<br> } G.arcs[k][l]=cost;//无向边赋权值
G.arcs[l][k]=cost;
}//使输入的边赋值 for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
if(i==j)
G.arcs[i][j]=0;//如果端点相同，则不存在边
}int LocateVex(iGraph G,char v)//节点的顶点向量中的下标
{int i,m;<br> for(i=0;i<G.vexnum;i++)<br> if(v==G.vexs[i])<br> m=i;<br> return m;<br>}void PrintUDN(iGraph G)//打印模块
{int i,j;<br> printf("对应的矩阵为\n");<br> printf(" ");<br> for(i=0;i<G.vexnum;i++)<br> printf("\t%c ",G.vexs[i]);<br> printf("\n");<br> for(i=0;i<G.vexnum;i++)<br> {<br> for(j=0;j<G.vexnum+1;j++)<br> { <br> if(j==0)<br> printf("%c\t",G.vexs[i]);<br> else<br> if(G.arcs[i][j-1]==100000)//如果没有被赋值，即ij两点不连通<br> printf("NO\t");<br> else<br> printf("%d\t",G.arcs[i][j-1]);<br> }
printf("\n");
}
}void MiniSpanTree_PRIM(iGraph G,closedge &minedge)//最小生成树
{ int i,j,k,z;
int temp;
int currentmin;
k=0;
minedge=(closedge)malloc((G.vexnum+1)*sizeof(closedges));
for(j=1;j<G.vexnum;j++)
{
minedge[j-1].adjvex=k;
minedge[j-1].endvex=j;
minedge[j-1].lowcost=G.arcs[k][j];
}
for(i=0;i<G.vexnum-1;i++)
{ currentmin=minedge[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum-1;j++)
{
if(minedge[j].lowcost<currentmin)
{currentmin=minedge[j].lowcost;<br> k=j;<br> }
}
//第K个元素和第I个元素交换
temp=minedge[i].adjvex;
minedge[i].adjvex=minedge[k].adjvex;
minedge[k].adjvex=temp;
temp=minedge[i].endvex;
minedge[i].endvex=minedge[k].endvex;
minedge[k].endvex=temp;
temp=minedge[i].lowcost;
minedge[i].lowcost=minedge[k].lowcost;
minedge[k].lowcost=temp; for(j=i+1;j<G.vexnum-1;j++)
{
z=minedge[i].endvex;//Z为新找到的顶点
k=minedge[j].endvex;
if(k!=z)
{
if(G.arcs[z][k]<minedge[j].lowcost)
{
minedge[j].adjvex=z;
minedge[j].lowcost=G.arcs[z][k];//和以前的节点比较，如果边的权值小，则，即选取已有的结点中权值最小的边
}
}
}
}
}
void PrintMinEdge(iGraph G,closedge minedge)
{int i,sum;<br>sum=0;<br> printf("最小生成树对应的边为\n");<br> for(i=0;i<G.vexnum-1;i++)<br> {<br> printf("%c-%c:权值为：%d\n",G.vexs[minedge[i].adjvex],G.vexs[minedge[i].endvex],minedge[i].lowcost);<br> sum=sum+minedge[i].lowcost;<br> }
printf("最小生成树的权值为：%d",sum);
}

㈡ 最小生成树

最小生成树算法.可以用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] };
}

㈢ 最小生成树存在线性算法吗

对于最小生成树的两种算法
kruskal算法：如果在排序的时候使用线性排序算法，比如基数排序之类的，也勉强可以算是线性吧
prim算法：如果使用斐波那契堆或者配对堆，最低可以实现O(nlgn+m)的时间复杂度，已经和线性相差不远了

㈣ 最小生成树两种算法有何区别

主要有两个：
1.普里姆（Prim)算法

特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法

特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。

㈤ 图的最小生成树算法

图的生成树和最小生成树生成树(SpanningTree):如果一个图的子图是一个包含图所有节点的树,那这个子图就称为生成树.

㈥ 最小生成树怎么求

一个有 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.

㈦ 最小生成树的算法描述

求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。
当一条边（u，v）加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。 1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew= {x}，其中x为集合V中的任一节点（起始点），Enew= {},为空；
3).重复下列操作，直到Vnew= V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。 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）。 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]; a[i]:=a[j]; a[j]:=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 exit(x);
fa[x]:=find(fa[x]);{路径压缩}
exit(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. 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. //maxe保存了最大边数structedge{intu,v,w;booloperator<(constedge&b)const{returnthis->w>b.w;}}e[maxe];//并查集相关intf[maxn];inlinevoidinit(){for(inti=0;i<maxn;i++)f[i]=i;}intfind(intx){if(f[x]==x)returnx;elsereturnf[x]=find(f[x]);}//主算法intkruskal(intn,intm){//n:点数,m:边数//所有边已经预先储存在e数组里sort(e,e+m);init();intans=0;for(inti=0;i<m;i++){intu=e[i].u,v=e[i].v,w=e[i].w;if(find(u)==find(v))continue;f[find(u)]=find(v);ans+=w;}returnans;}

㈧ 急！数据结构最小生成树prim算法C语言实现

Kruskal算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化辅助数组
k=1; //k表示当前构造最小生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<n) //生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v; //取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成边数增1
for (i=0;i<n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
}
Prim算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1个顶点
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 边(%d,%d)权为:%d/n",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<n;j++) //修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}

㈨ 最小生成树一共有几种算法

Prim算法和Kruskal算法

㈩ 最小生成树算法，急！

已编译确认，编译环境vs2005/dev-cpp
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<conio.h>
#include<math.h> /* floor(),ceil(),abs() */

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
/*图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作*/
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
Status CreateAN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造无向网G。*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 无向 */
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */
}
}
}
(*G).kind=AN;
return OK;
}
typedef struct
{ /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int minimum(minside SZ,MGraph G)
{ /* 求closedge.lowcost的最小正值 */
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost; /* 第一个不为0的值 */
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{ /* 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边*/
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j) /* 辅助数组初始化 */
{
if(j!=k)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0; /* 初始,U={u} */
printf("最小代价生成树的各条边为:\n");
for(i=1;i<G.vexnum;++i)
{ /* 选择其余G.vexnum-1个顶点 */
k=minimum(closedge,G); /* 求出T的下一个结点：第K顶点 */
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); /* 输出生成树的边 */
closedge[k].lowcost=0; /* 第K顶点并入U集 */
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{ /* 新顶点并入U集后重新选择最小边 */
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}

int main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
getch();
return 0;
}