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

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

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

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

E(G)是有向邊（也稱弧）的有限集合，弧是頂點的有序?qū)Γ洖?lt;v,w>，v,w是頂點，v為弧尾，w為弧頭無向圖——無向圖G是由兩個集合V(G)和E(G)組成的

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

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

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

^V1

V2

V4^

V5^

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

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//定義邊結構{intadjvex;//下一條邊的始點編號structarcnode*nextarc;//下一條邊的指針}arcnode;typedefstructvexnode//定義頂點數(shù)組{intvertex;//存放頂點信息

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

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

intvexnum,arcnum;//頂點個數(shù)和邊條數(shù)}graph;結構定義2023/2/422創(chuàng)建圖的基本算法//實質(zhì)是：將圖中的數(shù)據(jù)和關系存儲起來(1)初始化圖的頂點數(shù)和邊數(shù)(2)初始化圖的頂點數(shù)組(3)初始化圖的邊voidcreate(graph*g){//根據(jù)用戶輸入創(chuàng)建一個圖 intn,e,i,j,k; arcnode*p,*t; cout<<"創(chuàng)建一個圖:\t"; cout<<"頂點數(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<<"條邊(結點號從0到"<<n-1<<"):"; cin>>i>>j; p=newarcnode;//創(chuàng)建邊結點

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)//輸出一個圖{ 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有向圖的十字鏈表表示法(已介紹)弧結點：typedefstructarcnode{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置

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

structarcnode*tlink;//指向弧尾相同的下一條弧}AD;tailvexheadvexhlinktlink頂點結點：typedefstructdnode{intdata;//存與頂點有關信息

structarcnode*firstin；//指向以該頂點為弧頭的第一個弧結點

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

13

12

34

31

43

42

41^^^^^^^^2023/2/427無向圖的鄰接多重表表示法(了解)頂點結點：typedefstructdnode{intdata;//存與頂點有關的信息

structnode*firstedge;//指向第一條依附于該頂點的邊}DD;DDga[M];//ga[0]不用datafirstedge邊結點：typedefstructnode{intmark;//標志域

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

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

12

14

34

32

35

52^^^^^2023/2/429深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V77.3圖的遍歷2023/2/430V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V72023/2/431V1V2V4V5V3V7V6V8例（書）:深度遍歷：V1V2V4V8V3V6V7V52023/2/432深度優(yōu)先遍歷算法遞歸算法開始訪問V0,置標志求V0鄰接點有鄰接點w求下一鄰接點wV0W訪問過結束NYNYDFS開始標志數(shù)組初始化Vi=1Vi訪問過DFSVi=Vi+1Vi==Vexnums結束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^^^遞歸算法：以圖中某一結點作為當前結點進行以下過程：(1)訪問當前結點，并作已訪問標志；(2)若當前結點有后續(xù)結點，則取第一個后續(xù)結點，若該后續(xù)結點未被訪問過，則以該后繼結點作為當前結點用深度優(yōu)先搜索法進行訪問。這是一個遞歸過程。2023/2/436voiddfs(graphg,intv, intvisited[]){arcnode*p;inti;cout<<v<<“”;//開始訪問點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^^^結果2/437voidmain(){graphg;intvisited[Vnum],i,v;for(i=0;i<Vnum;i++)visited[i]=0;g=creatng();disp(&g);cout<<"輸入頂點:";cin>>v;cout<<"深度優(yōu)先序列:";dfs(g,v,visited);}…主函數(shù)2023/2/438廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V82023/2/439V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V82023/2/440V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V6V7V8V52023/2/441廣度優(yōu)先遍歷算法開始標志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結束NNYY2023/2/442開始訪問V0,置標志求V鄰接點ww存在嗎V下一鄰接點ww訪問過結束NYNYBFS初始化隊列V0入隊隊列空嗎隊頭V出隊訪問w,置標志w入隊NaaY2023/2/443(1)把隊列置空(f=r)；(2)打印出發(fā)結點，置該頂點已被訪問標志；(3)讓出發(fā)頂點進隊；(4)若隊列不空(f!=r)，則(a)取出隊首中的頂點v；(b)在鄰接表中，以此取得與頂點v

鄰接的各個頂點(i)若當前取得鄰接頂點未被訪問，則打印該頂點，置該頂點已被訪問標志，該頂點進隊；(ii)取得下個鄰接頂點；(c)轉(4)；(5)若隊列空，則處理過程結束。例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2為何要使用隊列?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)先遍歷算法實現(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}結果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; }}}結果：1327648(1)把隊列置空(f=r)；(2)打印出發(fā)結點，置該頂點已被訪問標志；(3)讓出發(fā)頂點進隊；(4)若隊列不空(f!=r)，則(a)取出隊首中的頂點v；(b)在鄰接表中，以此取得與頂點v

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

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

