最小生成樹演算法實現

⑴ 急！數據結構最小生成樹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;
}
}
}

⑵ sh實現最小生成樹和最短路徑的演算法

圖的最小生成樹與最短路徑的演算法

一、圖的生成樹與最小生成樹
在一個連通圖G中，如果取它的全部頂點和一部分邊構成一個子圖G』，即：

若邊集E（G』）中的邊既將圖中的所有頂點連通又不形成迴路，則稱子圖G』是原圖G的一棵生成樹。
最小生成樹：給圖中每個邊賦一權值，所有生成樹中所選擇邊的權值之和最小的生成樹，稱之為最小代價生成樹，即是最小生成樹。

1、普里姆演算法
1.1演算法描述
假設G=（V, E）是一個具有n個頂點的連通網，T=（U, TE）是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，U和TE的初值均為空集。演算法開始時，首先從V中任取一個頂點（假定取v1），將它並入U中，此時U={v1}，然後只要U是V的真子集（即），就從那些其一個端點已在T中，另一個端點仍在T外的所有邊中，找一條最短（即權值最小）邊，假定為（vi, vj），其中，並把該邊（vi, vj）和頂點vj分別並入T的邊集TE和頂點集U，如此進行下去，每次往生成樹里並入一個頂點和一條邊，直到（n-1）次後就把所有n個頂點都並入到生成樹T的頂點集中，此時U＝V，TE中含有（n-1）條邊，T就是最後得到的最小生成樹。 1.2關鍵問題
普里姆演算法的關鍵之處是：每次如何從生成樹T中到T外的所有邊中，找出一條最短邊。例如，在第k次前，生成樹T中已有k個頂點和（k-1）條邊，此時T中到T外的所有邊數為k（n-k），當然它包括兩頂點間沒有直接邊相連，其權值被看作為「無窮大」的邊在內，從如此多的邊中查找最短邊，其時間復雜性為O（k（n-k）），顯然是很費時的。是否有一種好的方法能夠降低查找最短邊的時間復雜性呢？ 1.3 解決方法
方法是：假定在進行第k次前已經保留著從T中到T外每一頂點（共（n-k）個頂點）的各一條最短邊，進行第k次時，首先從這（n-k）條最短邊中，找出一條最最短的邊（它就是從T中到T外的所有邊中的最短邊），假設為（vi, vj），此步需進行（n-k）次比較；然後把邊（vi, vj）和頂點vj分別並入T中的邊集TE和頂點集U中，此時T外只有n-（k+1）個頂點，對於其中的每個頂點vt，若（vj, vt）邊上的權值小於已保留的從原T中到vt的最短邊的權值，則用（v, vt）修改之，使從T中到T外頂點vt的最短邊為（vj, vt），否則原有最短邊保持不變，這樣，就把第k次後從T中到T外每一頂點vt的各一條最短邊都保留下來了。為進行第（k+1）次運算做好了准備，此步需進行（n-k-1）次比較。所以，利用此方法求第k次的最短邊共需比較2（n-k）-1次，即時間復雜性為O（n-k）。
1.4 prim演算法：
設一個輔助數組closedge，以記錄從U到V—U具有最小代價的邊。數組中的每個元素closedge[v]是記錄類型，包含兩個域： closedge[v].lowcast=Min{cost(u,v)|u∈U}; closedge[v].vex存儲該邊依附的在U中的頂點。
proc mintree_prim(gn:adjmatrix;u0:integer);
begin
for v:=1 to n do
if v<>u0 then
with closedage[v] do [vex:=u0; lowcast:=gn[u0,v];]
closedge[u0].lowcast:=0;{並入U集合}
for i:=1 to n-1 do
begin
v:=min(closedge);{尋找代價最小的邊}
write(closedge[v].vex,v); closedge[v].lowcast:=0;{並入U集合}
for k:=1 to n do
if gn[v,k]<closedge[k].lowcast then
begin closedge[k].lowcast:=gn[v,k]; closedge[k].vex:=v; end;
end;
end; 練習1：prim演算法實現
【問題描述】從文件中讀入連通帶權圖的信息，按prim演算法求出該圖的最小生成樹，以V1作為初始結點。
【輸入文件】第一行兩個整數m和n，分別表示圖的結點數和圖中的邊數。以下n行表示n條邊：每一行三個數x、y和k，k表示x與y之間邊的權值。
【輸出文件】共m行，第一行：最小生成樹的權；以下m-1行表示選取的邊，邊的第1個結點小於第2個結點，並按結點由小到大輸出。
【示例】輸入：5 7 輸出：45
1 2 17 1 4
2 3 30 1 5
1 4 5 2 4
2 4 10 3 5
3 4 24
3 5 7
1 5 23

