數(shù)據(jù)結(jié)構(gòu)電子科技第四章圖

4.4生成樹生成樹定義：所有頂點均由邊連接在一起，但不存在回路的圖叫~深度優(yōu)先生成樹與廣度優(yōu)先生成樹生成森林：非連通圖每個連通分量的生成樹一起組成非連通圖的~說明一個圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點：生成樹的頂點個數(shù)與圖的頂點個數(shù)相同生成樹是圖的極小連通子圖一個有n個頂點的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個頂點n-1條邊的圖不一定是生成樹GHKIV1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林最小生成樹問題提出要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點——表示城市權(quán)——城市間建立通信線路所需花費代價希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費的總代價）最小———最小代價生成樹問題分析1654327131791812752410n個城市間，最多可設(shè)置n(n-1)/2條線路n個城市間建立通信網(wǎng)，只需n-1條線路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費（各邊權(quán)值之和）最小構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)將(u0,v0)并入集合TE，同時v0并入U重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹算法實現(xiàn)：圖用鄰接矩陣表示算法描述Ch6_3.c例1654326513566425131163141643142116432142516543214253參見P174圖7.17000000

06

1

5maxmax

iclosest[i]lowcost[i]

012345

iclosest[i]lowcost[i]

012345U={v0}U={v0,v2}對iV-Uclosest[i]=j(jU)

(j,i)是一條邊，且是i到U中各頂點“權(quán)最小邊”Lowcost[i]：用來保存連接i到U中各頂點“權(quán)最小邊”的權(quán)。V-U={v1,V2,V3,V4,V5}V-U={v1,V3,V4,V5}V2V0V3V5V4V2V0V3V5V4020022

05056

4020520

05

0

260

iclosest[i]lowcost[i]

012345

iclosest[i]lowcost[i]

012345U={v0,V2,V5}U={v0,v2,V3,V5}V-U={v1,V3,V4}V-U={v1,V4}V2V0V3V5V4020020

05006

0V2V0V3V5V4

iclosest[i]lowcost[i]

012345U={v0,V1,v2,V3,V5}V-U={V4}000020

00006

0V2V0V3V5V4012345012345000例165432651356642500165432651356642516543214253普里姆算法(從頂點6出發(fā)，修改輔助數(shù)組)方法二：克魯斯卡爾(Kruskal)算法算法思想：設(shè)連通網(wǎng)N=(V,{E})，令最小生成樹初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,{})，每個頂點自成一個連通分量在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊依此類推，直至T中所有頂點都在同一連通分量上為止例165432651356642516543212345（0）用頂點數(shù)組和邊數(shù)組存放頂點和邊信息（1）初始時，令每個頂點的jihe互不相同；每個邊的flag為0（2）選出權(quán)值最小且flag為0的邊（3）若該邊依附的兩個頂點的jihe值不同，即非連通，則令該邊的flag=1,選中該邊；再令該邊依附的兩頂點的jihe以及兩集合中所有頂點的jihe相同若該邊依附的兩個頂點的jihe值相同，即連通，則令該邊的flag=2,即舍去該邊（4）重復(fù)上述步驟，直到選出n-1條邊為止頂點結(jié)點：typedefstruct{intdata;//頂點信息intjihe;}VEX;邊結(jié)點：typedefstruct{intvexh,vext;//邊依附的兩頂點intweight;//邊的權(quán)值intflag;//標志域}EDGE;算法實現(xiàn)：例1654326513566425Ch6_30.c算法描述：datajihe124536124536124536vexhweight112213233544vextflag6153550000000134256789334556666426000011111421112222216543212345有向無環(huán)圖

有向樹有向無環(huán)圖有向圖((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)對于無向圖來說，若深度優(yōu)先遍歷過程中遇到回邊（即指向已訪問過頂點的邊），則必定存在回環(huán)對于有向圖，從某個頂點v出發(fā)的遍歷，在dfs(v)結(jié)束之前出現(xiàn)一條從頂點u到頂點v的回邊，由于u在生成樹上是v的子孫，則有向圖中必定存在包含頂點v和u的環(huán)。4.4.2拓撲排序問題提出：學(xué)生選修課程問題頂點——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)——拓撲排序 定義AOV網(wǎng)——用頂點表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件拓撲排序——把AOV網(wǎng)絡(luò)中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程叫~檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)拓撲排序的方法在有向圖中選一個沒有前驅(qū)的頂點且輸出之從圖中刪除該頂點和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅(qū)的頂點為止例課程代號課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計和分析計算機原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個AOV網(wǎng)的拓撲序列不是唯一的C1C2C3C4C5C6C7C8C9C10C11C12C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2（2）C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3（3）C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4（4）C6C8C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9C6C8C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10（8）C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5（5）C6C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7（6）C6C8C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11（9）C8C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6（10）C8拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8（12）算法實現(xiàn)以鄰接表作存儲結(jié)構(gòu)把鄰接表中所有入度為0的頂點進棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧重復(fù)上述操作直至?？諡橹?。若棧空時輸出的頂點個數(shù)不是n，則有向圖有環(huán)；否則，拓撲排序完畢鄰接表結(jié)點：typedefstructnode{intvex;//頂點域structnode*next;//鏈域}JD;表頭結(jié)點：typedefstructtnode{intin;//入度域structnode*link;//鏈域}TD;TDg[M];//g[0]不用32104算法描述例1234560122inlink5543^^^vexnext3^25^240123456^Ch6_40.ctop16toptop0122inlink5543^^^vexnext3^25^240123456^輸出序列：63210416toptop0122inlink5543^^^vexnext3^25^240123456^輸出序列：6321041topp0122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp0122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp0112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp0112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp=NULL0112inlink5543^^^vexnext2^25^240123456^輸出序列：61321041toptop0112inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp0102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp40102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top0102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top0002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top30002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top30002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top30001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top30001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p=NULL4top30001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044top30001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044topp0001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp0001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp0000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp20000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp20000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044top2p=NULL0000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044top2p=NULL0000inlink5543^^^vexnext1^25^240123456