頂點(diǎn)對(duì)課件講義整理

東南大學(xué)計(jì)算機(jī)學(xué)院方效林本課件借鑒了清華大學(xué)殷人昆老師和哈爾濱工業(yè)大學(xué)張巖老師的課件第七章圖東南大學(xué)計(jì)算機(jī)學(xué)院方效林本課件借鑒了清華大學(xué)殷人昆老師第七本章主要內(nèi)容圖的基本概念圖的存儲(chǔ)表示圖的遍歷與連通性最小生成樹(shù)最短路徑2本章主要內(nèi)容圖的基本概念2圖的基本概念定義圖是由頂點(diǎn)及頂點(diǎn)之間的關(guān)系集合組成的數(shù)據(jù)結(jié)構(gòu)Graph=(V,E)V是頂點(diǎn)的有窮非空集，V={x|x∈某個(gè)對(duì)象}E是頂點(diǎn)之間關(guān)系，稱(chēng)為邊(edge)的有窮非窮集，E={(x,y)|x,y∈V}3圖的基本概念定義3圖的基本概念有向圖與無(wú)向圖有向圖中，頂點(diǎn)對(duì)(x,y)是有序的無(wú)向圖中，頂點(diǎn)對(duì)(x,y)是無(wú)序的完全圖n個(gè)頂點(diǎn)的無(wú)向圖有n(n-1)/2條邊,該圖為完全圖n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,該圖為完全有向圖421302140完全無(wú)向圖867365無(wú)向圖(自由樹(shù))120有向圖完全有向圖圖的基本概念有向圖與無(wú)向圖421302140完全無(wú)向圖867圖的基本概念鄰接頂點(diǎn)(u,v)是E中的一條邊，則稱(chēng)u與v互為鄰接頂點(diǎn)子圖設(shè)有兩個(gè)圖G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,則稱(chēng)G’是G的子圖權(quán)：邊附帶的權(quán)重，稱(chēng)這樣的圖稱(chēng)為帶權(quán)圖521301302132130子圖圖的基本概念鄰接頂點(diǎn)521301302132130子圖圖的基本概念頂點(diǎn)v的度與v為端點(diǎn)的邊條數(shù)，記作D(v)入度：有向圖中,以v為終點(diǎn)的邊的條數(shù),記作ID(v)出度：有向圖中,以v為始點(diǎn)的邊的條數(shù),記作OD(v)有向圖中v的度為入度與出度的和路徑圖G＝(V,E)中,從頂點(diǎn)vi出發(fā),沿一些邊經(jīng)過(guò)一些頂點(diǎn)vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱(chēng)頂點(diǎn)序列(vivp1vp2...vpmvj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過(guò)的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。6圖的基本概念頂點(diǎn)v的度6圖的基本概念路徑長(zhǎng)度非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和簡(jiǎn)單路徑路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù)回路路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合7圖的基本概念路徑長(zhǎng)度7圖的基本概念連通圖與連通分量無(wú)向圖中,從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱(chēng)頂點(diǎn)v1與v2是連通的。若圖中任意一對(duì)頂點(diǎn)都是連通的,則此圖是連通圖非連通圖的極大連通子圖叫連通分量821304連通圖521304非連通圖(有2個(gè)連通分量)5圖的基本概念連通圖與連通分量821304連通圖521304非圖的基本概念強(qiáng)連通圖與強(qiáng)連通分量在有向圖中,若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱(chēng)此圖是強(qiáng)連通圖非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量生成樹(shù)一個(gè)連通圖的生成樹(shù)是其極小連通子圖，在n個(gè)頂點(diǎn)的情形下，有n-1條邊。9圖的基本概念強(qiáng)連通圖與強(qiáng)連通分量9圖的存儲(chǔ)表示鄰接矩陣一個(gè)有n個(gè)頂點(diǎn)的圖G=(V,E)，

圖的鄰接矩陣是一個(gè)二維數(shù)組

