圖的連通性最小生成樹(shù)的算法思想

圖的連通性最小生成樹(shù)的算法思想第一頁(yè)，共三十五頁(yè)，2022年，8月28日1.算法思想

假設(shè)N=(V,E)是連通網(wǎng),TE是N上最小生成樹(shù)中邊的集合,算法從U={vk},TE={}開(kāi)始(即從vk出發(fā)求最小生成樹(shù),vk∈V)。重復(fù)執(zhí)行下述操作：在所有的邊(vi,vj)∈E(vi∈U,vj∈V-U)中尋找一條權(quán)值最小的邊(vi,vj)將其添加到TE中(或打印之),同時(shí)把vj添加到集合U中。反復(fù)執(zhí)行上述操作n-1次（或所有頂點(diǎn)全部加入U(xiǎn)時(shí)為止）。一、最小生成樹(shù)第二頁(yè)，共三十五頁(yè)，2022年，8月28日2.實(shí)例：V={v1,v2,v3,v4,v5,v6}

一、最小生成樹(shù)v1v2v3v4v5v66551256463①任取uk=v1,則：U={v1},V-U={v2,v3,v4,v5,v6}第三頁(yè)，共三十五頁(yè)，2022年，8月28日2.實(shí)例：V={v1,v2,v3,v4,v5,v6}

一、最小生成樹(shù)v1v2v3v4v5v66551256463①任取uk=v1,則：U={v1},V-U={v2,v3,v4,v5,v6}②取邊(v1,v3),則：U={v1,v3}V-U={v2,v4,v5,v6}第四頁(yè)，共三十五頁(yè)，2022年，8月28日2.實(shí)例：V={v1,v2,v3,v4,v5,v6}

一、最小生成樹(shù)v1v2v3v4v5v66551256463①任取uk=v1,則：U={v1},V-U={v2,v3,v4,v5,v6}②取邊(v1,v3),則：U={v1,v3}V-U={v2,v4,v5,v6}③取邊(v3,v6),則：U={v1,v3,v6}V-U={v2,v4,v5}第五頁(yè)，共三十五頁(yè)，2022年，8月28日2.實(shí)例：V={v1,v2,v3,v4,v5,v6}

一、最小生成樹(shù)v1v2v3v4v5v66551256463①任取uk=v1,則：U={v1},V-U={v2,v3,v4,v5,v6}②取邊(v1,v3),則：U={v1,v3}V-U={v2,v4,v5,v6}③取邊(v3,v6),則：U={v1,v3,v6}V-U={v2,v4,v5}④取邊(v6,v4),則：U={v1,v3,v6,v4}V-U={v2,v5}第六頁(yè)，共三十五頁(yè)，2022年，8月28日2.實(shí)例：V={v1,v2,v3,v4,v5,v6}

一、最小生成樹(shù)v1v2v3v4v5v66551256463①任取uk=v1,則：U={v1},V-U={v2,v3,v4,v5,v6}②取邊(v1,v3),則：U={v1,v3}V-U={v2,v4,v5,v6}③取邊(v3,v6),則：U={v1,v3,v6}V-U={v2,v4,v5}④取邊(v6,v4),則：U={v1,v3,v6,v4}V-U={v2,v5}⑤取邊(v3,v2),則：U={v1,v3,v6,v4,v2}V-U={v5}第七頁(yè)，共三十五頁(yè)，2022年，8月28日2.實(shí)例：V={v1,v2,v3,v4,v5,v6}

一、最小生成樹(shù)v1v2v3v4v5v66551256463①任取uk=v1,則：U={v1},V-U={v2,v3,v4,v5,v6}②取邊(v1,v3),則：U={v1,v3}V-U={v2,v4,v5,v6}③取邊(v3,v6),則：U={v1,v3,v6}V-U={v2,v4,v5}④取邊(v6,v4),則：U={v1,v3,v6,v4}V-U={v2,v5}⑤取邊(v3,v2),則：U={v1,v3,v6,v4,v2}V-U={v5}⑥取邊(v2,v5),則：U={v1,v3,v6,v4,v2,v5}V-U={}第八頁(yè)，共三十五頁(yè)，2022年，8月28日2.實(shí)例：V={v1,v2,v3,v4,v5,v6}

一、最小生成樹(shù)v1v2v3v4v5v66551256463①任取uk=v1,則：U={v1},V-U={v2,v3,v4,v5,v6}②取邊(v1,v3),則：U={v1,v3}V-U={v2,v4,v5,v6}③取邊(v3,v6),則：U={v1,v3,v6}V-U={v2,v4,v5}④取邊(v6,v4),則：U={v1,v3,v6,v4}V-U={v2,v5}⑤取邊(v3,v2),則：U={v1,v3,v6,v4,v2}V-U={v5}⑥取邊(v2,v5),則：U={v1,v3,v6,v4,v2,v5}V-U={}第九頁(yè)，共三十五頁(yè)，2022年，8月28日3.算法的實(shí)現(xiàn)：一、最小生成樹(shù)v1v2v3v4v5v66551256463

