【正文】 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓撲序列： C1C2C3C4C5C7C9C10C11C6C12C8 或 ： C9C10C11C6C1C12C4C2C3C5C7C8 一個 AOV網(wǎng)的拓撲序列不是唯一的 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 一、關(guān)鍵路徑 設(shè)一個工程有 11項活動， 9個事件 事件 V1—— 表示整個工程開始 事件 V9—— 表示整個工程結(jié)束 問題：（ 1）完成整項工程至少需要多少時間？ （ 2）哪些活動是影響工程進度的關(guān)鍵？ 9 8 7 6 4 5 3 2 1 a6=2 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering AOE網(wǎng) (Activity On Edge)—— 也叫邊表示活動的網(wǎng)。 TD ga[M]。 //存放頂點信息 struct node *firstarc。 //鏈域，指示下一條邊或弧 }JD。 無向圖中頂點 Vi的度 TD(Vi)是鄰接矩陣 A中第 i行元素之和 有向圖中， 頂點 Vi的出度是 A中第 i行元素之和 頂點 Vi的入度是 A中第 i列元素之和 網(wǎng)絡(luò)的鄰接矩陣可定義為： ????? ????，其它0E ( G )v,v或)v,(v若,],[ jijiijjiA ? 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering ??????????????????0618360240120228400530750? ? ? ? ? ? ? ? ? ? 例 1 4 5 2 3 7 5 3 1 8 6 4 2 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 3 鄰接表 實現(xiàn)：為圖中每個頂點建立一個單鏈表，第 i個單鏈表中的結(jié)點表示依附于頂點 Vi的邊（有向圖中指以 Vi為尾的?。? typedef struct node { int adjvex。 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 華北電力大學 電子與通信工程系 軟件技術(shù)基礎(chǔ) Fundamentals of Computer Software Technique 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 第六章 圖 圖的定義和術(shù)語 圖的存儲結(jié)構(gòu) 圖的遍歷 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 圖的定義和術(shù)語 1. 圖 (Graph)—— 圖 G是由兩個集合 V(G)和 E(G)組成的 ,記為 G=(V,E) 其中： V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)? 2. 有向圖 —— 有向圖 G是由兩個集合 V(G)和 E(G)組成的 其中： V(G)是頂點的非空有限集 E(G)是有向邊（也稱?。┑挠邢藜?，弧是頂點的有序?qū)?，記?v,w， v,w是頂點， v為弧尾， w為弧頭 3. 無向圖 —— 無向圖 G是由兩個集合 V(G)和 E(G)組成的 其中： V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)?，記為?v,w） 或（ w,v)， 并且（ v,w)=(w,v) 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 例 2 4 5 1 3 6 G1 圖 G1中： V(G1)={1,2,3,4,5,6} E(G1)={1,2, 2,1, 2,3, 2,4, 3,5, 5,6, 6,3} 例 1 5 7 3 2 4 G2 6 圖 G2中： V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)} 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 1. 權(quán) —— 與圖的邊或弧相關(guān)的數(shù) 2. 網(wǎng) —— 帶權(quán)的圖 3. 子圖 —— 如果圖 G(V,E)和圖 G‘(V’,E‘),滿足： V’?V 。 E’?E 則稱 G‘為 G的子圖 4. 頂點的度 無向圖中，頂點的度為與每個頂點相連的邊數(shù) 有向圖中，頂點的度分成入度與出度 入度：以該頂點為頭的弧的數(shù)目 出度：以該頂點為尾的弧的數(shù)目 5. 路徑 —— 路徑是頂點的序列V={Vi0,Vi1,…… Vin}， 滿足 (Vij1,Vij)?E 或 Vij1,Vij?E,(1j?n) 軟 件 技 術(shù) 基 礎(chǔ)