5-4最小生成樹v第五章圖最小生成樹的定義v0v1v2v4v3生成樹：連通圖的生成樹是包含全部頂點的一個極小連通子圖含有n-1條邊多——構成回路少——不連通v0v1v2v4v3v0v1v2v4v3v3v2v1v4v0v0v1v2v4v3可以指定根結點生成樹可能不唯一生成樹的代價：在無向連通網(wǎng)中，生成樹上各邊的權值之和最小生成樹：在無向連通網(wǎng)中，代價最小的生成樹v0v1v2v4v32785636v0v1v2v4v3275生成樹的代價：20v0v1v2v4v32563生成樹的代價：16最小生成樹的定義在n個城市之間建造通信網(wǎng)絡，至少要架設n-1條通信線路，每兩個城市之間架設通信線路的造價是不一樣的，如何設計才能使得總造價最?。縋rim算法Kruskal算法學什么？5-4-1Prim算法v第五章圖基本思想算法：Prim輸入：無向連通網(wǎng)G=(V，E)輸出：最小生成樹T=(U，TE)1.初始化：U={v}；TE={}；2.重復下述操作直到U=V：2.1在E中尋找最短邊(i，j)，且滿足i∈U，j∈V-U；2.2U=U+{j}；2.3TE=TE+{(i，j)}；關鍵：如何找到連接U和V-U的最短邊？uvv'頂點集U頂點集V-Uminv0v1v2v4v3v5341219262525463817關鍵：是如何找到連接U和V-U的最短邊？

U：涂色