②

用一個(gè)輔助的一維數(shù)組closedge[0..n-1]存儲(chǔ)n個(gè)頂點(diǎn)到U的距離：即對(duì)于每一個(gè)vi∈V-U,1≤i≤n,1)用closedge[i-1].lowcost存儲(chǔ)vi到U的最短距離(若vi已屬于U中的元素,則vi到U的距離為0)；

2)用closedge[i-1].adjvex存儲(chǔ)vi到U的最短距離所鄰接的那個(gè)頂點(diǎn)的值。①用順序存儲(chǔ)結(jié)構(gòu)(MgraphG)存儲(chǔ)圖，即利用一個(gè)二維數(shù)組(G.arcs)存儲(chǔ)圖的鄰接矩陣，用一個(gè)一維數(shù)組(G.vexs)存儲(chǔ)各頂點(diǎn)的值。第十頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v16v11v15v1∞v1∞{v1}{v2,v3,v4,v5,v6}01234501G.vexs:v1v2v3v4v5v6

012345第十一頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v16v11v15v1∞v1∞{v1}{v2,v3,v4,v5,v6}01234501G.vexs:v1v2v3v4v5v6

012345第十二頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v16v11v15v1∞v1∞{v1}{v2,v3,v4,v5,v6}201234501G.vexs:v1v2v3v4v5v6

012345打印(v1,v3),也即打?。?closedge[k].adjvex，G.vexs[k])第十三頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞

15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v16v10v15v1∞v1∞{v1}{v2,v3,v4,v5,v6}201234501G.vexs:v1v2v3v4v5v6

012345用二維數(shù)組的第K行與這里的lowcost行中的元素依次比較，若發(fā)現(xiàn)距離變小了，則用小值替代大值，且用G.vexs[K]的值(即v3)取代相應(yīng)的adjvex的值。第十四頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞

15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v15v36v34{v1}{v2,v4,v5,v6}201234501G.vexs:v1v2v3v4v5v6

012345第十五頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v15v36v34{v1,v3}{v2,v4,v5,v6}01234501G.vexs:v1v2v3v4v5v6

012345第十六頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v15v36v34{v1,v3}{v2,v4,v5,v6}501234501G.vexs:v1v2v3v4v5v6

012345打印(v3,v6),也即打印：(closedge[5].adjvex，G.vexs[5])第十七頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v15v36v30{v1,v3}{v2,v4,v5,v6}501234501G.vexs:v1v2v3v4v5v6

012345用二維數(shù)組的第K行與這里的lowcost行中的元素依次比較，若發(fā)現(xiàn)距離變小了，則用小值替代大值，且用G.vexs[K]的值(即v6)取代相應(yīng)的adjvex的值。第十八頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v62v36v30{v1,v3,v6}{v2,v4,v5}501234501G.vexs:v1v2v3v4v5v6

012345第十九頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v62v36v30{v1,v3,v6}{v2,v4,v5}01234501G.vexs:v1v2v3v4v5v6

012345第二十頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v62v36v30{v1,v3,v6}{v2,v4,v5}301234501G.vexs:v1v2v3v4v5v6

012345打印(v6,v4),也即打?。?closedge[3].adjvex，G.vexs[3])第二十一頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564

565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v60v36v30{v1,v3,v6}{v2,v4,v5}301234501G.vexs:v1v2v3v4v5v6

012345用二維數(shù)組的第K行與這里的lowcost行中的元素依次比較，若發(fā)現(xiàn)距離變小了，則用小值替代大值，且用G.vexs[K]的值(即v4)取代相應(yīng)的adjvex的值。第二十二頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v60v36v30{v1,v3,v6,v4}{v2,v5}01234501G.vexs:v1v2v3v4v5v6

012345第二十三頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v35v10v60v36v30{v1,v3,v6,v4}{v2,v5}101234501G.vexs:v1v2v3v4v5v6

012345打印(v3,v2),也即打?。?closedge[1].adjvex，G.vexs[1])第二十四頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞

6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v30v10v60v36v30{v1,v3,v6,v4}{v2,v5}101234501G.vexs:v1v2v3v4v5v6

012345用二維數(shù)組的第K行與這里的lowcost行中的元素依次比較，若發(fā)現(xiàn)距離變小了，則用小值替代大值，且用G.vexs[K]的值(即v2)取代相應(yīng)的adjvex的值。第二十五頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v30v10v60v23v30{v1,v3,v6,v4,v2}{v5}01234501G.vexs:v1v2v3v4v5v6

012345第二十六頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v30v10v60v23v30{v1,v3,v6,v4,v2}{v5}401234501G.vexs:v1v2v3v4v5v6

