最小生成樹演算法

㈠ 最小生成樹演算法源程序

#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;
}