數(shù)結(jié)7圖j3

1、7.5.1 拓?fù)渑判?AOV網(wǎng)(Activity On Vertex Network) 頂點(diǎn)表示活動(dòng)的網(wǎng)。通常用來(lái)表示一個(gè)工程 頂點(diǎn): 表示活動(dòng)(子工程） 有向邊: 表示活動(dòng)的次序關(guān)系,活動(dòng)Vi領(lǐng)先于活動(dòng)Vj發(fā)生或者說(shuō)活動(dòng)Vi是活動(dòng)Vj的先決條件,例如：計(jì)算機(jī)系學(xué)生的課程計(jì)劃(P181),C1,C4,C10,C11,C12,C2,C3,C6,C5,C8,C9,C7,,,,,,,

2、,,,,,,,,,,課程之間的先修關(guān)系可以用下面所示AOV網(wǎng)表示：,假定一次學(xué)習(xí)一門課。問(wèn)題：按什么次序進(jìn)行各門課的學(xué)習(xí), 能夠保證在學(xué)習(xí)某門課程時(shí)該課程的先修課已經(jīng)學(xué)過(guò)了？,AOV網(wǎng)中不應(yīng)該出現(xiàn)環(huán)。否則將意味著某個(gè)活動(dòng)將以自己為先決條件，這顯然是荒謬的。,前趨活動(dòng)：在AOV網(wǎng)中, 如果Vi到Vj有路徑，則稱Vi是Vj的前趨活動(dòng)。拓?fù)湫蛄校簩OV網(wǎng)中的所有活動(dòng)排成一個(gè)線性序列，使得在這個(gè)序列中每個(gè)活動(dòng)的前趨活動(dòng)都排在該活動(dòng)的前面。

3、拓?fù)渑判颍簩?duì)AOV網(wǎng)求拓?fù)湫蛄械牟僮?C1,C4,C10,C11,C12,C2,C3,C6,C5,C8,C9,C7,,,,,,,,,,,,,,,,,拓?fù)湫蛄校?C1, C2, C4, C3, C5, C9, C10, C11, C12, C6, C7, C8 C9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8,拓?fù)渑判虻姆椒ǎ?1. 從AOV網(wǎng)中任選

4、一個(gè)入度為0的頂點(diǎn)輸出 2. 在AOV網(wǎng)中刪除這個(gè)頂點(diǎn)及其相關(guān)聯(lián)的所有出邊 3. 若AOV網(wǎng)中還有頂點(diǎn)未輸出，則轉(zhuǎn)1，直至所有頂點(diǎn)都被輸出 。,C1,C4,C10,C11,C12,C2,C3,C6,C5,C8,C9,C7,,,,,,,,,,,,,,,,,拓?fù)湫蛄?,C1,C4,C2,C7,C5,C3,C9,C11,C10,C12,C6,C8,拓?fù)渑判蛩惴ㄋ枷耄?設(shè)有向圖用鄰接表表示，用一維數(shù)組inde

5、gree[n]來(lái)存放每個(gè)頂點(diǎn)的入度。刪除入度為0的頂點(diǎn)V以及V的出邊可以這樣來(lái)實(shí)現(xiàn)：將V的出邊鄰接點(diǎn)的入度值減1。為了避免反復(fù)檢測(cè)入度為0的頂點(diǎn)，用一個(gè)棧來(lái)暫存入度為0的頂點(diǎn)。,V1,V5,V3,V2,V4,V6,,,,,,,,,,,,,,,,,P182 算法7.12Status TopologicalSort( ALGraph, G){ FindInDegree(G, indegree)； //求每個(gè)頂點(diǎn)的入度

6、 InitStack(S); //初始化一個(gè)空棧 for(i=0; inextarc) { k=p->adjvex; indegree[k] - - ; //Vi的出邊鄰接點(diǎn)Vk的入度減 1 if( !indegree[k] ) Push(S, k); //若V

7、k的入度為0則進(jìn)棧 } } if(count< G.vexnum) return Error; else return OK; },§7.6 最短路徑,7.6.1 頂點(diǎn)之間邊數(shù)最少的路徑(BFS算法)7.6.2 單源最短路徑(Dijkstra算法)7.6.3 各對(duì)頂點(diǎn)之間的最短路徑(Floyd算法),7.6.1 頂點(diǎn)之間邊數(shù)最少的路徑

8、廣度優(yōu)先搜索遍歷是一種相對(duì)于出發(fā)點(diǎn)由近及遠(yuǎn)的遍歷過(guò)程。以出發(fā)點(diǎn)為樹(shù)根的BFS生成樹(shù)上，根到每個(gè)結(jié)點(diǎn)的路徑就是邊數(shù)最少的路徑,7.6.2 單源最短路徑最短路徑： 從出發(fā)點(diǎn)到終點(diǎn)的權(quán)之和為最小的路徑。,,V1至V5的路徑有5條：V1→ V5 65V1→ V2→ V5 33V1→ V3→ V4→ V5

9、80V1→ V2→ V4→ V5 108V1→ V2→ V3→ V4 → V5 88,單源最短路徑： 求出發(fā)點(diǎn)到圖中其余n-1個(gè)頂點(diǎn)的最短的路徑。,,Dijkstra算法思想：按路徑長(zhǎng)度遞增的次序逐個(gè)求出每個(gè)頂點(diǎn)的最短的路徑。,,可見(jiàn)， V1到Vj的最短路徑上如果有中轉(zhuǎn)點(diǎn)，中轉(zhuǎn)點(diǎn)一定是先于Vj而被求得了最短路徑的頂點(diǎn),紅點(diǎn)：最短路徑已經(jīng)確定的頂點(diǎn)藍(lán)點(diǎn)：最短路徑尚未確定的頂點(diǎn)初態(tài)：紅點(diǎn)

