算法分析與復(fù)雜性理論第7章(圖)

2023/2/41第七章圖2023/2/42引言圖是一類(lèi)重要的非線性結(jié)構(gòu)；由數(shù)據(jù)和結(jié)構(gòu)組成，G=(V,E)；是一種多對(duì)多的結(jié)構(gòu)關(guān)系，每個(gè)元素可以有零個(gè)或多個(gè)直接前趨；零個(gè)或多個(gè)直接后繼。圖論的創(chuàng)始人是瑞士科學(xué)家歐拉，他提出并解答了著名的哥尼斯堡七橋問(wèn)題，從而開(kāi)創(chuàng)了圖論的研究，請(qǐng)參見(jiàn)【L.Euler,SolutioProblematisadGeomertriamSitusPertinentis.1736】2023/2/43contents7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.2.1數(shù)組表示法7.2.2鄰接表7.3圖的遍歷7.3.1深度優(yōu)先搜索7.3.2廣度優(yōu)先搜索7.4圖的連通性問(wèn)題7.4.1無(wú)向圖的連通分量和生成樹(shù)7.4.2最小生成樹(shù)7.5有向無(wú)環(huán)圖及其應(yīng)用7.5.1拓?fù)渑判?.5.2關(guān)鍵路徑7.6最短路徑7.6.1從某個(gè)點(diǎn)源到其余各頂點(diǎn)的最短路徑7.6.2從一對(duì)頂點(diǎn)之間的最短路徑2023/2/447.1圖的定義和術(shù)語(yǔ)圖(Graph)——圖G是由兩個(gè)集合V(G)和E(G)組成的，記為G=(V,E)其中：V(G)是頂點(diǎn)的非空有限集

E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)蛴行驅(qū)τ邢驁D——有向圖G是由兩個(gè)集合V(G)和E(G)組成的

其中：V(G)是頂點(diǎn)的非空有限集

E(G)是有向邊（也稱(chēng)?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記?lt;v,w>，v,w是頂點(diǎn)，v為弧尾，w為弧頭無(wú)向圖——無(wú)向圖G是由兩個(gè)集合V(G)和E(G)組成的

其中：V(G)是頂點(diǎn)的非空有限集

E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，記?v,w）或(w,v)，并且(v,w)=(w,v) 2023/2/45例245136G1圖G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26圖G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}2023/2/46(1)鄰接點(diǎn)及關(guān)聯(lián)邊鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn)關(guān)聯(lián)邊：若邊e=(v,u),則稱(chēng)頂點(diǎn)v、u關(guān)連邊e(2)頂點(diǎn)的度無(wú)向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù)有向圖中，頂點(diǎn)的度分成入度與出度入度：以該頂點(diǎn)為頭的弧的數(shù)目出度：以該頂點(diǎn)為尾的弧的數(shù)目定理：設(shè)圖G的邊數(shù)為e，圖的所有頂點(diǎn)的度數(shù)和=2*e。例245136G1頂點(diǎn)2入度：1出度：3頂點(diǎn)4入度：1出度：0例157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：42023/2/47(3)路徑——路徑是頂點(diǎn)的序列V={Vi0,Vi1,……Vin}，滿足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路徑長(zhǎng)度——沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和回路——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫~(4)簡(jiǎn)單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫~(5)簡(jiǎn)單回路——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫~例245136G1路徑：1，2，3，5，6，3路徑長(zhǎng)度：5簡(jiǎn)單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡(jiǎn)單回路：3，5，6，32023/2/48例157324G26路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：1，2，3，1(6)連通圖連通——從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說(shuō)V和W是連通的連通圖——圖中任意兩個(gè)頂點(diǎn)都是連通的叫~連通分量——非連通圖的每一個(gè)連通部分叫~強(qiáng)連通圖——有向圖中，如果對(duì)每一對(duì)Vi,VjV,ViVj,從Vi到Vj和從Vj到Vi都存在路徑，則稱(chēng)G是~2023/2/49連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例2451362023/2/410(7)子圖——如果圖G(V,E)和圖G‘(V’,E‘),滿足：V’VE’E

