連通圖的生成樹：一個極小連通子圖，它含有圖中全部頂點，但只有足以構成一棵樹的n-1條邊，這樣的連通子圖稱為連通圖的生成樹。

在一個連通圖的所有生成樹中，各邊的代價之和（即各邊的權值最?。┑哪强蒙蓸浞Q為該連通網(wǎng)的最小生成樹。

普里姆(Prim)算法

(1)構造過程

假設N=(V,E)是連通網(wǎng)，TE是N上最小生成樹中邊的集合

1. U={u0}(u0∈V),TE={}（U中是在生成過程中將點納入的集合）

2. 在所有u∈U,v∈V-U的邊（u,v）∈E中找一條權值最小的邊(u0,v0)并入集合TE,同時v0并入U中

3. 重復2，直至U=V為止。

   此時TE中必有n-1條邊，則T=（V,TE）為N的最小生成樹的例子。可以看出Prim算法逐步增加U中的頂點，可稱為"加點法"。

   
   

（2）算法實現(xiàn)

struct?

{

VetTexType? adjvex;//最小邊在U中的那個頂點

?ArcType lowcost;//最小邊上的權值

}closedge[MVNum];

//這是輔助數(shù)組，用來記錄從頂點集U到V-U的權值的邊

具體過程

void MiniSpanTree_Prim(AMGraph G,VerTexType u)

{//無向網(wǎng)G以鄰接矩陣形式存儲，從頂點u出發(fā)構造G的最小生成樹T，輸出T的各條邊

k=LocateVex(G,u);//k為頂點u的下標

for(j=0;j<G.vexnum;++j)//對每一個頂點vj,初始化closedge[j]

????if(j!=k) closedge[j]={u,G.arcs[k][j]};

closedge[k].lowcost=0;? //lowcost存儲最小邊上的權值

for(i=1;i<G.vexnum;++i)

{//選擇其余n-1個頂點，生成n-1條邊（n=G.vexnum）

k=Min(closedge);

//求出T的下一個結點：第k個頂點，closedge[k]中存有當前最小邊

u0=closedge[k].adjvex; //u0為最小邊的一個頂點，u0∈U

v0=G.vexs[k];? //v0為最小邊的另一個頂點，v0∈V-U

cout<<u0<<v0;//輸出當前的最小邊(u0,v0)

closedge[k].lowcost=0;

for(j=0;j<G.vexnum;++j)

????if(G.arcs[k][j]<closedge[j].lowcost)

????????closedge[j]={G.vexs[k],G.arcs[k][j]};//選出最小的權值得到最小邊將新頂點并入U

}

}

【算法分析】

算法的時間復雜度為O(n^2),與網(wǎng)中的邊數(shù)無關，因此適用于求稠密圖網(wǎng)的最小生成樹。

克魯斯卡爾算法

（1）構造過程

假設連通網(wǎng)N=(V,E),將N中的邊按權值從小到大的順序排列

1. 初始狀態(tài)是只有n個頂點而無邊的非連通圖T=（V,{}）,圖中每個頂點自成一個連通分量

2. 在E中選擇權值最小的邊，若該邊依附的頂點落在T中不同的連通分量上（即不形成回路），則將此邊加入到T中，否則舍去此邊而選擇下一條權值最小的邊。

3. 重復2，直至T中所有頂點都在同一連通分量上為止

（2）算法實現(xiàn)

struct

{

VerTexType Head;//邊的始點

VerTexType Tail;//邊的終點

ArcType lowcost;//邊上的權值

}Edge[arcnum];

//以上為結構體數(shù)組Edge：存儲邊的信息

int Vexset[MVNum];

//該數(shù)組用于標記各個頂點所屬的連通分量

具體過程

void MiniSpanTree_Kruskal(AMGraph G)

{

Sort(Edge);//權值從小到大排序

for(i=0;i<G.vexnum;++i)

????Vexset[i]=i;

for(i=0;i<G.arcnum;++i)

{

v1=LocateVex(G,Edge[i].Head);

v2=LocateVex(G,Edge[i].Tail);

vs1=?Vexset[v1];//獲取邊的始點所在的連通分量vs1

vs2=?Vexset[v2];//獲取邊的終點所在的連通分量vs2

if(vs1!=vs2)

{

? cout<<Edge[i].Head<<Edge[i].Tail;//輸出此邊

?for(j=0;j<G.vexnum;++j)//合并vs1和vs2兩個分量，兩個集合統(tǒng)一編號

if(Vexset[j]==vs2)

Vexset[j]=vs1;

}

}

【算法分析】

該算法的時間復雜度為O(elog2e),與網(wǎng)中的邊數(shù)有關，與普里姆算法相比，克魯斯卡爾算法更適合求稀疏圖的最小生成樹。