【導(dǎo)讀】無(wú)向邊的集合，則稱該圖為無(wú)向圖。完全圖中共有n(n-1)/2條。數(shù)值，這個(gè)數(shù)值叫做該邊的權(quán)。E，則稱G’是G的子。例如圖G1的一些子圖。該頂點(diǎn)的度，記作TD。頂點(diǎn)的度等于其入度和出度之和。,Vm到達(dá)，Vq，則稱頂點(diǎn)序列。,Vm,Vq)為從Vp到Vq的路徑。個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則稱為回路。如果圖中任意一對(duì)頂點(diǎn)都是連。通的，則稱此圖是連通圖。間都有路徑，則稱這兩個(gè)頂點(diǎn)是強(qiáng)連通的。強(qiáng)連通子圖叫做強(qiáng)連通分量。生成樹(shù)：有n個(gè)頂點(diǎn)，n-1條邊的樹(shù)，且。鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。點(diǎn)的相鄰關(guān)系即它們之間有邊相連。若圖有n個(gè)結(jié)點(diǎn)數(shù)，鄰接矩陣是一個(gè)階方陣。儲(chǔ)其上三角陣元素即可.鄰接表是圖的一種鏈接存儲(chǔ)結(jié)構(gòu)。示以該頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)。鄰接表表示是不唯一的。

　　