10、集中只有出發(fā)點(diǎn)V0，藍(lán)點(diǎn)集中有待求的n－1個(gè)頂點(diǎn)求解過(guò)程：按Dijkstra算法思想，每次挑選與源點(diǎn)路徑長(zhǎng)度最短的藍(lán)點(diǎn)變成紅點(diǎn)。,假定當(dāng)前要將藍(lán)點(diǎn)Vj變成紅點(diǎn)，按Dijkstra算法思想，源點(diǎn)到Vj的最短路徑長(zhǎng)度一定大于到所有紅點(diǎn)的路徑長(zhǎng)度，小于到其余藍(lán)點(diǎn)的路徑長(zhǎng)度。如果這條路徑上有中轉(zhuǎn)點(diǎn)，則中轉(zhuǎn)點(diǎn)只能是紅點(diǎn)。,,算法的存儲(chǔ)結(jié)構(gòu)：圖G用鄰接矩陣表示；一維數(shù)組D[n], D[ i ]=當(dāng)前求得的源點(diǎn)到頂點(diǎn)Vi的最短路徑；二維數(shù)組P

11、[n][n], 記錄與D[ i ]對(duì)應(yīng)的路徑上的頂點(diǎn)序列；一維數(shù)組S[n], 標(biāo)志；S[ i ]=0---Vi是藍(lán)點(diǎn)； S[ i ]=1--- Vi是紅點(diǎn)；,初態(tài):D[ i ] = G.arcs[V0][ i ] 鄰接矩陣的第V0行S[V0]=1; S[ i ]=0 當(dāng)i != V0P[ i ][0]= V0, P[ i ][ 1 ]= i

12、 當(dāng)G.arcs[V0][ i ] !=∞,選取D[j]為最小且S[j]==0的藍(lán)點(diǎn)Vj，將其并入紅點(diǎn)集，即令S[ j ]=1；調(diào)整剩余藍(lán)點(diǎn)Vw到源點(diǎn)V0的最短距離，如果,則用新路徑取代老路徑： if (D[ j ]+G.arcs[ j ][w]<D[w] ) { D[w]=D[ j ]+G.arcs[ j ][w] for( k=0; P[w][k]

13、 != -1; k++) P[w][k]=P[ j ][k]; P[w][k]=w; P[ w ][k+1]=－1; },G.arcs=,P=,G.arcs=,P=,V6,V5,V2,V3,,,,,,,,,,,,V4,23,10,30,20,15,15,20,17,8,35,50,,,∞,V1,,65,,∞,,G.arcs=,P=,V6,V5,V2,V3,,,,,,,,,,,,V4,2

14、3,10,30,20,15,15,20,17,8,35,50,,,∞,V1,,65,,∞,,G.arcs=,P=,V6,V5,V2,V3,,,,,,,,,,,,V4,23,10,30,20,15,15,20,17,8,35,50,,,∞,V1,,65,,∞,,G.arcs=,P=,V6,V5,V2,V3,,,,,,,,,,,,V4,23,10,30,20,15,15,20,17,8,35,50,,,∞,V1,,65,,∞,,G.arcs

15、=,P=,V6,V5,V2,V3,,,,,,,,,,,,V4,23,10,30,20,15,15,20,17,8,35,50,,,∞,V1,,65,,∞,Floyd算法思想： 窮舉出各種可能的路徑，從中得出n×(n-1)條最短路徑。 假設(shè)求Vi到Vj的最短路徑。 一種可能是直達(dá)； 另一種可能是經(jīng)過(guò)若干個(gè)中轉(zhuǎn)點(diǎn)到達(dá)。 我們把V1, V2, ..., Vn分別插入到Vi至V

16、j的路徑中，檢測(cè)是否能使得路徑長(zhǎng)度變短，從而找到Vi到Vj的一條最短路徑。,存儲(chǔ)結(jié)構(gòu)： 二維數(shù)組D[n][n]：存放當(dāng)前求得的n×(n-1)條最短路徑： D[ i ][ j ] = Vi到Vj的最短路徑 初值：D[ i ][ j ] = G.arcs[ i ][ j ] 三維數(shù)組P[n][n][n]：存放與數(shù)組A對(duì)應(yīng)的路徑

17、上的頂點(diǎn)序列。,C,A,B,D,,,,,,,,,2,3,6,8,1,5,9,4,初態(tài)： D(0)[ i ][ j ]=G.arcs[ i ][ j ]測(cè)試將V1插入到路徑中： D(1)[ i ][ j ]=min( D(0)[ i ][ j ], D(0)[ i ][ 1 ]+D(0)[ 1 ][ j ] )測(cè)試將V2插入到路徑中： D(2)[ i ][ j ]=min( D(1)[ i

18、 ][ j ], D(1)[ i ][ 2 ]+D(1)[ 2 ][ j ] ) … …測(cè)試將Vk插入到路徑中： D(k)[ i ][ j ]=min( D(k-1)[ i ][ j ], D(k-1)[ i ][ k ]+D(k-1)[ k ][ j ] ) … …測(cè)試將Vn插入到路徑中： D(n)[ i ][ j ]=min( D(n-1)[ i ][ j ], D(