則稱(chēng)G‘為G的子圖356例245136圖與子圖(8)完備圖有向完備圖——n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無(wú)向完備圖——n個(gè)頂點(diǎn)的無(wú)向圖最大邊數(shù)是n(n-1)/22023/2/411(9)網(wǎng)權(quán)——與圖的邊或弧相關(guān)的數(shù)叫~網(wǎng)——帶權(quán)的圖叫~例213213有向完備圖無(wú)向完備圖例14523753186422023/2/412多重鏈表(了解)例G12413例15324G2V1V2^^V4^V3^

^V1

V2

V4^

V5^

V37.2圖的存儲(chǔ)結(jié)構(gòu)2023/2/413鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣?yán)鼼12413例15324G22023/2/414特點(diǎn)：無(wú)向圖的鄰接矩陣對(duì)稱(chēng)，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱(chēng)；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和網(wǎng)絡(luò)的鄰接矩陣可定義為：2023/2/415例14523753186422023/2/416關(guān)聯(lián)矩陣——表示頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系的矩陣(了解)定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)，e0條邊的圖，G的關(guān)聯(lián)矩陣A是具有以下性質(zhì)的ne階矩陣2023/2/4174321例G124131234例15324G21234564321562023/2/418例BDAC123456ABCD4321562023/2/419特點(diǎn)關(guān)聯(lián)矩陣每列只有兩個(gè)非零元素，是稀疏矩陣；n越大，零元素比率越大無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是關(guān)聯(lián)矩陣A中第i行元素之和有向圖中，頂點(diǎn)Vi的出度是A中第i行中“1”的個(gè)數(shù)頂點(diǎn)Vi的入度是A中第i行中“-1”的個(gè)數(shù)2023/2/420鄰接表實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。├齛ecbdG21234acdbvexdatafirstarc

4

2

1

2^^^adjvexnext5e

4

3

5^

1

5

3

2

3^鄰接表首次出現(xiàn)于J.E.Hopcroft和R.E.Tarjan發(fā)表的論文【Algorithm447:EfficientAlgorithmsforGraphManipulation,CommunicationsoftheACM,16(1973),225~231】。2023/2/421typedefstructarcnode//定義邊結(jié)構(gòu){intadjvex;//下一條邊的始點(diǎn)編號(hào)structarcnode*nextarc;//下一條邊的指針}arcnode;typedefstructvexnode//定義頂點(diǎn)數(shù)組{intvertex;//存放頂點(diǎn)信息

arcnode*firstarc;//指向第1條邊的指針}adjlist;typedefstructgraphs//圖類(lèi)型{

adjlistadjlist[Vnum];//頂點(diǎn)數(shù)組

intvexnum,arcnum;//頂點(diǎn)個(gè)數(shù)和邊條數(shù)}graph;結(jié)構(gòu)定義2023/2/422創(chuàng)建圖的基本算法//實(shí)質(zhì)是：將圖中的數(shù)據(jù)和關(guān)系存儲(chǔ)起來(lái)(1)初始化圖的頂點(diǎn)數(shù)和邊數(shù)(2)初始化圖的頂點(diǎn)數(shù)組(3)初始化圖的邊voidcreate(graph*g){//根據(jù)用戶輸入創(chuàng)建一個(gè)圖 intn,e,i,j,k; arcnode*p,*t; cout<<"創(chuàng)建一個(gè)圖:\t"; cout<<"頂點(diǎn)數(shù):"; cin>>n; cout<<"\t\t邊數(shù):"; cin>>e; g->vexnum=n;//(1)

g->arcnum=e;//(1)