練習2： Eddy painting
Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result it can be imagined, the friends are not interested in his picture.Eddy feels very puzze,in order to change all friends 's view to his technical of painting pictures ,so Eddy creates a problem for the his friends of you.
Problem descriptions as follows: Given you some coordinates pionts on a drawing paper, every point links with the ink with the straight line, causes all points finally to link in the same place. How many distants does your ty discover the shortest length which the ink draws?
Input：
The first line contains 0 < n <= 100, the number of point. For each point, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the point.

Input contains multiple test cases. Process to the end of file.
Output：
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the points.
Sample Input：
3
1.0 1.0
2.0 2.0
2.0 4.0
Sample Output：
3.41

2、克魯斯卡爾演算法
2.1 演算法描述
假設G＝（V，E）是一個具有n個頂點的連通網，T＝（U，TE）是G的最小生成樹，U的初值等於V，即包含有G中的全部頂點，TE的初值為空。此演算法的基本思想是，將圖G中的邊按權值從小到大的順序依次選取，若選取的邊使生成樹T不形成迴路，則把它並入TE中，保留作為T的一條邊，若選取的邊使生成樹T形成迴路，則將其舍棄，如此進行下去，直到TE中包含有n-1條邊為止。此時的T即為最小生成樹。
2.2 關鍵問題
克魯斯卡爾演算法的關鍵之處是：如何判斷欲加入的一條邊是否與生成樹中已選取的邊形成迴路。這可將各頂點劃分為所屬集合的方法來解決，每個集合中的頂點表示一個無迴路的連通分量。演算法開始時，由於生成樹的頂點集等於圖G的頂點集，邊集為空，所以n個頂點分屬於n個集合。每個集合中只有一個頂點，表明頂點之問互不連通。
2.3 Kruskal演算法：
proc mintree_krusk(gn:adjmatrix);
begin
for i:=1 to n do
un[i]:=i;
for i:=1 to n-1 do
begin
minedge(a,b);
write(a,b,gn[a,b]);
k:=un[b];
for i:=1 to n do {兩個連通分量合並}
if un[i]=k then un[i]:=un[a];
end;
end;
2.4 注意：
proc minedge(var a:integer;var b:integer);用於在剩下的邊中選取不再同一連通分量上的最小代價的邊，邊的結點分別為a和b。
為了實現該過程，可以將圖中的邊生成一邊結點（包含兩個頂點和代價）數組，由小到大排序，然後通過排序後的數組進行處理；
un數組：用來記載隨著邊的加入，各頂點屬於哪個連通分量。
練習3：Kruskal演算法實現
【問題描述】從文件中讀入連通帶權圖的信息，按Kruskal演算法求出該圖的最小生成樹，以V1作為初始結點。
【輸入文件】第一行兩個整數m和n，分別表示圖的結點數和圖中的邊數。以下n行表示n條邊：每一行三個數x、y和k，k表示x與y之間邊的權值。
【輸出文件】共m行，第一行：最小生成樹的權；以下m-1行表示選取的邊，按選取邊的權值由小到大輸出。
【示例】輸入：5 7 輸出：45
1 2 17 1 4
2 3 30 3 5
1 4 5 2 4
2 4 10 1 5
3 4 24
3 5 7
1 5 23

