【正文】 a b c d e f g h 2 6 6 7 3 4 6 4 5 5 ? ? ? ? ? ? 0 0 1 1 2 2 3 1 indegree 0 1 2 3 4 5 6 7 s a b 輸出次序 : b 02hh 1a 0 1 cc d 0d g f e 000 算法描述 Status Topologicalsort(ALGraph G) { FindinDegree(G,indegree)。 Count=0。 for(p=[i].firstarc。 } } if(count) return ERROR。 整個工程完成的時間為 ：從有向圖的 源點 到 匯點的最長路徑。 Status TopologicalOrder(ALGraph G,Stack amp。 ve[0..]=0。 for(p=[j].firstarc。 if(ve[j]+*(pinfo)=dut(j,k) ve[k]=ve[j]+*(pinfo)。 vl[0.. ]=ve[]。 dut=*(pinfo)。++j) for(p=[j] .firstarc。 ee=ve[j]。 v2 這條路徑 必定是直接從源點到該點 v1只含一條弧 ，并且這條弧的 權(quán)值最小。 求最短路徑的迪杰斯特拉算法： 一般情況下， Dist[k] = 源點到頂點 k 的弧上的權(quán)值 或者 = 源點到 已求出最短路徑的頂點 的路徑長度 + 已求出最短路徑的頂點 到頂點 k 的 弧上的 權(quán)值 。 假設(shè)求得最短路徑的頂點為 u， 若 Dist[u]+[u][k]Dist[k] 則將 Dist[k] 改為 Dist[u]+[u][k]。D) { for(v=0。 for(w=0。P[v][v]=TRUE。i。++w) if(!final[w]) if(D[w]min) {v=w。w。 P[w]=P[v]。 A B C 6 4 2 11 3 D D(1) D(0) D(1) D(2) 0 1 2 0 1 2 0 1 2 0 1 2 0 0 4 11 0 4 11 0 4 6 0 4 6 1 6 0 2 6 0 2 6 0 2 5 0 2 2 3 ∞ 0 3 7 0 3 7 0 3 7 0 P P(1) P(0) P(1) P(2) 0 1 2 0 1 2 0 1 2 0 1 2 0 AB AC AB AC AB ABC AB ABC 1 BA BC BA BC BA BC BAC BC 2 CA CA CAB CA CAB CA CAB 0 4 11 6 0 2 3 ∞ 0 A B C A B C 0 1 2 。 } } } 求每一對頂點之間的最短路徑 弗洛伊德算法的基本思想是： 從 vi 到 vj 的所有可能存在的路徑中，選出一條長度最短的路徑 。amp。} final[v]=TRUE。 for(w=0。 fimal[v0]=TRUE。++w) P[v][w]=FALSE。++v) { final[v]=FALSE。 v0 v1 v2 v3 v4 v5 100 60 10 5 50 10 30 20 ∞ 10 ∞ 30 100 D 0 1 2 3 4 5 F F F F F F final 0 1 2 3 4 5 0 ∞ 10 ∞ 30 100 ∞ 0 5 ∞ ∞ ∞ ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ 0 ∞ 10 ∞ ∞ ∞ 20 0 60 ∞ ∞ ∞ ∞ ∞ 0 0 1 2 3 4 5 0 1 2 3 4 5 P 鄰接矩陣 T T60 T50 90 T 60TVoid ShortestPath_DIJ(MGraph G,int v0,PathMatrix amp。 1）在所有從源點出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。 其余最短路徑的特點： 再下一條 路徑長度次短 的最短路徑的特點 : 它可能有三種情況：或者是 直接從源點到該點 v3(只含一條弧 )； 或者是 從源點經(jīng)過頂點 v1，再到達該頂點 (由兩條弧組成 )；或者是從源點經(jīng)過頂點 v2，再到達該頂點 v3。 tag=(ee==el)? ?*?:?? printf(j,k,dut,ee,el,tag)。p=pnextarc) { k=padjvex。 } for(j=0。 p。 else return OK。 p=pnextarc) { k=padjvex。Push(T,j)。 InitStack(T)。 假設(shè)第 i 條弧為 j, k 則 對第 i 項活動言 “活動 (弧 )”的 最早開始時間 e(i) e(i) = ve(j)； “活動 (弧 )”的 最遲開始時間 l(i) l(i) = vl(k) – dut(j,k)； 活動 ai的時間余量 ： l(i) e(i) 若 l[k] == e[k] 表示活動 ai是關(guān)鍵活動。 問：哪些子工程項是“關(guān)鍵工程”？ 即：哪些子工程項將影響整個工程的完成期限的。p=pnextarc) { k=padjvex。 printf(i,[i].data)。i。 例如：對于下列有向圖 B D A C 可求得 拓撲有序序列 ： A B C D 或 A C B D 由此所得頂點的線性序列稱之為拓撲有序序列 B D A C 反之，對于下列有向圖 不能求得它的拓撲有序序列。 且 k++。 k = i = 0。 ++j) //修改其它頂點的最小邊 if ([k][j].adj closedge[j].lowcost) closedge[j] = { [k], [k][j].adj }。 // 求出加入生成樹的下一個頂點 (k) printf(closedge[k].adjvex, [k])。 // 初始， U＝ {u} for (i=0。 for ( j=0。 一般情況下所添加的頂點應(yīng)滿足下列條件 : a b c d e g f 例如 : 19 5 14 18 27 16 8 21 3 12 7 所得生成樹權(quán)值和 = 14+8+3+5+16+21 = 67 設(shè)置一個輔助數(shù)組， 對每個頂點 ，記錄從頂點集 U到 V－ U具有 代價最小 的邊： struct { VertexType adjvex。 算法二：（克魯斯卡爾算法） 該問題等價于： 算法一：（普里姆算法） 假設(shè) N={V,{E})是連通網(wǎng) ， TE是 N上最小 生 成 樹 邊 的 集 合 。 圖的連通性問題 L E D H G A B F I C J K M 若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷 , 可求得無向圖的所有連通分量。 w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]=TRUE。 // 訪問 u EnQueue(Q, v)。 // 置空的輔助隊列 Q for ( v=0。 V w1 w8 w3 w7 w6 w2 w5 w4 F F F F F F F F F T T T T T T T T