pop(s,v);}//while｝2023/2/452BFS遞歸算法—針對鄰接矩陣的程序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生成樹定義：所有頂點均由邊連接在一起，但不存在回路的圖叫~分為：深度優(yōu)先生成樹與廣度優(yōu)先生成樹生成森林：非連通圖每個連通分量的生成樹一起組成非連通圖的~GHKI7.4生成樹2023/2/455說明：一個圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點：生成樹的頂點個數(shù)與圖的頂點個數(shù)相同生成樹是圖的極小連通子圖一個有n個頂點的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個頂點n-1條邊的圖不一定是生成樹2023/2/456V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V82023/2/457例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林2023/2/458最小生成樹問題提出要在n個城市間建立通信聯(lián)絡網(wǎng)，頂點——表示城市權——城市間建立通信線路所需花費代價給定一個無向網(wǎng)絡，在圖的所有生成樹中，使得各邊權數(shù)和最小的那棵生成樹稱為圖的最小生成樹，也叫最小代價生成樹。問題分析1654327131791812752410n個城市間，最多可設置n(n-1)/2條線路n個城市間建立通信網(wǎng)，只需n-1條線路問題轉化為：如何在可能的線路中選擇n-1條，能把

所有城市（頂點）均連起來，且總耗費

（各邊權值之和）最小2023/2/4591.1926年Baruvka提出了第一個最小生成樹算法【O.Baruvka,“Ojistemproblemuminimalnim,”Praca

MoravskePrirodovedeckeSpolecnosti,vol.3,pp.37~58】2.1957年Prim提出了著名的Prim算法【R.C.Prim,“ShortestConnectionNetworksandSomeGeneralizations,”BellSystemTechnicalJournal,vol.36,pp.1389~1401】3.1956年Kruskal提出了著名的Kruskal算法【J.B.Kruskal,“OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem,”ProceedingsoftheAmericanMathematicalSociety,vol.7,48~50】3.當前漸進最快的最小生成樹算法是1995年由Karger、Klein和Tarjan提出的隨機方法【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)地介紹了最小生成樹的歷史。2023/2/460構造最小生成樹方法一：普里姆(Prim)算法算法思想：按權值局部最小逐次將頂點和邊加入到T中，直至V(T)滿n個頂點為止。設N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)將(u0,v0)并入集合TE，同時v0并入U重復上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹算法實現(xiàn)：圖用鄰接矩陣表示例16543265135664252023/2/461例16543265135664251311631416431421164321425165432142532023/2/46210123450123451-21-41-11-51-3054321651356642505432114253算法：從網(wǎng)中任意一個頂點開始，首先把這個頂點包括在生成樹里，然后在那些其一個端點已在生成樹里另一個端點還未在生成樹里的邊中，找權值最小的一條邊，并把這條邊和邊依附的那個不在生成樹里的端點添加進生成樹里。說明：對角線元素全為0。構造最小生成樹的過程中，若頂點已包含在生成樹里，就把其對應的對角線元素置為“1”；若邊(vi,vj)已包含進生成樹里，就把A[i,j]或A[j,i]位于下三角的一個置為負值。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ù)上頁2023/2/4652023/2/466方法二：克魯斯卡爾(Kruskal)算法算法思想：按權值的遞增次序選擇合適邊來構造最小生成樹。設連通網(wǎng)N=(V,{E})，令最小生成樹：初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,{})，每個頂點自成一個連通分量在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊依此類推，直至T中所有頂點都在同一連通分量上為止例1654326513566425165432123452023/2/467（0）用頂點數(shù)組和邊數(shù)組存放頂點和邊信息（1）初始時，令每個頂點的jihe互不相同；每個邊的flag為0（2）選出權值最小且flag為0的邊（3）若該邊依附的兩個頂點的jihe值不同，即非連通，則令該邊的flag=1，選中該邊；再令該邊依附的兩頂點的jihe

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