練習4：判斷最小生成樹是否唯一
Given a connected undirected graph, tell if its minimum spanning tree is unique.
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:
1. V' = V.
2. T is connected and acyclic.

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.
Input
The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.
Output
For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!

二、最短路徑
【問題描述】由於從一頂點到另一頂點可能存在著多條路徑。每條路徑上所經過的邊數可能不同，即路徑長度不同，我們把路徑長度最短（即經過的邊數最少）的那條路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。求圖中一頂點vi到其餘各頂點的最短路徑和最短距離比較容易，只要從該頂點vi，出發對圖進行一次廣度優先搜索遍歷，在遍歷時記下每個結點的層次即可。
若圖是帶權圖（假定權值非負）從源點vi到終點vj的每條路徑上的權（它等於該路徑上所經邊上的權值之和，稱為該路徑的帶權路徑長度）可能不同，我們把權值最小的那條路徑也稱做最短路徑，其權值也稱作最短路徑長度或最短距離。
實際上，這兩類最短路徑問題可合並為一類，這只要把第一類的每條邊的權都設為1就歸屬於第二類了，所以在以後的討論中，若不特別指明，均是指第二類的最短路徑問題。
求圖的最短路徑問題包括兩個子問題：一是求圖中一頂點到其餘各頂點的最短路徑，二是求圖中每對頂點之間的最短路徑。下面分別進行討論。
始點 終點 最短路徑 路徑長度
v0 v1 No path
v2 (v0,v2) 10
v3 (v0,v4,v3) 50
v4 (v0,v4) 30
v5 (v0,v4,v3,v5) 60

始點 終點 最短路徑 路徑長度
v1 V2 (v1,v2) 10
V3 (v1,v2,v3) 27
V4 (v1,v5,v4) 20
v5 (v1,v5) 7

