【正文】 ?設(shè)一有向網(wǎng)絡(luò) G =（ V,E），已知各邊的權(quán)值，并設(shè)每邊的權(quán)均大于零，以某指定 V0為源點(diǎn)，求從 V0到圖的其余各點(diǎn)的最短路徑。 S∈V, 初值為 S={V0} 一維數(shù)組 dist[]: dist[i] 表示從 V0到 Vi的最 短路徑 ,其初值為鄰接矩陣 cost[i,*]. Vj, 使 dist[j]=min{ dist[i] | Vi ∈ VS} 并令 S=S∪Vj VS中頂點(diǎn) Vi的最短路徑 dist[i]. 若 dist[i] dist[j] + cost[j,i] 則 dist[i] = dist[j] + cost[j,i] 2, 3步 n1次 . Void shortpath(cost,V0,dist,path) { for(i=0。 /*集合的并運(yùn)算 else path[i]=[]。 k++) { wm=max。 i++) /*選擇最小的 dist[i] if (i !∈ S) amp。 } S=S + [j]。amp。 di s t 5 ∞ 25 0 25 ∞ 0 0 0 0 1 0 1 2 3 4 5 6 S 圖 算法動(dòng)態(tài)執(zhí)行情況 di s t 5 12 25 0 23 ∞ 1 0 0 0 1 0 1 2 3 4 5 6 S di s t 5 12 25 0 21 ∞ 1 1 0 0 1 0 1 2 3 4 5 6 S di s t 5 12 25 0 21 ∞ 1 1 0 0 1 1 1 2 3 4 5 6 S di st 5 12 25 0 21 ∞ 1 1 1 0 1 1 1 2 3 4 5 6 S 返回 拓?fù)渑判? ?在工程實(shí)踐中，一個(gè)工程項(xiàng)目往往由若干個(gè)子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系： ①先后關(guān)系，即必須在一子項(xiàng)目完成后，才能開(kāi)始實(shí)施另一個(gè)子項(xiàng)目； ②子項(xiàng)目之間無(wú)次序要求，即兩個(gè)子項(xiàng)目可以同時(shí)進(jìn)行，互不影響。 ?如果從頂點(diǎn) Vi到 Vj之間存在有向 邊 Vi， Vj,則表示 活動(dòng)之間的優(yōu)先關(guān)系 。這種前趨后繼關(guān)系有傳遞性。 圖 有向環(huán)路 ③ ① ② 拓?fù)渑判? ?所謂“拓?fù)渑判颉本褪菍?AOV網(wǎng)絡(luò)中的各個(gè)頂點(diǎn) (各個(gè)活動(dòng) )排列成一個(gè)線性有序序列，使得所有要求的前趨、后繼關(guān)系都能得到滿足。 如果進(jìn)行到某一步，無(wú)法找到無(wú)前趨的頂點(diǎn)，則說(shuō)明此 AOV網(wǎng)絡(luò)中存在有向回路。 ?例如圖 示。每次選入度為零的頂點(diǎn)時(shí)，只要取棧頂頂點(diǎn)即可。 1 2 4 3 5 2 1 3 0 3 Top ?用鄰接表存儲(chǔ) AOV網(wǎng)絡(luò)，實(shí)現(xiàn)拓?fù)渑判虻牟襟E可描述如下： ? 1。 拓?fù)渑判蛩惴? void topsort(adjlist adj, int n) /*adj為鄰接表 */ { int num,i,j,top。 /*num指示輸出頂點(diǎn)個(gè)數(shù) */ for(i=1。 } } 拓?fù)渑判蛩惴ɡm(xù) while(top0) { i=top。 /*輸出頂點(diǎn) Vi并計(jì)數(shù) */ num++。 top=j。 ? AOE網(wǎng)絡(luò)是一個(gè)帶權(quán)的有向無(wú)環(huán)路圖，其中，每個(gè)頂點(diǎn)代表一個(gè) 事件 (Event)，事件說(shuō)明某些活動(dòng)或某一項(xiàng)活動(dòng)的完成，即階段性的結(jié)果。 約定 : e(i): 活動(dòng) ai的 最早開(kāi)始時(shí)間 如 e(9)=7 e(7)=7 L(i): 活動(dòng) ai的 最遲開(kāi)始時(shí)間 , 即在不影響整個(gè) 工程進(jìn)度的情況下 , 活動(dòng) ai最遲必須開(kāi)始 的時(shí)間 . 如 L(9)=10 L(7)=7 顯然 , L(i) e(i) 是活動(dòng) ai的時(shí)間余量 (余地 ), 若 L(i) e(i)=0, 活動(dòng) ai一定是關(guān)鍵活動(dòng) . ?為了求出關(guān)鍵活動(dòng) , 就要求出活動(dòng)的 最早開(kāi)始時(shí)間 e(i)和 最遲開(kāi)始時(shí)間 L(i), 為了求出活動(dòng)的最早時(shí)間和最遲時(shí)間 , 首先要求出事件的 最早發(fā)生時(shí)間 和 最遲發(fā)生時(shí)間 . Ve(i): 事件 vi 的 最早 發(fā)生時(shí)間 VL(i): 事件 vi 的 最遲 發(fā)生時(shí)間 1. e(i)=ve(j) l(i)=vl(k)dur(j,k) 2. 從 ve(1)=0開(kāi)始，向后遞退推 Ve(j)=max{ve(i)+dur(i,j)} ai j k j i1 i2 im . …… vl(n)=ve(n) 起，向前遞推 Vl(i)=min{vl(j)dur(i,j)} i j1 j2 jm …… 求關(guān)鍵路徑算法 1. 輸入 e條有向邊 j, k，建立 AOE網(wǎng)絡(luò)的存儲(chǔ)結(jié)構(gòu) (可用鄰接表等 ). 2. 從源點(diǎn)出發(fā) v1出發(fā)，令 ve(1) =0，按拓?fù)渑判虻男蛄星蟪銎溆喔鼽c(diǎn)的 最早發(fā)生時(shí)間 ve(i)(用公式 2)。 圖 一個(gè)有向圖的鄰接表 5 3 4 5 ∧ 2 4 ∧ 2 4 ∧ ∧ ∧ 1 4 3 2 例 ?解：根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn) v1出發(fā)所得到的頂點(diǎn)序列是： v1， v3， v4， v5， v2 根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn) v1出發(fā)所得到的頂點(diǎn)序列是： v1， v3， v2， v4， v5 例 ?有 n個(gè)頂點(diǎn)的無(wú)向圖或有向圖采用鄰接矩陣和鄰接表表示，請(qǐng)回答下列問(wèn)題 : ? (1) 如何計(jì)算圖中有多少條邊？ ? (2) 如何判斷任意兩個(gè)頂點(diǎn) i和 j是否有邊相連？ ? (3) 如何計(jì)算任意一個(gè)頂點(diǎn)的度是多少？ 例 ?解： (1) 對(duì)于無(wú)向圖鄰接矩陣中 “ 1”的個(gè)數(shù)除 2為圖的邊數(shù) 。 ? (2) 對(duì)于無(wú)向圖 ， 在鄰接矩陣中第 i行第 j列元素為 “ 1”， 或者第 j行第 i列元素為 “ 1”， 則頂點(diǎn) i與 j有邊相連 。 ? (3)對(duì)于無(wú)向圖鄰接矩陣中第 i行的元素之和為i頂點(diǎn)的度 ， 鄰接表中的第 i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)為 i頂點(diǎn)的度 。 圖 一個(gè)無(wú)向圖 G ⑤ ④ ① ② ③ 4. 假設(shè)圖的頂點(diǎn)是 A、 B…… 請(qǐng)根據(jù)下面的鄰接矩陣畫出相應(yīng)的無(wú)向圖或有向圖。 ⑥ ⑤ ④ ① ② ③ ?二、算法設(shè)計(jì)題 1. 如圖 G，試給出其對(duì)應(yīng)的鄰接表，并寫出深度優(yōu)先算法。 圖 一個(gè)無(wú)向圖 G ⑦ ⑥ ⑤ ② ③ ④ ⑧ ① ⑨ 5. 已知一個(gè)有 n個(gè)頂點(diǎn)的有向圖的鄰接表，設(shè)計(jì)算法分別實(shí)現(xiàn) 1) 求出圖中每個(gè)頂點(diǎn)的出度。 返回 。 3) 求出圖中出度最大的一個(gè)頂點(diǎn)，輸出其頂點(diǎn)序號(hào)。 3. 編寫一個(gè)函數(shù)通過(guò)與用戶交互建立一個(gè)有向圖的鄰接表。 0 ⑥ ⑤ ④ ① ② ③ ⑦ ⑧ ⑨ 圖 一個(gè)帶權(quán)連通圖 G 6. 應(yīng)用 prim算法求圖 最小生成樹(shù)。在鄰接表中，第 i個(gè)單鏈表的結(jié)點(diǎn)數(shù)就是 i頂點(diǎn)的出度，整個(gè)鄰接表中具有的結(jié)點(diǎn)為 i的結(jié)點(diǎn)數(shù)就是 i頂點(diǎn)的入度。 對(duì)于有向圖，在鄰接矩陣中第 i行第 j列元素為“ 1”，則有一條從 i到 j的邊。 對(duì)于有向圖鄰接矩陣中 “ 1”的個(gè)數(shù)為圖的邊數(shù) 。 若某條邊 ai 滿足 e[i]=L[i], 則 ai為關(guān)鍵活動(dòng)。 ?權(quán)值表示 活動(dòng)持續(xù)的時(shí)間 。 /*找下一個(gè)后繼結(jié)點(diǎn) */ } } if(numn) printf(“網(wǎng)絡(luò)中有環(huán)路 ! ”\n)。 adj[j]data。 /*在鏈表中刪除入度為 0的頂點(diǎn) ， 頂點(diǎn)序號(hào)為 i*/ q=adj[i]link。i++)/*建立入度為 0頂點(diǎn)的堆棧 */ { if(adj[i]data==0) { adj[i]data=top。 top=0。在棧不空時(shí)： ①退棧并輸出棧頂元素 i； ②在鄰接表的第 i個(gè)單鏈表中，查找頂點(diǎn) i的所有直接后繼 k，并將頂點(diǎn) k的入度減 1。用該數(shù)據(jù)域存放下一個(gè)入度為零的頂點(diǎn)標(biāo)號(hào)，將堆棧中的各個(gè)單元鏈接起來(lái)，再設(shè)置一個(gè)棧頂指針 top即可。 ?刪去一個(gè)頂點(diǎn)時(shí)，所有它的直接后繼頂點(diǎn)入度均減 1，表示相應(yīng)的有向邊也被刪除掉。 ?規(guī)定將每個(gè)結(jié)點(diǎn)的 Data域改為 int型，并將每個(gè)鏈表的表頭結(jié)點(diǎn)構(gòu)成一個(gè)順序表，各表頭結(jié)點(diǎn)的 Data域存放相應(yīng)頂點(diǎn)的入度值。 ?通過(guò)拓?fù)渑判蜻€可以判斷出此 AOV網(wǎng)絡(luò)是否包含有有向環(huán)路，若有向圖 G所有頂點(diǎn)都在拓?fù)渑判蛐蛄兄?，則 AOV網(wǎng)絡(luò)必定不包含有有向環(huán)路。例如在圖， V2是 V3的前趨頂點(diǎn)，V1是 V2的前趨頂點(diǎn)， V3又是 V1的前趨頂點(diǎn)，環(huán)路表示頂點(diǎn)之間的先后關(guān)系進(jìn)入了死循環(huán)。 ?例如圖 互之間的關(guān)系，它對(duì)應(yīng)的 AOV網(wǎng)絡(luò)如圖 所示。 ?學(xué)校里某個(gè)專業(yè)的課程學(xué)習(xí)，有些課程是基礎(chǔ)課，它們可以獨(dú)立于其它課程，即無(wú)前導(dǎo)課程；有些課程必須在一些課程學(xué)完后才能開(kāi)始學(xué)。 Path[i]=path [j] +[i]。 in。(dist[i]wm) { j=i。 /*wm: 臨時(shí)變量 for( i=0。 /*