intjihe;}VEX;邊結點：typedefstruct{intvexh,vext;//邊依附的兩頂點

intweight;//邊的權值

intflag;//標志域}EDGE;算法實現(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++){//初始化頂點 cout<<"t["<<i<<"].data=:"; cin>>t[i].data; t[i].jihe=i;}for(i=0;i<m;i++){//初始化邊和權 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ù)上頁2023/2/4722023/2/473普里姆算法克魯斯卡爾算法時間復雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應范圍比較兩種算法2023/2/474作業(yè)實現(xiàn)普里姆(Prim)算法實現(xiàn)克魯斯卡爾(Kruskal)算法2023/2/475問題提出：學生選修課程問題頂點——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>學生應按怎樣的順序?qū)W習這些課程，才能無矛盾、順利地完成學業(yè)——拓撲排序定義AOV網(wǎng)——用頂點表示活動，用弧表示活動間優(yōu)先關系的有向圖，稱為頂點表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件7.5拓撲排序2023/2/476拓撲排序——把AOV網(wǎng)絡中各頂點按照它們相互之間的優(yōu)先關系排列成一個線性序列的過程叫~檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)拓撲排序的方法在有向圖中選一個沒有前驅(qū)的頂點且輸出之從圖中刪除該頂點和所有以它為尾的弧重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅(qū)的頂點為止2023/2/477例課程代號課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設計基礎離散數(shù)學數(shù)據(jù)結構匯編語言語言的設計和分析計算機原理編譯原理操作系統(tǒng)高等數(shù)學線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C122023/2/478C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：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)的拓撲序列不是唯一的2023/2/479C1C2C3C4C5C6C7C8C9C10C11C122023/2/480C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2（2）2023/2/481C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3（3）C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4（4）2023/2/482C6C8C10C11C12拓撲序列：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）2023/2/483C6C8C12拓撲序列：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）2023/2/484算法實現(xiàn)以鄰接表作存儲結構把鄰接表中所有入度為0的頂點進棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧重復上述操作直至?？諡橹埂Ｈ魲？諘r輸出的頂點個數(shù)不是n，則有向圖有環(huán)；否則，拓撲排序完畢(1)選無前驅(qū)結點輸出(2)刪除該點及其出邊2023/2/485鄰接表結點：typedefstructarcnode{intadjvex;//頂點域

structarcnode*next;//鏈域}arcnode;表頭結點：typedefstructvexnode{

intvexdata;

//頂點信息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;//進棧

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<<"輸出的頂點個數(shù):"<<m<<endl; if(m<g->vexnum) cout<<"Thenetworkhasacycle\n";}503241…續(xù)上頁2023/2/4120問題提出把工程計劃表示為有向圖，用頂點表示事件，弧表示活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始例設一個工程有11項活動，9個事件事件V1——表示整個工程開始事件V9——表示整個工程結束問題：（1）完成整項工程至少需要多少時間？（2）哪些活動是影響工程進度的關鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=47.6關鍵路徑2023/2/4121定義AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權表示活動持續(xù)時間路徑長度——路徑上各活動持續(xù)時間之和關鍵路徑——路徑長度最長的路徑叫~Ve(j)——表示事件Vj的最早發(fā)生時間Vl(j)——表示事件Vj的最遲發(fā)生時間e(i)——表示活動ai的最早開始時間l(i)——表示活動ai的最遲開始時間l(i)-e(i)——表示完成活動ai的時間余量關鍵活動——關鍵路徑上的活動叫~，即l(i)=e(i)的活動2023/2/4122問題分析如何找e(i)=l(i)的關鍵活動？設活動ai用弧<j,k>表示，其持續(xù)時間記為：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開始向前遞推(2)從Vl(n)=Ve(n)開始向后遞推2023/2/4123求關鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動ell-e000022660462583770770710316160141400332023/2/4124算法實現(xiàn)以鄰接表作存儲結構從源點V1出發(fā)，令Ve[1]=0,按拓撲序列求各頂點的Ve[i]從匯點Vn出發(fā)，令Vl[n]=Ve[n],按逆拓撲序列求其余各頂點的Vl[i]根據(jù)各頂點的Ve和Vl值，計算每條弧的e[i]和l[i],找出e[i]=l[i]的關鍵活動鄰接表結點：typedefstructnode{intvex;//頂點域

intlength;structnode*next;//鏈域}JD;表頭結點：typedefstructtnode{intvexdata;intin;//入度域

structnode*link;//鏈域}TD;TDg[M];//g[0]不用2023/2/4125算法描述輸入頂點和弧信息，建立其鄰接表計算每個頂點的入度對其進行拓撲排序排序過程中求頂點的Ve[i]將得到的拓撲序列進棧按逆拓撲序列求頂點的Vl[i]計算每條弧的e[i]和