1、從一頂點到其餘各頂點的最短路徑
1.1 描述
迪傑斯特拉（Dijkstra）於1959年提出了解決此問題的一般演算法，具體做法是按照從源點到其餘每一頂點的最短路徑長度的升序依次求出從源點到各頂點的最短路徑及長度，每次求出從源點vi到一個終點vj的最短路徑及長度後，都要以vj作為新考慮的中間點，用vi到vj的最短路徑和最短路徑長度對vi到其它尚未求出最短路徑的那些終點的當前路徑及長度作必要的修改，使之成為當前新的最短路徑和最短路徑長度，當進行n-2次後演算法結束。
1.2 Dijkstra演算法:
首先，引進一個輔助向量dist，dist[i]表示當前所找到的從始點V到每個終點Vi的最短路徑長度。其初態為：若<v,vi>存在，則dist[i]為其上的權值，否則為最大值（計算機能表示）。
演算法:(1)用鄰接矩陣cost表示帶權有向圖。S表示已找到的從v出發的最短路徑的終點的集合，初態為空。dist向量的初值為：dist[v,i]=cost[v,i];
(2)選擇vj，使得：dist[j]=Min{dist[i]|vi∈V-S}；vj就是當前求得從v出發的最短路徑的終點。
S=S+{j};
(3)修改從v出發到集合V-S上任意頂點vk可達的最短路徑長度。
if dist[j]+cost[j,k]<dist[k] then dist[k]:=dist[j]+cost[j,k];
(4)重復(2)(3)共n-1次。
代碼：proc short_dij;
begin
for i:=1 to n do
begin
dist[i]:=cost[v0,i];
if dist[i]<max then path[i]:=v0 else path[i]:=-1; end;
flag[I]:=true;
for k:=1 to n-1 do
begin
wm:=max; j:=v0;
for i:=1 to n do
if not(flag[i]) and (dist[i]<wm) then begin j:=i; m:=dist[i]; end;
flag[j]:=true; for i:=1 to n do if not(flag[i]) and (dist[j]+cost[j,i]<dist[i]) then
begin dist[i]:=dist[j]+cost[j,i]; path[i]:=j; end;
end;
end; 其中：cost：鄰接矩陣；
path[i]：存儲從v0到頂點i的最短路徑；是以集合作為數組元素；
dist[i]：存儲相應路徑長度；
flag[i]：表示已處理的頂點。
練習5：Dijkstra演算法練習
【問題描述】從文件中讀入帶權圖的信息，按Dijkstra演算法根據給定源點求出從源點法到該圖中其餘頂點的最短路徑。
【輸入文件】第一行：一個整數L：L=0表示無向圖，L=1表示有向圖；第二行三個整數m、n和k，分別表示圖的結點數、圖中的邊數以及源點。以下n行表示n條邊：每一行三個數x、y和z，z表示x與y之間邊的權值。
【輸出文件】共m-1行，每一行的數據包括：頂點： 最短路徑：路徑，如果不存在路徑，數據為：頂點：No path。
【示例】輸入：1 輸出：2：No path
6 8 1 3：10：1 3
1 3 10 4：50：1 5 4
1 5 30 5：30：1 5
1 6 100 6：60：1 5 4 6
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
練習6：路由選擇問題
【問題描述】
X城有一個含有N個節點的通信網路，在通信中，我們往往關心信息從一個節點I傳輸到節點J的最短路徑。遺憾的是，由於種種原因，線路中總有一些節點會出故障，因此在傳輸中要避開故障節點。
任務一：在己知故障節點的情況下，求避開這些故障節點，從節點I到節點J的最短路徑S0。
任務二：在不考慮故障節點的情況下，求從節點I到節點J的最短路徑S1、第二最短路徑S2。
【輸入文件】
第1行： N I J (節點個數 起始節點 目標節點)
第2—N+1行： Sk1 Sk2…SkN (節點K到節點J的距離為SkJ K=1，2，……，N)
最後一行： P T1 T2……Tp (故障節點的個數及編號)
【輸出文件】
S0 S1 S2 (S1<=S2 從節點I到節點J至少有兩條不同路徑)
【輸入輸出樣例】
route.in
5 1 5
0 10 5 0 0
10 0 0 6 20
5 0 0 30 35
0 6 30 0 6
0 20 35 6 0
1 2
route.out
40 22 30

2、每對頂點之間的最短路徑
求圖中每對頂點之間的最短路徑是指把圖中任意兩個頂點vi和vj（i≠j）之間的最短路徑都計算出來。解決此問題有兩種方法：一是分別以圖中的每個頂點為源點共調用n次迪傑斯特拉演算法，此方法的時間復雜性為O（n3）；二是採用下面介紹的弗洛伊德（Floyed）演算法，此演算法的時間復雜性仍為O（n3），但比較簡單。 弗洛伊德演算法實際上是一個動態規劃的演算法。從圖的鄰接矩陣開始，按照頂點v1，v2，…，vn的次序，分別以每個頂點vk（1≤k≤n）作為新考慮的中間點，在第k-1次運算Ak-1 （A（0）為原圖的鄰接矩陣G） 的基礎上，求出每對頂點vi到vj的最短路徑長度計算公式為：