A.edge[n][n]10120有向圖的鄰接矩陣可能不對(duì)稱(chēng)2130無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的圖的存儲(chǔ)表示鄰接矩陣10120有向圖的鄰接矩陣可能不對(duì)稱(chēng)21圖的存儲(chǔ)表示鄰接矩陣網(wǎng)絡(luò)(帶權(quán)圖)的鄰接矩陣11321086395214圖的存儲(chǔ)表示鄰接矩陣11321086395214圖的存儲(chǔ)表示鄰接表無(wú)向圖的鄰接表12DBCA12003CBDA12130datalinkdestlinkdestlinkdest保存的是鄰接頂點(diǎn)的下標(biāo)頂點(diǎn)數(shù)組鏈接結(jié)點(diǎn)圖的存儲(chǔ)表示鄰接表12DBCA12003CBDA12圖的存儲(chǔ)表示鄰接表有向圖的鄰接表和逆鄰接表13102CBA210datalinkdestlinkBCA102CBA210datalinkdestlinkdestlink鄰接表(出邊表)逆鄰接表(入邊表)圖的存儲(chǔ)表示鄰接表13102CBA210datalin圖的存儲(chǔ)表示網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表14鄰接表(出邊表)CDBA86395214CBDA2130datalinkcostlink3063221142destcostlinkdest935182圖的存儲(chǔ)表示網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表14鄰接表(出邊表)CDB圖的遍歷從給定頂點(diǎn)出發(fā)，沿某些邊遍歷圖中所有頂點(diǎn)一次且僅一次使用輔助數(shù)組visited[]標(biāo)識(shí)頂點(diǎn)是否被訪問(wèn)過(guò)visited[]初始為0訪問(wèn)過(guò)后標(biāo)識(shí)為115圖的遍歷從給定頂點(diǎn)出發(fā)，沿某些邊遍歷圖中所有頂點(diǎn)一次且僅一次圖的遍歷遍歷方式深度優(yōu)先遍歷DFS(DepthFirstSearch)廣度優(yōu)先遍歷BFS(BreadthFirstSearch)16圖的遍歷遍歷方式16圖的遍歷遍歷方式深度優(yōu)先遍歷DFS(DepthFirstSearch)從頂點(diǎn)v1出發(fā)，訪問(wèn)任一未被訪問(wèn)的鄰接頂點(diǎn)v2;再?gòu)捻旤c(diǎn)v2出發(fā)，訪問(wèn)任一未被訪問(wèn)的鄰接頂點(diǎn)v3;再?gòu)捻旤c(diǎn)v3出發(fā)，…，如此進(jìn)行下去，直到所有鄰接頂點(diǎn)都被訪問(wèn)過(guò)為止退回一步到剛被訪問(wèn)的頂點(diǎn)，看是否有未被訪問(wèn)的鄰接頂點(diǎn)。若有，則繼續(xù)訪問(wèn)否則，再退回一步直到所有頂點(diǎn)都被訪問(wèn)17圖的遍歷遍歷方式17圖的遍歷遍歷方式深度優(yōu)先遍歷DFS(DepthFirstSearch)18前進(jìn)回退深度優(yōu)先搜索過(guò)程深度優(yōu)先生成樹(shù)ABEDCGFHI123456789ABEDCGFHI123456789圖的遍歷遍歷方式18前進(jìn)回退深度優(yōu)先搜索過(guò)程深度優(yōu)先生成樹(shù)A圖的遍歷遍歷方式廣度優(yōu)先遍歷BFS(BreadthFirstSearch)從起始頂點(diǎn)v出發(fā)，依次訪問(wèn)v的未被訪問(wèn)的鄰接頂點(diǎn)w1,w2,…,wm順序訪問(wèn)w1,w2,…,wm的所有未被訪問(wèn)的鄰接頂點(diǎn),以此類(lèi)推，直到所有頂點(diǎn)都被訪問(wèn)19圖的遍歷遍歷方式19圖的遍歷遍歷方式廣度優(yōu)先遍歷BFS(BreadthFirstSearch)20廣度優(yōu)先搜索過(guò)程廣度優(yōu)先生成樹(shù)ABEDCGFHI125736489ABEDCGFHI125536489圖的遍歷遍歷方式20廣度優(yōu)先搜索過(guò)程廣度優(yōu)先生成樹(shù)ABEDC21作業(yè)：n個(gè)頂點(diǎn)無(wú)向圖，鄰接矩陣形式存儲(chǔ)在矩陣Edge[N][N]，用visited記錄是否訪問(wèn)過(guò)，初始時(shí)visited[N]={0}寫(xiě)出深度優(yōu)先遍歷程序：DFS(0,Edge[][]){}寫(xiě)出廣度優(yōu)先遍歷程序：BFS(0,Edge[][]){}21作業(yè)：圖的遍歷遍歷方式深度優(yōu)先遍歷DFS(DepthFirstSearch)回溯算法廣度優(yōu)先遍歷BFS(BreadthFirstSearch)分層算法22圖的遍歷遍歷方式22圖的連通性當(dāng)無(wú)向圖不連通時(shí)，從頂點(diǎn)v出發(fā)，遍歷方法只能遍歷v所在連通分量上的所有頂點(diǎn)23ACDEGBFHKJLIACDEGBFHKJLI非連通無(wú)向圖一種遍歷生成森林圖的連通性當(dāng)無(wú)向圖不連通時(shí)，從頂點(diǎn)v出發(fā)，遍歷方法只能遍歷v圖的連通性強(qiáng)連通有向圖不同出發(fā)點(diǎn)得到生成樹(shù)不同24ACDEBFACDEBF123465ACDEBF516243234516ACDEBF非強(qiáng)連通圖圖的連通性強(qiáng)連通有向圖24ACDEBFACDEBF12346圖的連通性非強(qiáng)連通有向圖遍歷可能生成的不是樹(shù)，而是森林25345ACB21DEACDEB生成森林ACDEB生成樹(shù)12354非強(qiáng)連通圖D,E不能到達(dá)A,B,C但A,B,C可到達(dá)D,E圖的連通性非強(qiáng)連通有向圖25345ACB21DEACDEB生最小生成樹(shù)在連通帶權(quán)圖上構(gòu)造一棵生成樹(shù)，使得該樹(shù)上邊權(quán)值的總和最小連通帶權(quán)圖生成樹(shù)(n個(gè)頂點(diǎn)，n-1條邊，無(wú)回路)邊的權(quán)值總和最小26最小生成樹(shù)在連通帶權(quán)圖上構(gòu)造一棵生成樹(shù)，使得該樹(shù)上邊權(quán)值的總最小生成樹(shù)克魯斯卡爾(Kruskal)算法初始時(shí)所有頂點(diǎn)自成一連通分量在圖上選權(quán)值最小的邊emin，判斷emin兩端點(diǎn)是否屬于不同連通分量ci,cj若是，將ci,cj用emin連接成同一個(gè)連通分量否則，舍棄emin重復(fù)上一過(guò)程，直到所有頂點(diǎn)在同一連通分量27最小生成樹(shù)克魯斯卡爾(Kruskal)算法27最小生成樹(shù)克魯斯卡爾(Kruskal)算法2828504613210251424221618125046132504613210504613210125046132101412504613210141612504613210142216125046132102514221612最小生成樹(shù)克魯斯卡爾(Kruskal)算法2828504最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度292850461321025142422161812504613210(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)初始時(shí)最小生成樹(shù)克魯斯卡爾(Kruskal)算法2928504最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度30285046132102514242216181210(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)5046132取邊(0,5)最小生成樹(shù)克魯斯卡爾(Kruskal)算法3028504最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度3110(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(2,3)50631422850461321025142422161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3110(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度3210(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(1,6)50631422850461321025142422161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3210(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度3310(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(1,2)50614322850461321025142422161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3310(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度3410(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(3,6)50614322850461321025142422161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3410(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度3510(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(3,4)50614322822504613210251424161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3510(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度3610(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(4,6)50614322822504613210251424161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3610(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度3710(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(4,5)此時(shí)所有頂點(diǎn)屬于同一連通分量，結(jié)束61450322825225046132101424161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3710(0最小生成樹(shù)普里姆(Prim)算法初始時(shí)令生成樹(shù)T為圖中任一頂點(diǎn)v0找u∈T，v?T，且邊(u,v)權(quán)值最小，將v加入T中重復(fù)上一步驟，直到所有頂點(diǎn)都加入T中38最小生成樹(shù)普里姆(Prim)算法38最小生成樹(shù)普里姆(Prim)算法3928504613210251424221618120設(shè)初始時(shí)生成樹(shù)中只有頂點(diǎn)0510010025545043102522504321025221250413210252216125046132102514221612最小生成樹(shù)普里姆(Prim)算法3928504613210最短路徑尋找從一頂點(diǎn)到另一頂點(diǎn)路徑，使得該路徑上邊的權(quán)值總和最小單源最短路徑(一個(gè)頂點(diǎn)到其他頂點(diǎn))非負(fù)權(quán)值(Dijkstra算法)任意權(quán)值(Bellman-Ford算法)所有頂點(diǎn)之間最短路徑Floyd算法40最短路徑尋找從一頂點(diǎn)到另一頂點(diǎn)路徑，使得該路徑上邊的權(quán)值總和最短路徑單源最短路徑的Dijkstra算法給定帶權(quán)圖(每條邊權(quán)值≥0)給定源點(diǎn)v，求v到其他頂點(diǎn)的最短路徑41最短路徑單源最短路徑的Dijkstra算法41最短路徑Dijkstra算法初始時(shí)令S={v0}，dist[v0]=0,dist[i]=Edge[v0][i]找u∈S,v?S,且dist[u]+Edge[u][v]最小,則將v加入S中，dist[v]=dist[u]+Edge[u][v]重復(fù)上一步驟，直到所有頂點(diǎn)都加入S中42最短路徑Dijkstra算法42最短路徑Dijkstra算法(不記錄路徑)10014235030101006020原圖0d=01001d=0d=10d=0d=101001303d=30d=3010012320d=0d=1030d=501001423301020d=0d=10d=30d=50d=60最短路徑Dijkstra算法(不記錄路徑)100142350最短路徑Dijkstra算法(記錄路徑)10014235030101006020原圖0d[0]=0p[0]=-11001d[0]=0p[0]=-1d[1]=10p[1]=0d[0]=0p[0]=-1d[1]=10p[1]=01001303d[3]=30p[3]=0d[3]=30p[3]=010012320d[0]=0p[0]=-1d[1]=10p[1]=030d[2]=50p[2]=31001423301020d[0]=0p[0]=-1d[1]=10p[1]=0d[3]=30p[3]=0d[2]=50p[2]=3d[4]=60p[4]=2最短路徑Dijkstra算法(記錄路徑)1001423503最短路徑Dijkstra算法(記錄路徑)10014235030101006020原圖1001423301020d[0]=0p[0]=-1d[1]=10p[1]=0d[3]=30p[3]=0d[2]=50p[2]=3d[4]=60p[4]=2獲取最短路徑方法，以頂點(diǎn)4為例：p[4]=3p[3]=2p[2]=0反向讀得0到4的最短路徑為(0,3,2,4)最短路徑Dijkstra算法(記錄路徑)1001423503用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)畫(huà)流程圖、工程圖等(用有向圖表示)頂點(diǎn)表示活動(dòng)有向邊表示兩活動(dòng)間的先后關(guān)系一活動(dòng)須先于另一活動(dòng)完成例如蓋樓，打地基和砌墻有先后關(guān)系圖中有向邊(u,v)，則稱(chēng)u是v的直接前驅(qū)，v是u的直接后繼46用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)畫(huà)流程圖、工程圖等(用有向圖用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)給定這樣的有向圖，判斷是否存在有向環(huán)若存在有向環(huán)，這個(gè)有向圖設(shè)計(jì)有問(wèn)題，一個(gè)活動(dòng)不能先于自身完成使用拓?fù)渑判蚺卸ㄊ欠翊嬖谟邢颦h(huán)若能將所有頂點(diǎn)排入拓?fù)湫蛄兄?，則無(wú)有向環(huán)47用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)給定這樣的有向圖，判斷是否存在用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判蚶?，有一些課，課程之間有先修后修關(guān)系48課程代號(hào)課程名稱(chēng)先修課程C1高等數(shù)學(xué)C2程序設(shè)計(jì)基礎(chǔ)C3離散數(shù)學(xué)C1,C2C4數(shù)據(jù)結(jié)構(gòu)C3,C2C5高級(jí)語(yǔ)言程序設(shè)計(jì)C2C6編譯方法C5,C4C7操作系統(tǒng)C4,C9C8普通物理C1C9計(jì)算機(jī)原理C8c1c8c9c7c3c4c2c5c6課程學(xué)習(xí)工程圖用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判?8課程代號(hào)課程名稱(chēng)先用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判蛟趫D中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn)，并輸出刪除輸出的頂點(diǎn)及以它為起點(diǎn)的有向邊重復(fù)以上兩步，直到：所有頂點(diǎn)均輸出(不存在有向環(huán))或找不到?jīng)]有直接前驅(qū)的頂點(diǎn)(存在有向環(huán))49用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判?9用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判蛟趫D中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn)，并輸出刪除輸出的頂點(diǎn)及以它為起點(diǎn)的有向邊重復(fù)以上兩步，直到：所有頂點(diǎn)均輸出(不存在有向環(huán))或找不到?jīng)]有直接前驅(qū)的頂點(diǎn)(存在有向環(huán))50c1c8c9c7c3c4c2c5c6c1c8c2c3c9c4c5c6c7輸出拓?fù)湫蛄校和負(fù)溆行蛐蛄胁皇俏ㄒ坏挠庙旤c(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判?0c1c8c9c7c用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)工程估算(帶權(quán)有向無(wú)環(huán)圖)邊表示活動(dòng)邊上權(quán)值表示活動(dòng)所需時(shí)間頂點(diǎn)表示事件計(jì)算工程至少需要多長(zhǎng)時(shí)間？哪些是關(guān)鍵活動(dòng)(為縮短工期應(yīng)加快哪些活動(dòng))？關(guān)鍵路徑51用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)工程估算(帶權(quán)有向無(wú)環(huán)圖)51用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑事件vi的最早可能開(kāi)始時(shí)間Ve(i)v0到vi的最長(zhǎng)路徑長(zhǎng)度事件vi的最遲允許開(kāi)始時(shí)間Vl(i)結(jié)束點(diǎn)的Ve(n-1)減去vi

到vn-1的最長(zhǎng)路徑長(zhǎng)度活動(dòng)ak的最早可能開(kāi)始時(shí)間Ae(k)，設(shè)ak在邊(i,j)上v0到vi的最長(zhǎng)路徑長(zhǎng)度，

Ae(i)=Ve(i)活動(dòng)ak的最遲允許開(kāi)始時(shí)間Al(k)

，設(shè)ak在邊(i,j)上結(jié)束點(diǎn)的Ve(n-1)減去vj

到vn-1的最長(zhǎng)路徑長(zhǎng)度，再減去ak的長(zhǎng)度，(即Vl(j)-

dur(i,j))用Al[k]-Ae[k]表示活動(dòng)ak的松弛時(shí)間520123a1=6a2=4a3=1a4=1用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑520123a1=6a2用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑先向前遞推計(jì)算各事件的最早可能開(kāi)始時(shí)間Ve[i]Ve[0]=0Ve[i]=max{Ve[x]+dur(x,i)}再逆向遞推計(jì)算各事件的最遲允許開(kāi)始時(shí)間Vl[i]Vl[n-1]=Ve[n-1]Vl[i]=min{Vl[x]-dur(i,x)}根據(jù)各頂點(diǎn)的Ve[i]和Vl[i]，求各有向邊Ae[i]和Al[i]其中Ae[i]==Al[i]即為關(guān)鍵活動(dòng)53用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑53用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑54012345678開(kāi)始結(jié)束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4事件的最早可能開(kāi)始時(shí)間：Ve[i]=max{Ve[x]+dur(x,i)}Ve[0]=0Ve[1]=6Ve[2]=4Ve[3]=5Ve[4]=max{Ve[1]+1,Ve[2]+1}=7Ve[5]=7Ve[6]=16Ve[7]=max{Ve[4]+7,Ve[5]+4}=14Ve[8]=max{Ve[6]+2,Ve[7]+4}=18前驅(qū)頂點(diǎn)Ve[x]邊權(quán)值用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑54012345678開(kāi)用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑55012345678開(kāi)始結(jié)束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4事件的最遲允許開(kāi)始時(shí)間：Vl[i]=min{Vl[x]-dur(i,x)}Vl[0]=min{Vl[1]-6,Vl[2]-4,Vl[3]-5}=0Vl[1]=6Vl[2]=6Vl[3]=8Vl[4]=min{Vl[6]-9,Vl[7]-7}=7Vl[5]=10Vl[6]=16Vl[7]=14Vl[8]=Ve[8]=18后繼頂點(diǎn)Vl[x]邊權(quán)值用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑55012345678開(kāi)用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑56012345678開(kāi)始結(jié)束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Ae[1]=Ve[0]=0Ae[2]=Ve[0]=0Ae[3]=Ve[0]=0Ae[4]=Ve[1]=6Ae[5]=Ve[2]=4Ae[6]=Ve[3]=5Ae[7]=Ve[4]=7Ae[8]=Ve[4]=7Ae[9]=Ve[5]=7Ae[10]=Ve[6]=16Ae[11]=Ve[7]=14活動(dòng)的最早可能開(kāi)始時(shí)間：Ae[k]=Ve[x]邊ak前驅(qū)頂點(diǎn)Ve[x]用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑56012345678開(kāi)用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑57Al[1]=Vl[1]-6=0Al[2]=Vl[2]-4=2Al[3]=Vl[3]-5=3Al[4]=Vl[4]-1=6Al[5]=Vl[4]-1=6Al[6]=Vl[5]-2=8Al[7]=Vl[6]-9=7Al[8]=Vl[7]-7=7Al[9]=Vl[7]-4=10Al[10]=Vl[8]-2=16Al[11]=Vl[8]-4始結(jié)束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4活動(dòng)的最遲允許開(kāi)始時(shí)間：Al[k]=Vl[x]-dur(i,x)邊ak的后繼頂點(diǎn)Vl[x]邊權(quán)值用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑57Al[1]=Vl用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑58012345678開(kāi)始結(jié)束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Ae[i]==Al[i]即為關(guān)鍵活動(dòng)Ae[1]

=0Ae[2]

=0Ae[3]

=0Ae[4]

=6Ae[5]

=4Ae[6]

=5Ae[7]

=7Ae[8]

=7Ae[9]

=7Ae[10]

=16Ae[11]

=14Al[1]

=0Al[2]

=2Al[3]

=3Al[4]

=6Al[5]

=6Al[6]

=8Al[7]

=7Al[8]

=7Al[9]

=10Al[10]

=16Al[11]

=14用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑58012345678開(kāi)東南大學(xué)計(jì)算機(jī)學(xué)院方效林本課件借鑒了清華大學(xué)殷人昆老師和哈爾濱工業(yè)大學(xué)張巖老師的課件第七章圖東南大學(xué)計(jì)算機(jī)學(xué)院方效林本課件借鑒了清華大學(xué)殷人昆老師第七本章主要內(nèi)容圖的基本概念圖的存儲(chǔ)表示圖的遍歷與連通性最小生成樹(shù)最短路徑60本章主要內(nèi)容圖的基本概念2圖的基本概念定義圖是由頂點(diǎn)及頂點(diǎn)之間的關(guān)系集合組成的數(shù)據(jù)結(jié)構(gòu)Graph=(V,E)V是頂點(diǎn)的有窮非空集，V={x|x∈某個(gè)對(duì)象}E是頂點(diǎn)之間關(guān)系，稱(chēng)為邊(edge)的有窮非窮集，E={(x,y)|x,y∈V}61圖的基本概念定義3圖的基本概念有向圖與無(wú)向圖有向圖中，頂點(diǎn)對(duì)(x,y)是有序的無(wú)向圖中，頂點(diǎn)對(duì)(x,y)是無(wú)序的完全圖n個(gè)頂點(diǎn)的無(wú)向圖有n(n-1)/2條邊,該圖為完全圖n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,該圖為完全有向圖6221302140完全無(wú)向圖867365無(wú)向圖(自由樹(shù))120有向圖完全有向圖圖的基本概念有向圖與無(wú)向圖421302140完全無(wú)向圖867圖的基本概念鄰接頂點(diǎn)(u,v)是E中的一條邊，則稱(chēng)u與v互為鄰接頂點(diǎn)子圖設(shè)有兩個(gè)圖G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,則稱(chēng)G’是G的子圖權(quán)：邊附帶的權(quán)重，稱(chēng)這樣的圖稱(chēng)為帶權(quán)圖6321301302132130子圖圖的基本概念鄰接頂點(diǎn)521301302132130子圖圖的基本概念頂點(diǎn)v的度與v為端點(diǎn)的邊條數(shù)，記作D(v)入度：有向圖中,以v為終點(diǎn)的邊的條數(shù),記作ID(v)出度：有向圖中,以v為始點(diǎn)的邊的條數(shù),記作OD(v)有向圖中v的度為入度與出度的和路徑圖G＝(V,E)中,從頂點(diǎn)vi出發(fā),沿一些邊經(jīng)過(guò)一些頂點(diǎn)vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱(chēng)頂點(diǎn)序列(vivp1vp2...vpmvj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過(guò)的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。64圖的基本概念頂點(diǎn)v的度6圖的基本概念路徑長(zhǎng)度非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和簡(jiǎn)單路徑路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù)回路路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合65圖的基本概念路徑長(zhǎng)度7圖的基本概念連通圖與連通分量無(wú)向圖中,從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱(chēng)頂點(diǎn)v1與v2是連通的。若圖中任意一對(duì)頂點(diǎn)都是連通的,則此圖是連通圖非連通圖的極大連通子圖叫連通分量6621304連通圖521304非連通圖(有2個(gè)連通分量)5圖的基本概念連通圖與連通分量821304連通圖521304非圖的基本概念強(qiáng)連通圖與強(qiáng)連通分量在有向圖中,若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱(chēng)此圖是強(qiáng)連通圖非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量生成樹(shù)一個(gè)連通圖的生成樹(shù)是其極小連通子圖，在n個(gè)頂點(diǎn)的情形下，有n-1條邊。67圖的基本概念強(qiáng)連通圖與強(qiáng)連通分量9圖的存儲(chǔ)表示鄰接矩陣一個(gè)有n個(gè)頂點(diǎn)的圖G=(V,E)，

圖的鄰接矩陣是一個(gè)二維數(shù)組

A.edge[n][n]68120有向圖的鄰接矩陣可能不對(duì)稱(chēng)2130無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的圖的存儲(chǔ)表示鄰接矩陣10120有向圖的鄰接矩陣可能不對(duì)稱(chēng)21圖的存儲(chǔ)表示鄰接矩陣網(wǎng)絡(luò)(帶權(quán)圖)的鄰接矩陣69321086395214圖的存儲(chǔ)表示鄰接矩陣11321086395214圖的存儲(chǔ)表示鄰接表無(wú)向圖的鄰接表70DBCA12003CBDA12130datalinkdestlinkdestlinkdest保存的是鄰接頂點(diǎn)的下標(biāo)頂點(diǎn)數(shù)組鏈接結(jié)點(diǎn)圖的存儲(chǔ)表示鄰接表12DBCA12003CBDA12圖的存儲(chǔ)表示鄰接表有向圖的鄰接表和逆鄰接表71102CBA210datalinkdestlinkBCA102CBA210datalinkdestlinkdestlink鄰接表(出邊表)逆鄰接表(入邊表)圖的存儲(chǔ)表示鄰接表13102CBA210datalin圖的存儲(chǔ)表示網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表72鄰接表(出邊表)CDBA86395214CBDA2130datalinkcostlink3063221142destcostlinkdest935182圖的存儲(chǔ)表示網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表14鄰接表(出邊表)CDB圖的遍歷從給定頂點(diǎn)出發(fā)，沿某些邊遍歷圖中所有頂點(diǎn)一次且僅一次使用輔助數(shù)組visited[]標(biāo)識(shí)頂點(diǎn)是否被訪問(wèn)過(guò)visited[]初始為0訪問(wèn)過(guò)后標(biāo)識(shí)為173圖的遍歷從給定頂點(diǎn)出發(fā)，沿某些邊遍歷圖中所有頂點(diǎn)一次且僅一次圖的遍歷遍歷方式深度優(yōu)先遍歷DFS(DepthFirstSearch)廣度優(yōu)先遍歷BFS(BreadthFirstSearch)74圖的遍歷遍歷方式16圖的遍歷遍歷方式深度優(yōu)先遍歷DFS(DepthFirstSearch)從頂點(diǎn)v1出發(fā)，訪問(wèn)任一未被訪問(wèn)的鄰接頂點(diǎn)v2;再?gòu)捻旤c(diǎn)v2出發(fā)，訪問(wèn)任一未被訪問(wèn)的鄰接頂點(diǎn)v3;再?gòu)捻旤c(diǎn)v3出發(fā)，…，如此進(jìn)行下去，直到所有鄰接頂點(diǎn)都被訪問(wèn)過(guò)為止退回一步到剛被訪問(wèn)的頂點(diǎn)，看是否有未被訪問(wèn)的鄰接頂點(diǎn)。若有，則繼續(xù)訪問(wèn)否則，再退回一步直到所有頂點(diǎn)都被訪問(wèn)75圖的遍歷遍歷方式17圖的遍歷遍歷方式深度優(yōu)先遍歷DFS(DepthFirstSearch)76前進(jìn)回退深度優(yōu)先搜索過(guò)程深度優(yōu)先生成樹(shù)ABEDCGFHI123456789ABEDCGFHI123456789圖的遍歷遍歷方式18前進(jìn)回退深度優(yōu)先搜索過(guò)程深度優(yōu)先生成樹(shù)A圖的遍歷遍歷方式廣度優(yōu)先遍歷BFS(BreadthFirstSearch)從起始頂點(diǎn)v出發(fā)，依次訪問(wèn)v的未被訪問(wèn)的鄰接頂點(diǎn)w1,w2,…,wm順序訪問(wèn)w1,w2,…,wm的所有未被訪問(wèn)的鄰接頂點(diǎn),以此類(lèi)推，直到所有頂點(diǎn)都被訪問(wèn)77圖的遍歷遍歷方式19圖的遍歷遍歷方式廣度優(yōu)先遍歷BFS(BreadthFirstSearch)78廣度優(yōu)先搜索過(guò)程廣度優(yōu)先生成樹(shù)ABEDCGFHI125736489ABEDCGFHI125536489圖的遍歷遍歷方式20廣度優(yōu)先搜索過(guò)程廣度優(yōu)先生成樹(shù)ABEDC79作業(yè)：n個(gè)頂點(diǎn)無(wú)向圖，鄰接矩陣形式存儲(chǔ)在矩陣Edge[N][N]，用visited記錄是否訪問(wèn)過(guò)，初始時(shí)visited[N]={0}寫(xiě)出深度優(yōu)先遍歷程序：DFS(0,Edge[][]){}寫(xiě)出廣度優(yōu)先遍歷程序：BFS(0,Edge[][]){}21作業(yè)：圖的遍歷遍歷方式深度優(yōu)先遍歷DFS(DepthFirstSearch)回溯算法廣度優(yōu)先遍歷BFS(BreadthFirstSearch)分層算法80圖的遍歷遍歷方式22圖的連通性當(dāng)無(wú)向圖不連通時(shí)，從頂點(diǎn)v出發(fā)，遍歷方法只能遍歷v所在連通分量上的所有頂點(diǎn)81ACDEGBFHKJLIACDEGBFHKJLI非連通無(wú)向圖一種遍歷生成森林圖的連通性當(dāng)無(wú)向圖不連通時(shí)，從頂點(diǎn)v出發(fā)，遍歷方法只能遍歷v圖的連通性強(qiáng)連通有向圖不同出發(fā)點(diǎn)得到生成樹(shù)不同82ACDEBFACDEBF123465ACDEBF516243234516ACDEBF非強(qiáng)連通圖圖的連通性強(qiáng)連通有向圖24ACDEBFACDEBF12346圖的連通性非強(qiáng)連通有向圖遍歷可能生成的不是樹(shù)，而是森林83345ACB21DEACDEB生成森林ACDEB生成樹(shù)12354非強(qiáng)連通圖D,E不能到達(dá)A,B,C但A,B,C可到達(dá)D,E圖的連通性非強(qiáng)連通有向圖25345ACB21DEACDEB生最小生成樹(shù)在連通帶權(quán)圖上構(gòu)造一棵生成樹(shù)，使得該樹(shù)上邊權(quán)值的總和最小連通帶權(quán)圖生成樹(shù)(n個(gè)頂點(diǎn)，n-1條邊，無(wú)回路)邊的權(quán)值總和最小84最小生成樹(shù)在連通帶權(quán)圖上構(gòu)造一棵生成樹(shù)，使得該樹(shù)上邊權(quán)值的總最小生成樹(shù)克魯斯卡爾(Kruskal)算法初始時(shí)所有頂點(diǎn)自成一連通分量在圖上選權(quán)值最小的邊emin，判斷emin兩端點(diǎn)是否屬于不同連通分量ci,cj若是，將ci,cj用emin連接成同一個(gè)連通分量否則，舍棄emin重復(fù)上一過(guò)程，直到所有頂點(diǎn)在同一連通分量85最小生成樹(shù)克魯斯卡爾(Kruskal)算法27最小生成樹(shù)克魯斯卡爾(Kruskal)算法8628504613210251424221618125046132504613210504613210125046132101412504613210141612504613210142216125046132102514221612最小生成樹(shù)克魯斯卡爾(Kruskal)算法2828504最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度872850461321025142422161812504613210(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)初始時(shí)最小生成樹(shù)克魯斯卡爾(Kruskal)算法2928504最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度88285046132102514242216181210(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)5046132取邊(0,5)最小生成樹(shù)克魯斯卡爾(Kruskal)算法3028504最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度8910(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(2,3)50631422850461321025142422161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3110(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度9010(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(1,6)50631422850461321025142422161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3210(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度9110(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(1,2)50614322850461321025142422161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3310(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度9210(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(3,6)50614322850461321025142422161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3410(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度9310(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(3,4)50614322822504613210251424161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3510(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度9410(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(4,6)50614322822504613210251424161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3610(0最小生成樹(shù)克魯斯卡爾(Kruskal)算法經(jīng)常需要判斷權(quán)值最小的邊的兩端是否屬于不同連通分量可使用并查集技術(shù)加快判斷速度9510(0,5)12(2,3)14(1,6)16(1,2)18(3,6)22(3,4)24(4,6)25(4,5)取邊(4,5)此時(shí)所有頂點(diǎn)屬于同一連通分量，結(jié)束61450322825225046132101424161812最小生成樹(shù)克魯斯卡爾(Kruskal)算法3710(0最小生成樹(shù)普里姆(Prim)算法初始時(shí)令生成樹(shù)T為圖中任一頂點(diǎn)v0找u∈T，v?T，且邊(u,v)權(quán)值最小，將v加入T中重復(fù)上一步驟，直到所有頂點(diǎn)都加入T中96最小生成樹(shù)普里姆(Prim)算法38最小生成樹(shù)普里姆(Prim)算法9728504613210251424221618120設(shè)初始時(shí)生成樹(shù)中只有頂點(diǎn)0510010025545043102522504321025221250413210252216125046132102514221612最小生成樹(shù)普里姆(Prim)算法3928504613210最短路徑尋找從一頂點(diǎn)到另一頂點(diǎn)路徑，使得該路徑上邊的權(quán)值總和最小單源最短路徑(一個(gè)頂點(diǎn)到其他頂點(diǎn))非負(fù)權(quán)值(Dijkstra算法)任意權(quán)值(Bellman-Ford算法)所有頂點(diǎn)之間最短路徑Floyd算法98最短路徑尋找從一頂點(diǎn)到另一頂點(diǎn)路徑，使得該路徑上邊的權(quán)值總和最短路徑單源最短路徑的Dijkstra算法給定帶權(quán)圖(每條邊權(quán)值≥0)給定源點(diǎn)v，求v到其他頂點(diǎn)的最短路徑99最短路徑單源最短路徑的Dijkstra算法41最短路徑Dijkstra算法初始時(shí)令S={v0}，dist[v0]=0,dist[i]=Edge[v0][i]找u∈S,v?S,且dist[u]+Edge[u][v]最小,則將v加入S中，dist[v]=dist[u]+Edge[u][v]重復(fù)上一步驟，直到所有頂點(diǎn)都加入S中100最短路徑Dijkstra算法42最短路徑Dijkstra算法(不記錄路徑)10014235030101006020原圖0d=01001d=0d=10d=0d=101001303d=30d=3010012320d=0d=1030d=501001423301020d=0d=10d=30d=50d=60最短路徑Dijkstra算法(不記錄路徑)100142350最短路徑Dijkstra算法(記錄路徑)10014235030101006020原圖0d[0]=0p[0]=-11001d[0]=0p[0]=-1d[1]=10p[1]=0d[0]=0p[0]=-1d[1]=10p[1]=01001303d[3]=30p[3]=0d[3]=30p[3]=010012320d[0]=0p[0]=-1d[1]=10p[1]=030d[2]=50p[2]=31001423301020d[0]=0p[0]=-1d[1]=10p[1]=0d[3]=30p[3]=0d[2]=50p[2]=3d[4]=60p[4]=2最短路徑Dijkstra算法(記錄路徑)1001423503最短路徑Dijkstra算法(記錄路徑)10014235030101006020原圖1001423301020d[0]=0p[0]=-1d[1]=10p[1]=0d[3]=30p[3]=0d[2]=50p[2]=3d[4]=60p[4]=2獲取最短路徑方法，以頂點(diǎn)4為例：p[4]=3p[3]=2p[2]=0反向讀得0到4的最短路徑為(0,3,2,4)最短路徑Dijkstra算法(記錄路徑)1001423503用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)畫(huà)流程圖、工程圖等(用有向圖表示)頂點(diǎn)表示活動(dòng)有向邊表示兩活動(dòng)間的先后關(guān)系一活動(dòng)須先于另一活動(dòng)完成例如蓋樓，打地基和砌墻有先后關(guān)系圖中有向邊(u,v)，則稱(chēng)u是v的直接前驅(qū)，v是u的直接后繼104用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)畫(huà)流程圖、工程圖等(用有向圖用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)給定這樣的有向圖，判斷是否存在有向環(huán)若存在有向環(huán)，這個(gè)有向圖設(shè)計(jì)有問(wèn)題，一個(gè)活動(dòng)不能先于自身完成使用拓?fù)渑判蚺卸ㄊ欠翊嬖谟邢颦h(huán)若能將所有頂點(diǎn)排入拓?fù)湫蛄兄?，則無(wú)有向環(huán)105用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)給定這樣的有向圖，判斷是否存在用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判蚶?，有一些課，課程之間有先修后修關(guān)系106課程代號(hào)課程名稱(chēng)先修課程C1高等數(shù)學(xué)C2程序設(shè)計(jì)基礎(chǔ)C3離散數(shù)學(xué)C1,C2C4數(shù)據(jù)結(jié)構(gòu)C3,C2C5高級(jí)語(yǔ)言程序設(shè)計(jì)C2C6編譯方法C5,C4C7操作系統(tǒng)C4,C9C8普通物理C1C9計(jì)算機(jī)原理C8c1c8c9c7c3c4c2c5c6課程學(xué)習(xí)工程圖用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判?8課程代號(hào)課程名稱(chēng)先用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判蛟趫D中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn)，并輸出刪除輸出的頂點(diǎn)及以它為起點(diǎn)的有向邊重復(fù)以上兩步，直到：所有頂點(diǎn)均輸出(不存在有向環(huán))或找不到?jīng)]有直接前驅(qū)的頂點(diǎn)(存在有向環(huán))107用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判?9用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判蛟趫D中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn)，并輸出刪除輸出的頂點(diǎn)及以它為起點(diǎn)的有向邊重復(fù)以上兩步，直到：所有頂點(diǎn)均輸出(不存在有向環(huán))或找不到?jīng)]有直接前驅(qū)的頂點(diǎn)(存在有向環(huán))108c1c8c9c7c3c4c2c5c6c1c8c2c3c9c4c5c6c7輸出拓?fù)湫蛄校和負(fù)溆行蛐蛄胁皇俏ㄒ坏挠庙旤c(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV)拓?fù)渑判?0c1c8c9c7c用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)工程估算(帶權(quán)有向無(wú)環(huán)圖)邊表示活動(dòng)邊上權(quán)值表示活動(dòng)所需時(shí)間頂點(diǎn)表示事件計(jì)算工程至少需要多長(zhǎng)時(shí)間？哪些是關(guān)鍵活動(dòng)(為縮短工期應(yīng)加快哪些活動(dòng))？關(guān)鍵路徑109用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)工程估算(帶權(quán)有向無(wú)環(huán)圖)51用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑事件vi的最早可能開(kāi)始時(shí)間Ve(i)v0到vi的最長(zhǎng)路徑長(zhǎng)度事件vi的最遲允許開(kāi)始時(shí)間Vl(i)結(jié)束點(diǎn)的Ve(n-1)減去vi

到vn-1的最長(zhǎng)路徑長(zhǎng)度活動(dòng)ak的最早可能開(kāi)始時(shí)間Ae(k)，設(shè)ak在邊(i,j)上v0到vi的最長(zhǎng)路徑長(zhǎng)度，

Ae(i)=Ve(i)活動(dòng)ak的最遲允許開(kāi)始時(shí)間Al(k)

，設(shè)ak在邊(i,j)上結(jié)束點(diǎn)的Ve(n-1)減去vj

到vn-1的最長(zhǎng)路徑長(zhǎng)度，再減去ak的長(zhǎng)度，(即Vl(j)-

dur(i,j))用Al[k]-Ae[k]表示活動(dòng)ak的松弛時(shí)間1100123a1=6a2=4a3=1a4=1用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑520123a1=6a2用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE)關(guān)鍵路徑先向前遞推計(jì)算各事件的最早可能開(kāi)始時(shí)間Ve[i]Ve[0]=0Ve[i]=max{Ve[x]+dur(x,i)}再逆向遞推計(jì)算各事件的最遲允許開(kāi)始時(shí)間Vl[i]