數(shù)結7圖j3

1、7.5.1 拓撲排序,AOV網(Activity On Vertex Network) 頂點表示活動的網。通常用來表示一個工程 頂點: 表示活動(子工程） 有向邊: 表示活動的次序關系,活動Vi領先于活動Vj發(fā)生或者說活動Vi是活動Vj的先決條件,例如：計算機系學生的課程計劃(P181),C1,C4,C10,C11,C12,C2,C3,C6,C5,C8,C9,C7,,,,,,,

2、,,,,,,,,,,課程之間的先修關系可以用下面所示AOV網表示：,假定一次學習一門課。問題：按什么次序進行各門課的學習, 能夠保證在學習某門課程時該課程的先修課已經學過了？,AOV網中不應該出現(xiàn)環(huán)。否則將意味著某個活動將以自己為先決條件，這顯然是荒謬的。,前趨活動：在AOV網中, 如果Vi到Vj有路徑，則稱Vi是Vj的前趨活動。拓撲序列：將AOV網中的所有活動排成一個線性序列，使得在這個序列中每個活動的前趨活動都排在該活動的前面。

3、拓撲排序：對AOV網求拓撲序列的操作,C1,C4,C10,C11,C12,C2,C3,C6,C5,C8,C9,C7,,,,,,,,,,,,,,,,,拓撲序列： C1, C2, C4, C3, C5, C9, C10, C11, C12, C6, C7, C8 C9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8,拓撲排序的方法： 1. 從AOV網中任選

4、一個入度為0的頂點輸出 2. 在AOV網中刪除這個頂點及其相關聯(lián)的所有出邊 3. 若AOV網中還有頂點未輸出，則轉1，直至所有頂點都被輸出 。,C1,C4,C10,C11,C12,C2,C3,C6,C5,C8,C9,C7,,,,,,,,,,,,,,,,,拓撲序列:,C1,C4,C2,C7,C5,C3,C9,C11,C10,C12,C6,C8,拓撲排序算法思想： 設有向圖用鄰接表表示，用一維數(shù)組inde

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

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

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

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

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

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

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

12、 當G.arcs[V0][ i ] !=∞,選取D[j]為最小且S[j]==0的藍點Vj，將其并入紅點集，即令S[ j ]=1；調整剩余藍點Vw到源點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)條最短路徑。 假設求Vi到Vj的最短路徑。 一種可能是直達； 另一種可能是經過若干個中轉點到達。 我們把V1, V2, ..., Vn分別插入到Vi至V

16、j的路徑中，檢測是否能使得路徑長度變短，從而找到Vi到Vj的一條最短路徑。,存儲結構： 二維數(shù)組D[n][n]：存放當前求得的n×(n-1)條最短路徑： D[ i ][ j ] = Vi到Vj的最短路徑 初值：D[ i ][ j ] = G.arcs[ i ][ j ] 三維數(shù)組P[n][n][n]：存放與數(shù)組A對應的路徑

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

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