Floyd演算法：
proc shortpath_floyd;
begin
for i:=1 to n do for j:=1 to n do
begin
length[i,j]:=cost[i,j];
if length[i,j]<max then path[i,j]:=[i]+[j];
end;
for k:=1 to n do for i:=1 to n do for j:=1 to n do
if length[i,k]+length[k,j]<length[i,j] then
begin
length[i,j]:=length[i,k]+length[k,j];
path[i,j]:=path[i,k]+path[k,j];
end;
end;
其中：cost為鄰接矩陣；
path[i,j]：表示頂點i到j的最短路徑；
length[i,j]：
練習7：Floyd演算法練習
【問題描述】從文件中讀入帶權圖的信息，按Dijkstra演算法根據給定源點求出從源點到該圖中其餘頂點的最短路徑。
【輸入文件】第一行：一個整數L：L=0表示無向圖，L=1表示有向圖；第二行三個整數m、n，分別表示圖的結點數和圖中的邊數。以下n行表示n條邊：每一行三個數x、y和z，z表示x與y之間邊的權值。第n+2行：整數R，以下R行每行一個整數表示頂點標號作為源點。
【輸出文件】共R行，每一行的數據表示源點到其餘頂點的距離，按頂點編號由小大輸出，如果沒有路徑，輸出-1。
【示例】輸入：1 輸出：-1 10 50 30 60
6 8 -1 –1 –1 20 30
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
2
1
5

⑶ 最小生成樹

所謂最小生成樹，就是在一個具有N個頂點的帶權連通圖G中，如果存在某個子圖G'，其包含了圖G中的所有頂點和一部分邊，且不形成迴路，並且子圖G'的各邊權值之和最小，則稱G'為圖G的最小生成樹。 由定義我們可得知最小生成樹的三個性質：
•最小生成樹不能有迴路。
•最小生成樹可能是一個，也可能是多個。
•最小生成樹邊的個數等於頂點的個數減一。宴昌 本文將介紹兩種最小生成樹的演算法，分別為克魯斯卡爾演算法(Kruskal Algorithm)和普利姆演算法(Prim Algorithm)。

克魯斯卡爾演算法的核心思想是：在帶權連通圖中，不斷地在邊集合中找到最小的邊，如果該邊滿足得到最小生成樹的條件，就將其構造，直到最後得到一顆最小生成樹。
克魯斯卡爾演算法的執行步驟：
第一步：在帶權連通圖中，將邊的權值排序；
第二步：判斷是否需要選擇這條邊（此時圖中的邊已按權值從小到大排好序）。判斷的依據是邊的兩個頂點是亂蘆否已連通，如果連通則繼續下一條；如果不連通，那麼就選擇晌陪扒使其連通。
第三步：循環第二步，直到圖中所有的頂點都在同一個連通分量中，即得到最小生成樹。
下面我用圖示法來演示克魯斯卡爾演算法的工作流程，如下圖：

⑷ 最小生成樹解法有哪些

以下是一些最小生成樹的解法

prime演算法的基本思想

1.清空生成樹，任取一個頂點加入生州正成樹

2.在那些一個端點在生成樹里，另一個端點不在生襲畝成樹里的邊中，選取一條權最小的邊，將它和另一個端點加進生成樹

3.重復步驟2，直到所有的頂點都進入了生成樹為止，此時的生成樹就是最小生成樹

kruskal演算法能夠在並查集的基礎很快的實現。結合例子來介紹具體演算法實現（其中並查集的部分可以詳見並查集介紹部分）

生成樹的概念：聯通圖G的一個子圖如果是一棵包含G的所拍跡森有頂點的樹，則該子圖稱為G的生成樹 生成樹是聯通圖的極小連通子圖。所謂極小是指：若在樹中任意增加一條邊，則 將出現一個迴路；若去掉一條邊，將會使之編程非連通圖。生成樹各邊的權 值總和稱為生成素的權。權最小的生成樹稱為最小生成樹，常用的演算法有prime演算法和kruskal演算法。

⑸ 最小生成樹怎麼求

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

⑹ 最小生成樹

參見貪心演算法——最小生成樹演算法

貪心策略：

該演算法的理解：

循環不變式：鍵畝
在每次循環之前，A是某棵最小生成樹的一個子集。

安全邊：滿足如下條件的邊稱之為安全邊。
將邊(u, v)加入到集合A中，使得A不違反循環不變式，即AU{(u, v)}也是某棵最小生成樹的子集。

貪心策略中辨認安全邊的規則：

一個推論：