V-U：尚未涂色方法：一個頂點涂色、另一個頂點尚未涂色的最短邊v0v1v2v4v3v51219262517基本思想v0運行實例初始化：U={v0}V-U={v1,v2,v3,v4,v5}cost={(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}v0v519第一次迭代：U={v0

,v5}V-U={v1,v2,v3,v4}cost={(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26}v0v1v2v4v3v5341219262525463817v0v519v225第二次迭代：U={v0

,v5,v2}V-U={v1,v3,v4}cost={(v0,v1)34,(v2,v3)17,(v5,v4)26}v0v2v51925v317第三次迭代：U={v0

,v5,

v2,v3}V-U={v1,v4}cost={(v0,v1)34,(v5,v4)26}第一次迭代：cost={(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26}運行實例v0v1v2v4v3v5341219262525463817v426v0v2v3v5192517第四次迭代：U={v0

,v5,

v2,v3,v4}V-U={v1}cost={(v4,v1)12}v112v0v2v4v3v519262517第三次迭代：cost={(v0,v1)34,(v5,v4)26運行實例v0v1v2v4v3v5341219262525463817存儲結構需要不斷讀取任意兩個頂點之間邊的權值圖采用什么存儲結構？圖采用鄰接矩陣存儲如何存儲候選最短邊集（連接U和V-U的候選最短邊）？數(shù)組adjvex[n]：表示候選最短邊的鄰接點數(shù)組lowcost[n]：表示候選最短邊的權值adjvex[i]=jlowcost[i]=w例如：{(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}含義是：候選最短邊（i,j）的權值為w，其中i∈V-U，j∈U初始時，lowcost[v]=0，表示將頂點v加入集合U中；

adjvex[i]=v，lowcost[i]=edge[v][i]（0≤i

≤n-1）例如：{(v0,v0)0,(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}000000adjvex[n]=012345

03446∞

∞19lowcost[n]=存儲結構每一次迭代，設數(shù)組lowcost[n]中的最小權值是lowcost[j]，則

令lowcost[j]=0，表示將頂點j加入集合U中；例如：{(v0,v0)0,(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}更新：{(v0,v0)0,(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26,(v0,v5)0}lowcost[i]=min{lowcost[i],edge[i][j]}adjvex[i]=j（如果edge[i][j]<lowcost[i]）（0≤i≤n-1）由于頂點j從集合V-U進入集合U，候選最短邊集發(fā)生變化，需要更新：012345

000000adjvex[n]=

03446∞

∞19lowcost[n]=

005

550adjvex[n]=

034252526

0lowcost[n]=012345存儲結構v0v1v2v4v3v5341219262525463817v0000340460∞0∞019

Vv0

v1

v2

v3

v4

v5U輸出

adjvexlowcost下標012345voidPrim(intv)/*假設從頂點v出發(fā)*/{inti,j,k,adjvex[MaxSize],lowcost[MaxSize];

lowcost[v]=0;/*將頂點v加入集合U*/for(i=0;i<vertexNum;i++)/*初始化輔助數(shù)組shortEdge*/{lowcost[i]=edge[v][i];adjvex[i]=v;}算法實現(xiàn)v0000340460∞0∞019(v0,v5)19

Vv0

v1

v2

v3

v4

v5U輸出

adjvexlowcostadjvexlowcost下標012345v0,v503452552552600v0v1v2v4v3v5341219262525463817for(k=1;k<vertexNum;i++)/*迭代n-1次*/{j=MinEdge(lowcost,vertexNum)/*尋找最短邊的鄰接點j*/cout<<j<<adjvex[j]<<lowcost[j];lowcost[j]=0;

}for(i=0;i<vertexNum;i++)/*調整數(shù)組shortEdge[n]*/if(edge[i][j]<lowcost[i]){lowcost[i]=edge[i][j];adjvex[i]=j;}算法實現(xiàn)v0v1v2v4v3v5341219262525463817v0,v5,v2,v3,v4,v1(v4,v1)12v0000340460∞0∞019(v0,v5)19

Vv0

v1

v2

v3

v4

v5U輸出

adjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcost下標012345v0,v503452552552600(v5,v2)25v0,v5,v203450217526(v2,v3)17v0,v5,v2,v303420526(v5,v4)26v0,v5,v2,v3,v44125040v0v1v2v4v3v51219262517驗證算法voidPrim(intv){inti,j,k,adjvex[MaxSize],lowcost[MaxSize];}O(n)O(n)O(n)時間復雜度？O(n2)for(i=0;i<vertexNum;i++)if(edge[i][j]<lowcost[i]){lowcost[i]=edge[i][j];adjvex[i]=j;}for(i=0;i<vertexNum;i++){lowcost[i]=edge[v][i];adjvex[i]=v;}lowcost[v]=0;for(k=1;k<vertexNum;i++){j=MinEdge(lowcost,vertexNum)cout<<j<<adjvex[j]<<lowcost[j];lowcost[j]=0;

}算法實現(xiàn)5-4-2Kruskal算法v第五章圖基本思想找到連接U和V-U的最短邊Prim算法的關鍵是什么？最短邊頂點分別位于U和V-U中Prim算法：先構造滿足條件的候選最短邊集，再查找最短邊Kruskal算法：先查找最短邊，再判斷是否滿足條件算法：Kruskal算法輸入：無向連通網(wǎng)G=(V,E)輸出：最小生成樹T=(U,TE)1.初始化：U=V；TE={}；

2.重復下述操作直到所有頂點位于一個連通分量：2.1在E中選取最短邊(u,v);2.2如果頂點

u、v

位于兩個連通分量，則2.2.1TE=TE+{(u,v)}；2.2.2將這兩個連通分量合成一個連通分量；2.3在

E

中標記邊(u,v)，使得(u,v)不參加后續(xù)最短邊的選?。换舅枷腙P鍵：如何判斷、合并頂點位于的連通分量？v0v1v2v4v3v5341219262525463817初始化：連通分量＝{v0},{v1},{v2},{v3},{v4},{v5}第一次迭代：連通分量＝{v0},{v1,v4},{v2},{v3},{v5}第二次迭代：連通分量＝{v0},{v1,v4},{v2,v3},{v5}第三次迭代：連通分量＝{v0,v5},{v1,v4},{v2,v3}第四次迭代：連通分量＝{v0,v2,v3,v5},{v1,v4}v0v1v2v4v3v51217252619第五次迭代：連通分量＝{v0,v2,v3,v5,v1,v4}運行實例圖采用什么存儲結構呢？邊集數(shù)組表示法存儲結構算法：Kruskal算法輸入：無向連通網(wǎng)G=(V,E)輸出：最小生成樹T=(U,TE)1.初始化：U=V；TE={}；

2.重復下述操作直到所有頂點位于一個連通分量：2.1在

E中選取最短邊(u,v);2.2如果頂點

u、v

位于兩個連通分量，則2.2.1TE=TE+{(u,v)}；2.2.2將這兩個連通分量合成一個連通分量；2.3在

E

中標記邊(u,v)，使得(u,v)不參加后續(xù)最短邊的選?。籿0v1v2v4v3v5341219262525463817v0

v1

v2

v3

v4

v5下標：012345

0519

2317

2525

3525

4526

0134

3438

0246

1412fromtoweight圖采用什么存儲結構呢？邊集數(shù)組表示法存儲結構v0

v1

v2

v3

v4

v5下標：012345

0519

2317

2525

3525

4526

3438

0134

0246

1412fromtoweightconstintMaxVertex=10;constintMaxEdge=100;template<typenameDataType>classEdgeGraph{public:

EdgeGraph(DataTypea[],intn,inte);

~EdgeGraph();

voidKruskal();private:

intFindRoot(intparent[],intv)

DataTypevertex[MaxVertex];

EdgeTypeedge[MaxEdge];

intvertexNum,edgeNum;};如何定義邊集數(shù)組表示法？存儲結構如何存儲連通分量呢？并查集{v0,v5},{v1,v4},{v2,v3}v0v1v2v4v3v5{v0,v5,v2,v3},{v1,v4}v2v1v3v4v5v0并查集：集合中的元素組織成樹的形式：（1）查找兩個元素是否屬于同一集合：所在樹的根結點是否相同（2）合并兩個集合——將一個集合的根結點作為另一個集合根結點的孩子存儲結構如何存儲并查集呢？雙親表示法{v0,v5},{v1,v4},{v2,v3}v0v1v2v4v3v5v0

v1

v2

v3

v4

v5下標：012345vertexparent[n]-1-1-1210parent存儲結構并查集：集合中的元素組織成樹的形式：（1）查找兩個元素是否屬于同一集合：所在樹的根結點是否相同（2）合并兩個集合——將一個集合的根結點作為另一個集合根結點的孩子v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5121719{v0,v5},{v1,v4},{v2,v3}v0v1v2v4v3v5-1-1-1210下標：012345parent如何判斷兩個頂點是否位于同一個連通分量呢？intFindRoot(intparent[],intv){intt=v;while(parent[t]>-1)t=parent[t];returnt;}vex1=FindRoot(parent,i);vex2=FindRoot(parent,j);if(vex1!=vex2){}例如，邊(v2,v5)運行實例{v0,v5},{v1,v4},{v2,v3}v0v1v2v4v3v5-1-1-1210下標：012345parent如何合并兩個連通分量呢？vex1=FindRoot(parent,i);vex2=FindRoot(parent,j);if(vex1!=vex2){

}parent[vex2]=vex1;{v0,v5,v2,v3},{v1,v4}v2v1v3v4v5v02v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5121719運行實例v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5初始化{v0}{v1}{v2}{v3}{v4}{v5}-1-1-1-1-1-1parent

Vv0

v1

v2

v3

v4

v5

最短邊

說明

parent下標012345voidKruskal(

){inti,num=0,vex1,vex2;for(i=0;i<vertexNum;i++)parent[i]=-1;}算法實現(xiàn)v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5初始化{v0}{v1}{v2}{v3}{v4}{v5}-1-1-1-1-1-112(v4,v1)12vex1=1,vex2=4,parent[4]=1{v0}{v1,v4}{v2}{v3}{v5}-1-1-1-1

1-117(v2,v3)17vex1=2,vex2=3,parent[3]=2{v0}{v1,v4}{v2,v3}{v5}-1-1-1

2

1-1parent

Vv0

v1

v2

v3

v4

v5

最短邊

說明

parent下標012345parentparentfor(num=0,i=0;num<ertexNum;i++){vex1=FindRoot(parent,edge[i].from);vex2=FindRoot(parent,edge[i].to);if(vex1!=vex2){cout<<edge[i].from<<edge[i].to<<edge[i].weight;

parent[vex2]=vex1;

num++;}}算法實現(xiàn)v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5初始化{v0}{v1}{v2}{v3}{v4}{v5}-1-1-1-1-1-112(v4,v1)12vex1=1,vex2=4,parent[4]=1{v0}{v1,v4}{v2}{v3}{v5}-1-1-1-1