for(i=0;i<n;i++){//(2) g->adjlist[i].vertex=i; g->adjlist[i].firstarc=NULL; }//for2023/2/423 for(k=0;k<e;k++){//(3) cout<<"第"<<k+1<<"條邊(結(jié)點(diǎn)號(hào)從0到"<<n-1<<"):"; cin>>i>>j; p=newarcnode;//創(chuàng)建邊結(jié)點(diǎn)

p->adjvex=j; p->nextarc=NULL;// p->nextarc=g->adjlist[i].firstarc;// g->adjlist[i].firstarc=p;

if(g->adjlist[i].firstarc!=NULL){ t=g->adjlist[i].firstarc; while(t->nextarc!=NULL) {t=t->nextarc;} t->nextarc=p; }//if else g->adjlist[i].firstarc=p; }//for}2023/2/424voiddisp(graph*g)//輸出一個(gè)圖{ inti,have; arcnode*p; cout<<"輸出圖:"<<endl;; for(i=0;i<g->vexnum;i++) { p=g->adjlist[i].firstarc; have=0; while(p!=NULL) { cout<<"("<<i<<","<<p->adjvex<<")"; p=p->nextarc; have=1; } if(have==1)cout<<endl; }}voidmain(){ graphg; create(&g); disp(&g);}2023/2/425有向圖的十字鏈表表示法(已介紹)弧結(jié)點(diǎn)：typedefstructarcnode{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置

structarcnode*hlink；//指向弧頭相同的下一條弧

structarcnode*tlink;//指向弧尾相同的下一條弧}AD;tailvexheadvexhlinktlink頂點(diǎn)結(jié)點(diǎn)：typedefstructdnode{intdata;//存與頂點(diǎn)有關(guān)信息

structarcnode*firstin；//指向以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)

structarcnode*firstout;//指向以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)}DD;DDg[M];//g[0]不用datafirstinfirstout2023/2/426例bdacabcd1234

13

12

34

31

43

42

41^^^^^^^^2023/2/427無(wú)向圖的鄰接多重表表示法(了解)頂點(diǎn)結(jié)點(diǎn)：typedefstructdnode{intdata;//存與頂點(diǎn)有關(guān)的信息

structnode*firstedge;//指向第一條依附于該頂點(diǎn)的邊}DD;DDga[M];//ga[0]不用datafirstedge邊結(jié)點(diǎn)：typedefstructnode{intmark;//標(biāo)志域

intivex,jvex;//該邊依附的兩個(gè)頂點(diǎn)在表頭數(shù)組中位置

structnode*ilink,*jlink;//分別指向依附于ivex和jvex的下一條邊}JD;markivexilinkjvexjlink2023/2/428例aecbd1234acdb5e

12

14

34

32

35

52^^^^^2023/2/429深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)；然后依次從V0的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V77.3圖的遍歷2023/2/430V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V72023/2/431V1V2V4V5V3V7V6V8例（書(shū)）:深度遍歷：V1V2V4V8V3V6V7V52023/2/432深度優(yōu)先遍歷算法遞歸算法開(kāi)始訪問(wèn)V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)wV0W訪問(wèn)過(guò)結(jié)束NYNYDFS開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)DFSVi=Vi+1Vi==Vexnums結(jié)束NNYY2023/2/433V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V7V6V2V5V8V42023/2/434V1V2V4V5V3V7V6V8例12341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^深度遍歷：V1V3V7V6V2V4V8V52023/2/43512341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^遞歸算法：以圖中某一結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)進(jìn)行以下過(guò)程：(1)訪問(wèn)當(dāng)前結(jié)點(diǎn)，并作已訪問(wèn)標(biāo)志；(2)若當(dāng)前結(jié)點(diǎn)有后續(xù)結(jié)點(diǎn)，則取第一個(gè)后續(xù)結(jié)點(diǎn)，若該后續(xù)結(jié)點(diǎn)未被訪問(wèn)過(guò)，則以該后繼結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)用深度優(yōu)先搜索法進(jìn)行訪問(wèn)。這是一個(gè)遞歸過(guò)程。2023/2/436voiddfs(graphg,intv, intvisited[]){arcnode*p;inti;cout<<v<<“”;//開(kāi)始訪問(wèn)點(diǎn)visited[v]=1;p=g.adjlist[v].firstarc;while(p!=NULL){i=p->adjvex;if(visited[i]==0)

dfs(g,i,visited);p=p->nextarc;}}12341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^結(jié)果2/437voidmain(){graphg;intvisited[Vnum],i,v;for(i=0;i<Vnum;i++)visited[i]=0;g=creatng();disp(&g);cout<<"輸入頂點(diǎn):";cin>>v;cout<<"深度優(yōu)先序列:";dfs(g,v,visited);}…主函數(shù)2023/2/438廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)V0的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V82023/2/439V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V82023/2/440V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V6V7V8V52023/2/441廣度優(yōu)先遍歷算法開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)BFSVi=Vi+1Vi==Vexnums結(jié)束NNYY2023/2/442開(kāi)始訪問(wèn)V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V下一鄰接點(diǎn)ww訪問(wèn)過(guò)結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪問(wèn)w,置標(biāo)志w入隊(duì)NaaY2023/2/443(1)把隊(duì)列置空(f=r)；(2)打印出發(fā)結(jié)點(diǎn)，置該頂點(diǎn)已被訪問(wèn)標(biāo)志；(3)讓出發(fā)頂點(diǎn)進(jìn)隊(duì)；(4)若隊(duì)列不空(f!=r)，則(a)取出隊(duì)首中的頂點(diǎn)v；(b)在鄰接表中，以此取得與頂點(diǎn)v