如果一個問題的最優解中包含了子問盯亮絕題的最優解，則該問題具有最優子結構。
最小生成樹是滿足最優子結構的，下面會給出證明：
最優子結構描述：假設我們已經得到了一個圖凱姿的最小生成樹(MST) T，(u, v)是這棵樹中的任意一條邊。如圖所示：

現在我們把這條邊移除，就得到了兩棵子樹T 1 和T 2，
如圖：

⑺ 3. 最小生成樹演算法

在一給定的無向連通圖 G = (V, E) 中， (u, v) 代表連接頂點 u 與頂點 v 的邊， w(u, v) 代表此邊的權重；若存在 T 為 E 的子集， G' = (V , T) 構成的圖為 G 的生成樹，使得的 ∑w(T) 最小，則此 T 為 G 的最小生成樹。

最小生成樹其實是最小權重生成樹的簡稱。

在n個城市中建立一個通信網路，則連通這n個城市需要亂叢布置n-1一條通信線路，考慮如何在成本最低的情況下建立這個通信網？
於是可以引入連通圖來解決上述問題，n個城市就是圖上的n個頂點，然後，邊表示兩個城市的通信線路，每條邊上的權重就是搭建這條線路所需要的成本，所以現在有n個頂點的連通網可以建立不同的生成樹，每一顆生成樹都可以作為一個通信網，當我們構造這個連通網所花的成本最小時，搭建該連通網的生成樹，就稱為最小生成樹。

G＝ （V，E） 為一個帶權連通無向圖， U 是頂點集 V 的一個非空子集，若 （嘩滑櫻u，v） 是一條具有最小權的邊，其中 u∈U ， v∈V-U ，則必存在一棵包含邊 （u，v） 的最小生成樹。

演算法過程： 帶權連通無向讓枯圖 G＝ （V，E）

演算法過程： 帶權連通無向圖 G＝ （V，E） ，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 演算法的總時間復雜度為 。

⑼ 最小生成樹演算法，急！

已編譯確認，編譯環境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;
}

⑽ 對給定的網和起點，實現求解最小生成樹的PRIM演算法，並給出動態演示。萬分火急

最近忙著考試，沒時間做圖形界面來動態演示部分啦，先給你一個基本的Prim程序吧，希望有所幫助。
/**
* PRIM(簡單版) 最小生成樹演算法 (Minimum Spanning Tree)
* 輸入：圖g； // 有向圖或者無向圖
* 輸出：(1)最小生成樹長sum；
* (2)最小生成樹prev。
* 結構: 圖g用鄰接矩陣表示，最短邊長dist用數組表示。
* 演算法：Prim演算法
* 復雜度：O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n; // n : 頂點個數
vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示)
vector<bool> known; // known : 各點是否已經選取
vector<早擾int> dist; // dist : 已選取點集到凳枯未選取點的最小邊長
vector<int> prev; // prev : 最小生成樹中各點的前一頂點
int s; // s : 起點(start)
int sum; // sum : 最小生成樹長

bool Prim() // 貪心演算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化起點到自身的路徑長為0。
int i;
for (i = 0; i < n; ++i)
{
int min = INT_MAX, v;
for (int i = 0; i <陸粗旦 n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 尋找未知的最短路徑長的頂點v，
if (min == INT_MAX) break; // 如果找不到，退出；
known[v] = true; // 如果找到，將頂點v設為已知，
sum += dist[v]; // 調整最小生成樹長
for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點w，
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; /* 調整頂點w的最短路徑長dist和最短路徑的前一頂點 prev。 */
}
return i == n; // 如果選取頂點個數為n，成功。
}

int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;
g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
g[4][6] = g[6][4] = 6;
g[5][6] = g[6][5] = 1;

s = 0; // 起點任選
sum = 0;
if (Prim())
{
cout << sum << endl;
for (int i = 1; i < n; ++i)
if(i != s) cout << prev[i] << "->" << i << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}

system("pause");
return 0;
}