【正文】 *adj為鄰接表 */ { int num,i,j,top。 struct vexnode *q。 top=0。 num=0。 /*num指示輸出頂點(diǎn)個(gè)數(shù) */ for(i=1。i=n。i++)/*建立入度為 0頂點(diǎn)的堆棧 */ { if(adj[i]data==0) { adj[i]data=top。 top=i。 } } 拓?fù)渑判蛩惴ɡm(xù) while(top0) { i=top。 top=adj[i]data。 /*在鏈表中刪除入度為 0的頂點(diǎn) ， 頂點(diǎn)序號(hào)為 i*/ q=adj[i]link。 printf(“%d”,i)。 /*輸出頂點(diǎn) Vi并計(jì)數(shù) */ num++。 while(q!=NULL) { j=qadjvex。 adj[j]data。 /*將后繼結(jié)點(diǎn) j的入度減 1*/ 拓?fù)渑判蛩惴ɡm(xù) if(adj[j]data==0) { adj[j]data=top。 top=j。 } q=pnext。 /*找下一個(gè)后繼結(jié)點(diǎn) */ } } if(numn) printf(“網(wǎng)絡(luò)中有環(huán)路 ! ”\n)。 /*因輸出的頂點(diǎn)數(shù)小于 n*/ } 返回 關(guān)鍵路徑 ?關(guān)鍵路徑法是采用邊表示 活動(dòng) (Activity On Edge)的網(wǎng)絡(luò)，簡(jiǎn)稱為 AOE網(wǎng)絡(luò)。 ? AOE網(wǎng)絡(luò)是一個(gè)帶權(quán)的有向無(wú)環(huán)路圖，其中，每個(gè)頂點(diǎn)代表一個(gè) 事件 (Event)，事件說(shuō)明某些活動(dòng)或某一項(xiàng)活動(dòng)的完成，即階段性的結(jié)果。 ?離開(kāi)某頂點(diǎn)的各條邊所代表的活動(dòng)，只有在該頂點(diǎn)對(duì)應(yīng)的事件出現(xiàn)后才能開(kāi)始。 ?權(quán)值表示 活動(dòng)持續(xù)的時(shí)間 。 圖 一個(gè) AOE網(wǎng)絡(luò) a1=6 ② ⑤ ① ③ ④ ⑥ ⑧ ⑨ ⑦ a2=4 a4=1 a3=5 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 源點(diǎn) 匯點(diǎn) 要研究的問(wèn)題： 1. 完成整個(gè)工程至少需要多少時(shí)間？ 2. 哪些活動(dòng)影響工程進(jìn)度？ 關(guān)鍵路徑 在 AOV網(wǎng)絡(luò)中 , 有些活動(dòng)是可以平行進(jìn)行的 , 所以完成工程的最短時(shí)間是從開(kāi)始點(diǎn)到終點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度 . 長(zhǎng)度最長(zhǎng)的路徑稱為 關(guān)鍵路徑 . 在關(guān)鍵路徑上的活動(dòng)叫 關(guān)鍵活動(dòng) . 分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的效率，縮短整個(gè)工期。 約定 : 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)。 (若拓?fù)渑判蛐蛄兄械捻旤c(diǎn)個(gè)數(shù)小于網(wǎng)絡(luò) 中的頂點(diǎn)數(shù)，則說(shuō)明網(wǎng)絡(luò)中存在環(huán)路，算 法中止執(zhí)行 .) 3. 從匯點(diǎn) Vn出發(fā)，令 VL[n]=Ve[n]，按逆拓?fù)渑判虻男蛄星笃溆喔鼽c(diǎn)的 最遲發(fā)生時(shí)間 VL(i). ( 用公式 3) 4. 根據(jù)各點(diǎn)的 ve和 VL值 , 求出每條邊 ai的最早開(kāi)始時(shí)間 e(i)和最遲開(kāi)始時(shí)間 L(i) (用公式 1)。 若某條邊 ai 滿足 e[i]=L[i], 則 ai為關(guān)鍵活動(dòng)。 例 ?已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖，分別給出從頂點(diǎn) v1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷所得到的頂點(diǎn)序列。 圖 一個(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ù) 。 鄰接表中的各單鏈表中的結(jié)點(diǎn)數(shù)除 2為圖的邊數(shù) 。 對(duì)于有向圖鄰接矩陣中 “ 1”的個(gè)數(shù)為圖的邊數(shù) 。 鄰接表中的各單鏈表中的結(jié)點(diǎn)數(shù)為圖的邊數(shù) 。 ? (2) 對(duì)于無(wú)向圖 ， 在鄰接矩陣中第 i行第 j列元素為 “ 1”， 或者第 j行第 i列元素為 “ 1”， 則頂點(diǎn) i與 j有邊相連 。 在鄰接表中的第 i個(gè)單鏈表中有結(jié)點(diǎn)為 j， 或者第 j個(gè)單鏈表中有結(jié)點(diǎn)為 i， 則頂點(diǎn) i與 j有邊相連 。 對(duì)于有向圖，在鄰接矩陣中第 i行第 j列元素為“ 1”，則有一條從 i到 j的邊。在鄰接表中的第 i個(gè)單鏈表中有結(jié)點(diǎn)為 j，則有一條從 i到 j的邊。 ? (3)對(duì)于無(wú)向圖鄰接矩陣中第 i行的元素之和為i頂點(diǎn)的度 ， 鄰接表中的第 i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)為 i頂點(diǎn)的度 。 對(duì)于有向圖鄰接矩陣中第 i行元素之和為 i頂點(diǎn)的入度，第 j列元素之和為 j頂點(diǎn)的出度。在鄰接表中，第 i個(gè)單鏈表的結(jié)點(diǎn)數(shù)就是 i頂點(diǎn)的出度，整個(gè)鄰接表中具有的結(jié)點(diǎn)為 i的結(jié)點(diǎn)數(shù)就是 i頂點(diǎn)的入度。 返回 小 結(jié) ?圖 ?圖的存儲(chǔ)結(jié)構(gòu) 鄰接矩陣 鄰接表 ?圖的遍歷 深度優(yōu)先搜索 廣度優(yōu)先搜索 ?圖的應(yīng)用 最小生成樹(shù) 最短路徑問(wèn)題 利用 AOV網(wǎng)絡(luò)研究拓?fù)渑判騿?wèn)題 利用 AOE網(wǎng)絡(luò)研究關(guān)鍵路徑的方法 返回 習(xí)題與練習(xí) ?一、基本知識(shí)題 1. 圖的邏輯結(jié)構(gòu)特點(diǎn)是什么？什么是無(wú)向圖和有向圖？什么是子圖？什么是網(wǎng)絡(luò)？ 2. 什么是頂點(diǎn)的度？什么是路徑？什么是連通圖和非連通圖？什么是非連通圖的連通分量？ 3. 給出圖 G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。 圖 一個(gè)無(wú)向圖 G ⑤ ④ ① ② ③ 4. 假設(shè)圖的頂點(diǎn)是 A、 B…… 請(qǐng)根據(jù)下面的鄰接矩陣畫(huà)出相應(yīng)的無(wú)向圖或有向圖。 ????????????0111101111011110????????????????0101000001100010100000110(a) (b) 圖 一個(gè)無(wú)向圖 G 5. 分別給出圖 G圖的深度優(yōu)先搜索和廣度優(yōu)先搜索得到的頂點(diǎn)訪問(wèn)序列。 0 ⑥ ⑤ ④ ① ② ③ ⑦ ⑧ ⑨ 圖 一個(gè)帶權(quán)連通圖 G 6. 應(yīng)用 prim算法求圖 最小生成樹(shù)。 1 ⑤ ④ ① ② ③ 1 2 2 2 3 5 3 圖 一個(gè)有向圖 G 7. 寫(xiě)出圖 。 ⑥ ⑤ ④ ① ② ③ ?二、算法設(shè)計(jì)題 1. 如圖 G，試給出其對(duì)應(yīng)的鄰接表，并寫(xiě)出深度優(yōu)先算法。 2. 如圖 G，試給出其對(duì)應(yīng)的鄰接矩陣，并寫(xiě)出廣度優(yōu)先算法。 3. 編寫(xiě)一個(gè)函數(shù)通過(guò)與用戶交互建立一個(gè)有向圖的鄰接表。 4. 編寫(xiě)一個(gè)無(wú)向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。 圖 一個(gè)無(wú)向圖 G ⑦ ⑥ ⑤ ② ③ ④ ⑧ ① ⑨ 5. 已知一個(gè)有 n個(gè)頂點(diǎn)的有向圖的鄰接表，設(shè)計(jì)算法分別實(shí)現(xiàn) 1) 求出圖中每個(gè)頂點(diǎn)的出度。 2) 求出圖中每個(gè)頂點(diǎn)的入度。 3) 求出圖中出度最大的一個(gè)頂點(diǎn)，輸出其頂點(diǎn)序號(hào)。 4) 計(jì)算圖中出度為 0的頂點(diǎn)個(gè)數(shù)。 返回