鄰接的各個(gè)頂點(diǎn)(i)若當(dāng)前取得鄰接頂點(diǎn)未被訪問(wèn)，則打印該頂點(diǎn)，置該頂點(diǎn)已被訪問(wèn)標(biāo)志，該頂點(diǎn)進(jìn)隊(duì)；(ii)取得下個(gè)鄰接頂點(diǎn)；(c)轉(zhuǎn)(4)；(5)若隊(duì)列空，則處理過(guò)程結(jié)束。例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2為何要使用隊(duì)列?2023/2/444例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

20123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：1432023/2/445例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2012345432fr遍歷序列：1432012345

32fr遍歷序列：1432012345

325fr遍歷序列：143252023/2/446012345

25fr遍歷序列/p>

5fr遍歷序列/p>

fr遍歷序列：14325例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

22023/2/447//廣度優(yōu)先遍歷算法實(shí)現(xiàn)voidbfs(graphg,intv){intqueue[Vnum],rear=-1,first=-1;intvisited[Vnum],i;arcnode*p;//for(i=0;i<Vnum;i++)visited[i]=0;cout<<v<<"";visited[v]=1;rear++;queue[rear]=v;2023/2/448while(rear!=first){

first++;

v=queue[first]; p=g.adjlist[v].firstarc; while(p!=NULL) { if(!visited[p->adjvex]) { cout<<p->adjvex<<""; visited[p->adjvex]=1; rear++;

queue[rear]=p->adjvex; } p=p->nextarc; }//while}//while}結(jié)果2/449voidbfs(graphg,intv){intqueue[Vnum],rear=-1,first=-1;intvisited[Vnum],i;arcnode*p;//for(i=0;i<Vnum;i++)visited[i]=0;

cout<<v<<"";visited[v]=1;rear++;queue[rear]=v;while(rear!=first){

first++;

v=queue[first]; p=g.adjlist[v].firstarc; while(p!=NULL){ if(!visited[p->adjvex]){ cout<<p->adjvex<<""; visited[p->adjvex]=1; rear++;

queue[rear]=p->adjvex; } p=p->nextarc; }}}結(jié)果：1327648(1)把隊(duì)列置空(f=r)；(2)打印出發(fā)結(jié)點(diǎn)，置該頂點(diǎn)已被訪問(wèn)標(biāo)志；(3)讓出發(fā)頂點(diǎn)進(jìn)隊(duì)；(4)若隊(duì)列不空(f!=r)，則(a)取出隊(duì)首中的頂點(diǎn)v；(b)在鄰接表中，以此取得與頂點(diǎn)v