012345打印(v2,v5),也即打印：(closedge[4].adjvex，G.vexs[4])第二十七頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)v1v2v3v4v5v66551256463

③數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)分析∞615∞∞6∞5∞3∞15∞564565∞∞2∞36∞∞6∞∞426∞G.arcs如下：012345

012345算法執(zhí)行期間一維數(shù)組closedge的動(dòng)態(tài)變化過(guò)程：3.算法的實(shí)現(xiàn)：

iclosedge012345UV-UKadjvexlowcostv10v30v10v60v20v30{v1,v3,v6,v4,v2,v5}{}01234501G.vexs:v1v2v3v4v5v6

012345第二十八頁(yè)，共三十五頁(yè)，2022年，8月28日一、最小生成樹(shù)3.算法的實(shí)現(xiàn)：

④算法程序第二十九頁(yè)，共三十五頁(yè)，2022年，8月28日

④算法程序1.復(fù)習(xí)圖的數(shù)組表示法

(MGgraph)的定義#defineINFINITY10000//INFINITY用以表示∞#defineMAX_VERTEX_NUM20//最大頂點(diǎn)數(shù)enumGraphKind{DG,DN,UDG,UDN};//枚舉：有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)typedefstructArcCell{VRTypeadj;//VRType的類(lèi)型視具體情況而定。對(duì)于帶權(quán)圖，adj用以存

//放邊或弧上的權(quán)值;對(duì)于無(wú)權(quán)圖，adj用以存放0或1(int類(lèi)型)//InfoType*info;//一般情況下可以不使用該項(xiàng)

}ArcCell,AdjMatrix[MAX_VERTEX_NUM,MAX_VERTEX_NUM];

//AdiMatrix是一個(gè)類(lèi)型為ArcCell的二維數(shù)組,用以存放弧或邊的鄰接關(guān)系或權(quán)值typedefstruct{VertexType

vexs[MAX_VERTEX_NUM];//VertexType是頂點(diǎn)值的類(lèi)型

//一維數(shù)組vexs用以存放各頂點(diǎn)的值

AdjMatrixarcs;//二維數(shù)組arcs存放邊或弧上的信息（如權(quán)值）

intvexnum,arcnum;//這兩項(xiàng)分別存放圖的頂點(diǎn)數(shù)目和弧的條數(shù)

GraphKindkind;//kind用以存放圖的種類(lèi)標(biāo)志

}MGraph第三十頁(yè)，共三十五頁(yè)，2022年，8月28日

④算法程序typedefstructAdjvexlowcost{VertexTypeadjvex;intlowcost;}Adjvexlowcost,ALList[MAX_VERTEX_NUM];ALListclosedge;//定義一個(gè)一維數(shù)組，其每個(gè)數(shù)組下標(biāo)變量

//closedge[i]均有兩個(gè)分量：adjvex和lowcost//closedge[i].lowcost記錄了vi到U的最短距離

//closedge[i].adjvex記錄了vi到U的這個(gè)最短距依賴U中哪個(gè)頂點(diǎn)2.求圖的最小生成樹(shù)的輔助一維數(shù)組

closedge的定義第三十一頁(yè)，共三十五頁(yè)，2022年，8月28日

④算法程序voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){k=locateVex(G,u);//在G.vexs[0..G.vexnum-1]中查找u,將u的序號(hào)作為返回值

closedge[k].adjvex=u;closedge[k].lowcost=0;//將u并入到U中

for(j=0;j<G.vexnum;++j)//將鄰接矩陣的第k行(如選u=v1,則k=0)作為數(shù)組

//closedge的初值

if(!j=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}for(i=1;i<G.vexnum;++i){//在無(wú)向網(wǎng)中找出n-1條邊構(gòu)成最小生成樹(shù)

k=minimum(closedge);//在數(shù)組closedge中查找一個(gè)k使得

//closedge[k].lowcost是最小的且不等于0printf(closedge[k].adjvex,G.vex[k]);//輸出找到的一條最小代價(jià)邊

closedge[k].lowcost=0;//將vk+1添加到U中

for(j=0;j<G.vexnum;++j)//用鄰接矩陣的第k行及vk+1修改closedgeif(G.arcs[k][j].adj)<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}第三十二頁(yè)，共三十五頁(yè)，2022年，8月28日voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){k=locateVex(G,u);//在G.vexs[0..G.vexnum-1]中查找u,將u的序號(hào)作為返回值

closedge[k].adjvex=u;closedge[k].lowcost=0;//將u并入到U中

for(j=0;j<G.vexnum;++j)//將鄰接矩陣的第k行(如選u=v1,則k=0)作為數(shù)組

//closedge的初值

if(!j=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}for(i=1;i<G.vexnum;++i){//在無(wú)向網(wǎng)中找出n-1條邊構(gòu)成最小生成樹(shù)

k=minimum(closedge);//在數(shù)組