鄰接的各個(gè)頂點(diǎn)(i)若當(dāng)前取得鄰接頂點(diǎn)未被訪問(wèn)，則打印該頂點(diǎn)，置該頂點(diǎn)已被訪問(wèn)標(biāo)志，該頂點(diǎn)進(jìn)隊(duì)；(ii)取得下個(gè)鄰接頂點(diǎn)；(c)轉(zhuǎn)(4)；(5)若隊(duì)列空，則處理過(guò)程結(jié)束。2023/2/450作業(yè)：Dfs的非遞歸算法；Bfs的遞歸算法(嘗試)。2023/2/451DFS非遞歸算法Dfs(Graphg,intv){//利用棧實(shí)現(xiàn)非遞歸算法 //第一個(gè)頂點(diǎn)入棧并訪問(wèn)Visit(v);visit[v]=1;push(s,v); //當(dāng)棧不空時(shí)做

Whlie(!EmptyStack(s)){p=ghead[v]->firstArc; //找到棧頂?shù)囊粋€(gè)未被訪問(wèn)的鄰接點(diǎn)，入棧并訪問(wèn) while(p){w=p->adjvex; if(!visited[w]){push(s,w);visit(w); p=ghead[w]->firstArc;} elsep=p->next; }//while //如果所有鄰接點(diǎn)都被訪問(wèn)，出棧

pop(s,v);}//while｝2023/2/452BFS遞歸算法—針對(duì)鄰接矩陣的程序voidBFSTraverse(Graphg){inti;for(i=0;i<g.vexnum;i++)visited[i]=0;for(i=0;i<g.vexnum;i++)if(!visited[i])BFSM(g,i);}2023/2/453voidBFSM(Graphg,intk){ inti,j; CirQueueQ; InitQueue(&Q); cout<<g.vertex[k]<<endl; visited[k]=1; EnQueue(&Q,k); while(!QueueEmpty(&Q)) { i=DeQueue(&Q); for(j=0;j<g.vexnum;j++) if(g.edges[i][j]==1&&!visited[j]){ cout<<g.vertex[j]<<endl; visited[j]=1; EnQueue(&Q,j); } }}2023/2/454生成樹(shù)定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫~分為：深度優(yōu)先生成樹(shù)與廣度優(yōu)先生成樹(shù)生成森林：非連通圖每個(gè)連通分量的生成樹(shù)一起組成非連通圖的~GHKI7.4生成樹(shù)2023/2/455說(shuō)明：一個(gè)圖可以有許多棵不同的生成樹(shù)所有生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹(shù)是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n-1條邊生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹(shù)中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)2023/2/456V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V82023/2/457例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林2023/2/458最小生成樹(shù)問(wèn)題提出要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)——表示城市權(quán)——城市間建立通信線路所需花費(fèi)代價(jià)給定一個(gè)無(wú)向網(wǎng)絡(luò)，在圖的所有生成樹(shù)中，使得各邊權(quán)數(shù)和最小的那棵生成樹(shù)稱(chēng)為圖的最小生成樹(shù)，也叫最小代價(jià)生成樹(shù)。問(wèn)題分析1654327131791812752410n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路問(wèn)題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把

所有城市（頂點(diǎn)）均連起來(lái)，且總耗費(fèi)

（各邊權(quán)值之和）最小2023/2/4591.1926年Baruvka提出了第一個(gè)最小生成樹(shù)算法【O.Baruvka,“Ojistemproblemuminimalnim,”P(pán)raca

MoravskePrirodovedeckeSpolecnosti,vol.3,pp.37~58】2.1957年P(guān)rim提出了著名的Prim算法【R.C.Prim,“ShortestConnectionNetworksandSomeGeneralizations,”BellSystemTechnicalJournal,vol.36,pp.1389~1401】3.1956年Kruskal提出了著名的Kruskal算法【J.B.Kruskal,“OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem,”P(pán)roceedingsoftheAmericanMathematicalSociety,vol.7,48~50】3.當(dāng)前漸進(jìn)最快的最小生成樹(shù)算法是1995年由Karger、Klein和Tarjan提出的隨機(jī)方法【D.R.Karger,P.Klein,andR.E.Tarjan,“ARandomizedLinear-timeAlgorithmtoFindMinimumSpanningTrees,”JournaloftheACM,vol.42,321~328】4.文章【R.L.GrahamandP.Hell,“OntheHistoryoftheMinimumSpanningTreeProblem,”AnnalsoftheHistoryofComputing,vol.7,43~57】系統(tǒng)地介紹了最小生成樹(shù)的歷史。2023/2/460構(gòu)造最小生成樹(shù)方法一：普里姆(Prim)算法算法思想：按權(quán)值局部最小逐次將頂點(diǎn)和邊加入到T中，直至V(T)滿n個(gè)頂點(diǎn)為止。設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹(shù)算法實(shí)現(xiàn)：圖用鄰接矩陣表示例16543265135664252023/2/461例16543265135664251311631416431421164321425165432142532023/2/46210123450123451-21-41-11-51-3054321651356642505432114253算法：從網(wǎng)中任意一個(gè)頂點(diǎn)開(kāi)始，首先把這個(gè)頂點(diǎn)包括在生成樹(shù)里，然后在那些其一個(gè)端點(diǎn)已在生成樹(shù)里另一個(gè)端點(diǎn)還未在生成樹(shù)里的邊中，找權(quán)值最小的一條邊，并把這條邊和邊依附的那個(gè)不在生成樹(shù)里的端點(diǎn)添加進(jìn)生成樹(shù)里。說(shuō)明：對(duì)角線元素全為0。構(gòu)造最小生成樹(shù)的過(guò)程中，若頂點(diǎn)已包含在生成樹(shù)里，就把其對(duì)應(yīng)的對(duì)角線元素置為“1”；若邊(vi,vj)已包含進(jìn)生成樹(shù)里，就把A[i,j]或A[j,i]位于下三角的一個(gè)置為負(fù)值。2023/2/463voidminispantree_PRIM(intad[][M],intn){inti,j,k,p,q,wm;q=p=n-1;ad[q][q]=1;

for(k=0;k<(n-1);k++){ wm=MAX;

for(i=0;i<n;i++) if(ad[i][i]==1)

for(j=0;j<n;j++) if((ad[j][j]==0)&&(ad[i][j]<wm)) { wm=ad[i][j]; p=i; q=j; }2023/2/464 ad[q][q]=1; cout<<p<<“”q<<“”<<ad[p][q]; if(p>q) ad[p][q]=-ad[p][q]; else ad[q][p]=-ad[q][p];}//for}…續(xù)上頁(yè)2023/2/4652023/2/466方法二：克魯斯卡爾(Kruskal)算法算法思想：按權(quán)值的遞增次序選擇合適邊來(lái)構(gòu)造最小生成樹(shù)。設(shè)連通網(wǎng)N=(V,{E})，令最小生成樹(shù)：初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V,{})，每個(gè)頂點(diǎn)自成一個(gè)連通分量在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊依此類(lèi)推，直至T中所有頂點(diǎn)都在同一連通分量上為止例1654326513566425165432123452023/2/467（0）用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息（1）初始時(shí)，令每個(gè)頂點(diǎn)的jihe互不相同；每個(gè)邊的flag為0（2）選出權(quán)值最小且flag為0的邊（3）若該邊依附的兩個(gè)頂點(diǎn)的jihe值不同，即非連通，則令該邊的flag=1，選中該邊；再令該邊依附的兩頂點(diǎn)的jihe

以及兩集合中所有頂點(diǎn)的jihe相同若該邊依附的兩個(gè)頂點(diǎn)的jihe值相同，即連通，則令該邊的flag=2，即舍去該邊（4）重復(fù)上述步驟，直到選出n-1條邊為止//頂點(diǎn)結(jié)點(diǎn)：typedefstruct{intdata;//頂點(diǎn)信息

intjihe;}VEX;邊結(jié)點(diǎn)：typedefstruct{intvexh,vext;//邊依附的兩頂點(diǎn)

intweight;//邊的權(quán)值

intflag;//標(biāo)志域}EDGE;算法實(shí)現(xiàn)：2023/2/468例1654326513566425算法描述：datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222165432123452023/2/469voidminitree_KRUSKAL(void){intn,i,m,min,k,j;VEXt[M];EDGEe[M];cout<<"Inputnumberofvertexandedge:";cin>>n>>m;cout<<"Inputdataofvertex"<<endl;for(i=1;i<=n;i++){//初始化頂點(diǎn) cout<<"t["<<i<<"].data=:"; cin>>t[i].data; t[i].jihe=i;}for(i=0;i<m;i++){//初始化邊和權(quán) cout<<"e["<<i<<"].vexhe["<<i<<"].vexte["<<i<<"].weight:"; cin>>e[i].vexh>>e[i].vext>>e[i].weight; e[i].flag=0;}2023/2/470i=1;while(i<n){ min=MAX; for(j=0;j<m;j++){//尋找weight最小的邊，k if(e[j].weight<min&&e[j].flag==0){ min=e[j].weight;k=j;} }//for if(t[e[k].vexh].jihe!=t[e[k].vext].jihe){ e[k].flag=1; for(j=1;j<=n;j++) if(t[j].jihe==t[e[k].vext].jihe) t[j].jihe=t[e[k].vexh].jihe; t[e[k].vext].jihe=t[e[k].vexh].jihe; i++; }//使連通 elsee[k].flag=2;//已連通}//while

2023/2/471//輸出代碼for(i=0;i<m;i++) if(e[i].flag==1) cout<<e[i].vexh<<e[i].vext<<e[i].weight;}…續(xù)上頁(yè)2023/2/4722023/2/473普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法2023/2/474作業(yè)實(shí)現(xiàn)普里姆(Prim)算法實(shí)現(xiàn)克魯斯卡爾(Kruskal)算法2023/2/475問(wèn)題提出：學(xué)生選修課程問(wèn)題頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無(wú)矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判蚨xAOV網(wǎng)——用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖，稱(chēng)為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexnetwork)，簡(jiǎn)稱(chēng)AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件7.5拓?fù)渑判?023/2/476拓?fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過(guò)程叫~檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止2023/2/477例課程代號(hào)課程名稱(chēng)先修棵C1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言語(yǔ)言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C122023/2/478C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?023/2/479C1C2C3C4C5C6C7C8C9C10C11C122023/2/480C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2（2）2023/2/481C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3（3）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4（4）2023/2/482C6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9C6C8C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10（8）C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5（5）C6C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7（6）2023/2/483C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11（9）C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6（10）C8拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8（12）2023/2/484算法實(shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至?？諡橹?。若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤?1)選無(wú)前驅(qū)結(jié)點(diǎn)輸出(2)刪除該點(diǎn)及其出邊2023/2/485鄰接表結(jié)點(diǎn)：typedefstructarcnode{intadjvex;//頂點(diǎn)域

structarcnode*next;//鏈域}arcnode;表頭結(jié)點(diǎn)：typedefstructvexnode{

intvexdata;

//頂點(diǎn)信息intin;//入度域

arcnode

*firstarc;//鏈域}adjlist[Vnum];例123456typedefstructgraphs{adjlistadjlist;intvexnum,arcnum;}graph;2023/2/48632104算法描述例1234560122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^top16toptop2023/2/4870122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416toptop2023/2/4880122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：6321041topp2023/2/4890122inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp2023/2/4900122inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp2023/2/4910112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp2023/2/4920112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp=NULL2023/2/4930112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：61321041toptop2023/2/4940112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104topp2023/2/4950102inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104topp42023/2/4960102inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top2023/2/4970102inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top2023/2/4980002inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top32023/2/4990002inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top32023/2/41000002inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top32023/2/41010001inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top32023/2/41020001inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p=NULL4top32023/2/41030001inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：613321044top32023/2/41040001inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：613321044topp2023/2/41050001inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044topp2023/2/41060001inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044topp2023/2/41070000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044topp22023/2/41080000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044topp22023/2/41090000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044top2p=NULL2023/2/41100000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：6132321044top2p=NULL2023/2/41110000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：6132321044topp=NULL2023/2/41120000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：61324321044top2023/2/41130000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：6132432104topp2023/2/41140000inlink

5

5

4

3^^^vexnext0^

2

5^

2

40123456^輸出序列：6132432104topp52023/2/41150000inlink

5

5

4

3^^^vexnext0^

2

5^

2

40123456^輸出序列：6132432104topp=NULL52023/2/41160000inlink

5

5

4

3^^^vexnext0^

2

5^

2

40123456^輸出序列：61324532104top52023/2/41170000inlink

5

5

4

3^^^vexnext0^

2

5^

2

40123456^輸出序列：61324532104topp=NULL2023/2/4118voidtoposort(graph*g){ inttop,m,k,j,s[20]; arcnode*p; top=0;m=0; for(j=0;j<g->vexnum;j++) if(g->adjlist[j].in==0) s[top++]=j;//進(jìn)棧

while(top>0){ j=s[--top]; cout<<g->adjlist[j].vexdata<<""; m++; p=g->adjlist[j].firstarc;2023/2/4119 while(p!=NULL) { k=p->adjvex; g->adjlist[k].in--; if(g->adjlist[k].in==0) s[top++]=k; p=p->nextarc; } } cout<<endl; cout<<"輸出的頂點(diǎn)個(gè)數(shù):"<<m<<endl; if(m<g->vexnum) cout<<"Thenetworkhasacycle\n";}503241…續(xù)上頁(yè)2023/2/4120問(wèn)題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開(kāi)始例設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件事件V1——表示整個(gè)工程開(kāi)始事件V9——表示整個(gè)工程結(jié)束問(wèn)題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=47.6關(guān)鍵路徑2023/2/4121定義AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間路徑長(zhǎng)度——路徑上各活動(dòng)持續(xù)時(shí)間之和關(guān)鍵路徑——路徑長(zhǎng)度最長(zhǎng)的路徑叫~Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間e(i)——表示活動(dòng)ai的最早開(kāi)始時(shí)間l(i)——表示活動(dòng)ai的最遲開(kāi)始時(shí)間l(i)-e(i)——表示完成活動(dòng)ai的時(shí)間余量關(guān)鍵活動(dòng)——關(guān)鍵路徑上的活動(dòng)叫~，即l(i)=e(i)的活動(dòng)2023/2/4122問(wèn)題分析如何找e(i)=l(i)的關(guān)鍵活動(dòng)？設(shè)活動(dòng)ai用弧<j,k>表示，其持續(xù)時(shí)間記為：dut(<j,k>)則有：（1）e(i)=Ve(j)

（2）l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開(kāi)始向前遞推(2)從Vl(n)=Ve(n)開(kāi)始向后遞推2023/2/4123求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)ell-e000022660462583770770710316160141400332023/2/4124算法實(shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)從源點(diǎn)V1出發(fā)，令Ve[1]=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的Ve[i]從匯點(diǎn)Vn出發(fā)，令Vl[n]=Ve[n],按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的Vl[i]根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)鄰接表結(jié)點(diǎn)：typedefstructnode{intvex;//頂點(diǎn)域

intlength;structnode*next;//鏈域}JD;表頭結(jié)點(diǎn)：typedefstructtnode{intvexdata;intin;//入度域

structnode*link;//鏈域}TD;TDg[M];//g[0]不用2023/2/4125算法描述輸入頂點(diǎn)和弧信息，建立其鄰接表計(jì)算每個(gè)頂點(diǎn)的入度對(duì)其進(jìn)行拓?fù)渑判蚺判蜻^(guò)程中求頂點(diǎn)的Ve[i]將得到的拓?fù)湫蛄羞M(jìn)棧按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的e[i]和