《數(shù)據(jù)結(jié)構(gòu)與算法》課件chap07

1、第七章 圖本章介紹另一種非線性數(shù)據(jù)結(jié)構(gòu) 圖 圖：是一種多對多的結(jié)構(gòu)關(guān)系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼； 第七章 圖 7.1 圖的概念 7.2 圖的存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 生成樹 7.7 最短路徑 7.6 拓撲排序?qū)W習要點 1熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解實際問題的求解效率與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系； 2熟練掌握圖的兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法。在學習中應(yīng)注意圖的遍歷算法與樹的遍歷算法之間的類似和差異。樹的先根遍歷是一種深度優(yōu)先搜索策略，樹的層次遍歷是一種廣度優(yōu)先搜索策略; 3理解課件中討論的各種圖的算法；第七 章 圖 7.1 圖

2、的概念 一 圖的概念 二 圖的應(yīng)用 三 圖的基本操作 四 圖的基本術(shù)語7.1 圖的基本概念一 圖的概念 圖的定義 圖G由兩個集合構(gòu)成，記作G= 其中V是頂點的非空有限集合，E是邊的有限集合，其中邊是頂點的無序?qū)蛴行驅(qū)?。G1=V1=v0 ,v1,v2,v3,v4 E1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)G1圖示無序?qū)?vi,vj)：用連接頂點vi、vj的線段表示，稱為無向邊；例 V0 V4 V3 V1 V2G2 圖示有序?qū)?：用以為vi起點、以vj為終點的有向線段表示，稱為有向邊或?。粺o向圖：在圖G中，若所有邊是無向邊，則稱G為無向

3、圖；有向圖：在圖G中，若所有邊是有向邊，則稱G為有向圖；混和圖：在圖G中，即有無向邊也有有向邊，則稱G為混合圖；7.1 圖的基本概念 V0 V1 V2 V3G2=V2=v0 v1,v2,v3E2= , , ,圖的應(yīng)用舉例例1 交通圖（公路、鐵路） 頂點：地點 邊：連接地點的公路 交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例2 電路圖 頂點：元件 邊：連接元件之間的線路例3 通訊線路圖 頂點：地點 邊：地點間的連線例4 各種流程圖 如產(chǎn)品的生產(chǎn)流程圖 頂點：工序 邊：各道工序之間的順序關(guān)系7.1 圖的基本概念 V0 V4 V3 V1 V2 V0 V1 V2 V31 鄰接點及關(guān)聯(lián)邊 鄰接

4、點：邊的兩個頂點 關(guān)聯(lián)邊：若邊e= (v, u), 則稱頂點v、u 關(guān)連邊e2 頂點的度、入度、出度 頂點V的度 = 與V相關(guān)聯(lián)的邊的數(shù)目 在有向圖中： 頂點V的出度=以V為起點有向邊數(shù) 頂點V的入度=以V為終點有向邊數(shù) 頂點V的度= V的出度+V的入度 設(shè)圖G的頂點數(shù)為n，邊數(shù)為e 圖的所有頂點的度數(shù)和 = 2*e （每條邊對圖的所有頂點的度數(shù)和“貢獻”2度） e圖的基本術(shù)語7.1 圖的基本概念 V0 V4 V3 V1 V2 V0 V1 V2 V3 路徑、回路 無向圖G=（V，E）中的頂點序列v1,v2, ,vk,若(vi,vi+1)E( i=1,2,k-1), v =v1, u =vk,

5、則稱該序列是從頂點v到頂點u的路徑；若v=u，則稱該序列為回路； 有向圖D=（V，E）中的頂點序列v1,v2, ,vk, 若E (i=1,2,k-1), v =v1, u =vk, 則稱該序列是從頂點v到頂點u的路徑；若v=u，則稱該序列為回路； 7.1 圖的基本概念 在圖1中，V0,V1,V2,V3 是V0到V3的路徑； V0,V1,V2,V3,V0是回路；在圖2中，V0,V2,V3 是V0到V3的路徑； V0,V2,V3,V0是回路；例 V0 V4 V3 V1 V2無向圖G1 V0 V1 V2 V3有向圖G2 簡單路徑和簡單回路 在一條路徑中,若除起點和終點外,所有頂點各不相同,則稱該路徑

6、為簡單路徑； 由簡單路徑組成的回路稱為簡單回路； 在圖1中，V0,V1,V2,V3 是簡單路徑； V0,V1,V2,V4,V1不是簡單路徑；在圖2中， V0,V2,V3,V0是簡單回路；無向圖G1有向圖G2例 V0 V4 V3 V1 V2 V0 V1 V2 V3連通圖（強連通圖） 在無（有）向圖G=中，若對任何兩個頂點 v、u 都存在從v 到 u 的路徑，則稱G是連通圖（強連通圖） 非連通圖 連通圖 強連通圖 非強連通圖 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V7 V4子圖 設(shè)有兩個圖G=（V，E）、G1=（V1，E1），若V1

7、V，E1 E，E1關(guān)聯(lián)的頂點都在V1中，則稱 G1是G的子圖；例 (b)、(c) 是 (a) 的子圖(a)(b)(c) V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2連通分圖（強連通分量） 無向圖G 的極大連通子圖稱為G的連通分量 極大連通子圖意思是：該子圖是 G 連通子圖，將G 的任何不在該子圖中的頂點加入，子圖不再連通； 連通分圖非連通圖7.1 圖的基本概念 V0 V2 V3 V1 V5 V4 V0 V2 V1非連通分圖有向圖D 的極大強連通子圖稱為D 的強連通分量 極大強連通子圖意思是：該子圖是D強連通子圖，將D的任何不在該子圖中的頂點加入，子圖

8、不再是強連通的；強連通分量 V0 V1 V2 V3 V0 V2 V3 V17 生成樹 包含無向圖G 所有頂點的的極小連通子圖稱為G 的生成樹 極小連通子圖意思是：該子圖是G 的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通， 若T是G 的生成樹當且僅當T 滿足如下條件 T是G 的連通子圖 T包含G 的所有頂點 T中無回路連通圖 G1G1的生成樹7.1 圖的基本概念 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2第七 章 圖 7.2 圖的存儲結(jié)構(gòu) 一 數(shù)組表示法 二 鄰接表 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 至少要保存兩類信息： 1)頂點的數(shù)據(jù) 2)頂

9、點間的關(guān)系約定: G=是圖, V=v0,v1,v2, vn-1 ,設(shè)頂點的 角標為它的編號 如何表示頂點間的關(guān)系？頂點的編號 ？ V0 V4 V3 V1 V2 V0 V1 V2 V3鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣： Aij=1 若(vi,vi+1)E 或 E0 否則0 1 0 1 00 1 0 10 1 0 1 10 1 0 00 1 1 0 00 1 1 00 0 0 00 0 0 10 0 0一 數(shù)組表示法(鄰接矩陣表示)在數(shù)組表示法中，用鄰接矩陣表示頂點間的關(guān)系 7.2 圖的存儲結(jié)構(gòu) V0 V4 V3 V1 V2 V0 V1 V2 V3無向圖數(shù)組表示法特點：1）無向圖鄰接

10、矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點v的度：等于二維數(shù)組對應(yīng)行（或列）中1的個數(shù)；3）判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應(yīng)分量是否為1；4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值1或清0；5）設(shè)圖的頂點數(shù)為 n ,存儲圖用一維數(shù)組, 數(shù)組元素有 m 個 （m=n),則 G占用存儲空間：m+n2；G占用存儲空間只與它的頂點數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖；對有向圖的數(shù)組表示法可做類似的討論0 1 0 1 00 1 0 10 1 0 1 10 1 0 00 1 1 0 0數(shù)組表示法的空間代價只與圖的頂點數(shù)有關(guān) 7.2 圖的存儲結(jié)構(gòu) V0 V4 V3 V1

11、V2圖的基本操作：1）求無向圖某頂點vi的度(或有向圖中vi的出度)。Ai0到Ain-1中的非0個數(shù)，即數(shù)組A中第i 行的非0 元素的個數(shù)；2）求有向圖某頂點vi 的 入度。： A0i到A n-1i 中的非0個數(shù)，即數(shù)組A中第i 列的非0 元素的個數(shù)；3）檢測圖中的總邊數(shù)。掃描整個數(shù)組A，統(tǒng)計出數(shù)組中非0元素的個數(shù)。無向圖的總邊數(shù)為非0元素個數(shù)的一半，而有向圖的總弧數(shù)為非0元素個數(shù)；0 1 0 1 00 1 0 10 1 0 1 10 1 0 00 1 1 0 0 7.2 圖的存儲結(jié)構(gòu) V0 V4 V3 V1 V2 V0 V1 V2 V30 1 1 00 0 0 00 0 0 10 0 0鄰接

12、表 鄰接表是圖的鏈式存儲結(jié)構(gòu)1 無向圖的鄰接表頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中；關(guān)聯(lián)同一頂點的邊：用線性鏈表存儲該結(jié)點表示邊（Vi Vj）,其中的1是Vj在一維數(shù)組中的位置例 7.2 圖的存儲結(jié)構(gòu) V0 V4 V3 V1 V22 0 1 2 3 4m-1V0V1V2V3V413422110034下標 編號 link圖的鄰接表類型定義struct node /邊（?。┙Y(jié)點的類型定義 int vertex; /邊（弧）的另一頂點在數(shù)組中的位置 struct node *link; /指向下一條邊（?。┙Y(jié)點的指針; typedef struct NODE；Typedef struct

13、vnode vertextype data: /頂點的數(shù)據(jù)類型 NODE *firstarc; /指向第一條依附該頂點的弧的指針VNODE;VNODE adjlistMAX; / 鄰接點鏈表的頭指針所對應(yīng)的數(shù)組 7.2 圖的存儲結(jié)構(gòu)無向圖的鄰接表的特點 1）在G鄰接表中，同一條邊對應(yīng)兩個結(jié)點； 2）頂點v的度：等于v對應(yīng)線性鏈表的長度； 3）判定兩頂點v ，u是否鄰接：要看v對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點 4）在G中增減邊：要在兩個單鏈表插入、刪除結(jié)點； 5）設(shè)存儲頂點的一維數(shù)組大小為m(m圖的頂點數(shù)n), 圖的邊數(shù)為e，G占用存儲空間為：m+2*e。G占用存儲空間與 G 的頂點數(shù)、邊數(shù)均有關(guān)；

14、適用于邊稀疏的圖 0 1 2 3 4m-1V0V1V2V3V413422110043鄰接表的空間代價與圖的邊及頂點數(shù)均有關(guān) 7.2 圖的存儲結(jié)構(gòu) V0 V4 V3 V1 V222 有向圖的鄰接表和逆鄰接表1）有向圖的鄰接表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為起點的弧：用線性鏈表存儲類似于無向圖的鄰接表，所不同的是：以同一頂點為起點的弧：用線性鏈表存儲下標 編號 link V0V1V2V31230 0 1 2 3m-1例 7.2 圖的存儲結(jié)構(gòu) V0 V1 V2 V32）有向圖的逆鄰接表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為終點的弧：用線性鏈表存儲V0V1V2V3 0 1 2 3

15、m-10023類似于有向圖的鄰接表，所不同的是：以同一頂點為終點弧：用線性鏈表存儲例 7.2 圖的存儲結(jié)構(gòu) V0 V1 V2 V3 建立鄰接表的算法建立無向鄰接表 int create(VNODE *adjlist ) NODE *p; int num, i, v1, v2; scanf(“%dn”, &num); /讀入結(jié)點數(shù) for(i=0; inum; i+) /初始化空關(guān)系圖 adjlisti.firstarc=NULL; adjlisti.data=i; 7.2 圖的存儲結(jié)構(gòu) for(; ;) scanf(“%d to %dn”, &v1, &v2); /讀入一條邊 if (v10

16、| v2vertex=v2; p-link=adjlistv1.firstarc; adjlistv1.firstarc=p; /插入在鏈表首部 p=(NODE *)malloc(sizeof(NODE); p-vertex=v1; p-link=adjlistv2.firstarc; adjlistv2.firstarc=p; return(num); / 返回圖的結(jié)點數(shù) 7.2 圖的存儲結(jié)構(gòu) 在不同的存儲結(jié)構(gòu)下，實現(xiàn)各種操作的效率可能是不同的。所以在求解實際問題時，要根據(jù)求解問題所需操作，選擇合適的存儲結(jié)構(gòu)。 7.2 圖的存儲結(jié)構(gòu)第七 章 圖 7.3 圖的遍歷 一 深度優(yōu)先遍歷 二 廣度優(yōu)

17、先遍歷7.3 圖的遍歷 圖的遍歷：從圖的某頂點出發(fā)，訪問圖中所有頂點，并且每個頂點僅訪問一次。在圖中，訪問部分頂點后，可能又沿著其他邊回到已被訪問過的頂點。為保證每一個頂點只被訪問一次，必須對頂點進行標記，一般用一個輔助數(shù)組 visitMAX作為對頂點的標記，當頂點vi未被訪問，visiti值為0；當vi已被訪問，則visiti值為1。 圖的遍歷與樹的遍歷有什么不同？ 有兩種遍歷方法（它們對無向圖，有向圖都適用） 深度優(yōu)先遍歷 廣度優(yōu)先遍歷 V0 V7 V6 V7 V4 V3 V2 V1從圖中某頂點v出發(fā)： 1）訪問頂點v；2）依次從v的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷； V0,

18、V1,V3,V7,V4,V2,V5,V6, 由于沒有規(guī)定訪問鄰接點的順序，深度優(yōu)先序列不是唯一的這是序列（1）在遍歷過程中所經(jīng)過的路徑例一 深度優(yōu)先遍歷求圖G以V0起點的的深度優(yōu)先序列： V0 V1 V3 V2 V7 V6 V5 V4 V0,V1,V4,V7,V3,V2,V5,V67.3 圖的遍歷如果將圖頂點的鄰接點看作二叉樹結(jié)點的左、右孩子深度優(yōu)先遍歷與先序遍歷是不是很類似？深度優(yōu)先遍歷從圖中某頂點v出發(fā)： （1）訪問頂點v；（2）依次從v的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷； 先序遍歷（DLR） 若二叉樹非空 （1）訪問根結(jié)點； （2）先序遍歷左子樹； （3）先序遍歷右子樹；7.3

19、 圖的遍歷 V0 V7 V6 V7 V4 V3 V2 V1結(jié)點定義typedef struct node int vertex; / 邊（?。┑牧硪豁旤c在數(shù)組中的位置 struct node *link; / 指向下一條邊（?。┙Y(jié)點的指針; typedef struct NODE；Typedef struct vnode int data; NODE *fistarc;VNODE;VNODE adjlistMAX; / 鄰接點鏈表的頭指針所對應(yīng)的數(shù)組輔助數(shù)組 int visitMAX; /頂點標志數(shù)組,全局變量 NODE *ptrMAX; /頂點鏈表指針數(shù)組visit01234m-100000

20、深度優(yōu)先遍歷算法7.3 圖的遍歷調(diào)用深度優(yōu)先遍歷算法的主函數(shù) main( ) VNODE adjlist MAX; int num; num=create(adjlist ); /* 建立圖G 的鄰接表 */ depthfirst(adjlist, num); /* 調(diào)用對圖G 深度優(yōu)先搜索算法*/ 深度優(yōu)先遍歷算法7.3 圖的遍歷void depthfirst( NODE adjlist, int num) int i; for (i=0; inum;i+) ptri=adjlisti.firstarc; /記住每個頂點鏈表的第一個結(jié)點的地址 visiti=0; /給每個結(jié)點一個未訪問標記

21、for (i=0; ivertex; 取結(jié)點的鄰接頂點w if ( visitw= =0) dfs(w); ptrv=ptrv-link; / 記住頂點v 的鄰接頂點位置， 該鄰接點在w之后 從第v個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖G 。 7.3 圖的遍歷7.3 圖的遍歷 V0 V7 V6 V5 V4 V3 V2 V1 0 1 2 3 4 5 6 7V0V1V2V3V4V5V6V7120115773064265243如果將圖頂點的鄰接點看作二叉樹結(jié)點的左、右孩子深度優(yōu)先遍歷算法與先序遍歷算法的結(jié)構(gòu)是不是很像？深度優(yōu)先遍歷算法void dfs( int v) int w; printf( “%d,

22、 “, v); visitv=1; / 訪問此結(jié)點 while (ptrv！=NULL） w= ptrv-vertex; 取結(jié)點的鄰接頂點w if ( visitw= =0; ) dfs(w); ptrv=ptrv-link; / 記住頂點v 的鄰接點位置， 該鄰接點在w之后 先序遍歷遞歸算法 void prev (NODE *root) if (root!=NULL) printf(“%d,”, root-data)； / 訪問此結(jié)點 prev(root-lch); / 訪問孩子結(jié)點 prev(root-rch); 比較7.3 圖的遍歷 V0 V7 V6 V5 V4 V3 V2 V1圖中某未

23、訪問過的頂點vi出發(fā)：1）訪問頂點vi ；2）訪問 vi 的所有未被訪問的鄰接點w1 ,w2 , wk ；3）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；二 廣度優(yōu)先遍歷（類似于樹的按層遍歷）V0 V1 V3 V2 V7 V6 V5 V4這是序列（1）在遍歷過程中所經(jīng)過的路徑由于沒有規(guī)定訪問鄰接點的順序，廣度優(yōu)先序列不是唯一的例求圖G 的以V0起點的的廣度優(yōu)先序列 V0,V1,V2,V3,V4,V5,V6,V77.3 圖的遍歷從圖中某頂點vi出發(fā)：1）訪問頂點vi ；（容易實現(xiàn)）2）訪問vi 的所有未被訪問的鄰接點w1 ,w2 ,

24、 wk ； （容易實現(xiàn)）3）依次從這些鄰接點（在步驟 2）訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；為實現(xiàn) 3），需要保存在步驟(2）中訪問的頂點，而且訪問這些頂點鄰接點的順序為：先保存的頂點，其鄰接點先被訪問。廣度優(yōu)先遍歷算法在廣度優(yōu)先遍歷算法中，需設(shè)置一隊列Q，保存已訪問的頂點，并控制遍歷頂點的順序。7.3 圖的遍歷 V0 V7 V6 V5 V4 V3 V2 V1Q廣度優(yōu)先遍歷V0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7從圖中某頂點v出發(fā)： 1）訪問頂點v ；2）訪問v的所有未被訪問的鄰接點w1 ,w2 ,

25、wk ；3）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；7.3 圖的遍歷 V0 V7 V6 V5 V4 V3 V2 V1void breadfirst(int num) int; for (i=0;inum;i+) visiti=0;/給所有頂點一個未被訪問標記 for (i=0;ivertex; /遍歷v所指的整個鏈表 if(visitw= =0) /如果w 未被訪問過 printf(“%d,”,w); / 訪問 w visitw=1;enter(w); 訪問后，w 入隊 p=p-link; 7.3 圖的遍歷7.3 圖的遍歷 V

26、0 V2 V3 V1 V5 V4 V0 V2 V3 V1 V5 V4深度優(yōu)先遍歷廣度優(yōu)先遍歷兩種遍歷的比較 7.4 生成樹1 無向圖的生成樹 生成樹是一個連通圖G 的一個極小的連通子圖。包含圖G 的所有頂點，但只有n-1 條邊，并且是連通的。生成樹可由遍歷過程中所經(jīng)過的邊組成。深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。 V0 V7 V6 V5 V4 V3 V2 V1 V3 V0 V7 V6 V5 V4 V2 V1深度優(yōu)先生成樹廣度優(yōu)先生成樹 7.4 生成樹7.4 生成樹 要在 n 個城市間建立交通網(wǎng)，要考慮的問題如何在保證 n 點連通的前題下最節(jié)省

27、經(jīng)費? V2V0V3V5V4 求解: 連通6個城市且代價最小的交通線路? 如何求連通圖的最小生成樹?？7.4.2 最小生成樹（最小支撐樹） 若有一個連通的無向圖 G ，有 n 個頂點，并且它的邊是有權(quán)值的。在 G 上構(gòu)造生成樹 G ,最小生成樹 n-1 條邊的權(quán)值之和最小的 G 。 普魯姆算法基本步驟設(shè)G=（V，E）為一個具有n個頂點的帶權(quán)的連通網(wǎng)絡(luò)，T=（U，TE）為構(gòu)造的生成樹。（1）初始時，U=u0，TE=；（2）在所有uU 、vV-U 的邊（u,v）中選擇一條權(quán)值最小的邊，不妨設(shè)為（u,v)；（3）(u,v) 加入TE，同時將u 加入U；（4）重復(fù)(2)、（3

28、），直到U=V為止；二 普魯姆算法 7.4 最小的生成樹V2V0V3V7V42V0V3V5V42V0V3V5V4V112V2V0V3V5V4V114V2V0V3V5V4V1142V2V0V3V5V4V11452V3V0V3V5V4V11453U= V0 U= V0,V2 U= V0,V2,V5U= V0,V2,V5,V3 U= V0,V2,V5,V3,V1 U= V0,V2,V5,V3,V1,V4 7.4 最小的生成樹有關(guān)數(shù)據(jù)的存儲結(jié)構(gòu) 無向連通網(wǎng)絡(luò): G 為選擇權(quán)值最小的邊: 置一個一維數(shù)組：closest ，對iV-U closesti=

29、 j (jU) (j,i)是一條邊，且是 i 到 U 中各頂點“權(quán)最小邊”Lowcosti：用來保存連接 i 到 U 中各頂點“權(quán)最小邊”的權(quán)。 普魯姆算法涉及的數(shù)據(jù)和操作： 數(shù)據(jù)：無向連通網(wǎng)絡(luò) 操作 : 選擇權(quán)值最小的邊，不妨設(shè)為（u,v) (u,v)加入TE，u加入UUV-Uvi7.4 最小的生成樹V2V0V3V5V4V-UvivjV2V0V3V5V4 0 0 0 0 0 0 0 6 1 5 max max iclosestilowcosti 0 1 2 3 4 5 iclosestilowcosti 0 1 2 3 4 5 0 2 0

30、0 2 2 0 5 0 5 6 4U= v0U= v0,v2V2V0V3V5V4U7.4 最小的生成樹對iV-U closesti= j (jU) (j,i)是一條邊，且是 i 到 U 中各頂點“權(quán)最小邊”Lowcosti：用來保存連接 i 到 U 中各頂點“權(quán)最小邊”的權(quán)。V-U= v1,V2,V3,V4,V5 V-U= v1, V3,V4,V5 0 0 0 0 0 0 0 6 1 5 max max lowcost0 0 2 0 0 2 2 0 5 0 5 6 4 closestlowcost0,2 0 2 0 5 2 2 0 5 0 2 6 0 closestl

31、owcost0,2,5 0 2 0 5 2 2 0 5 0 0 6 0 closestlowcost0,2,5,3 0 2 0 5 1 2 0 0 0 0 3 0closestlowcost0,2,5,3,1 0 2 0 5 1 2 0 0 0 0 0 0 closestlowcost0,2,5,3,1,4iclosest 0 1 2 3 4 5 U7.4 最小的生成樹普里姆算法 圖采用鄰接矩陣表示，鄰接矩陣所對應(yīng)的二維數(shù)組是costMAXMAX, 則 (1) 初始化( U=0),closesti=0;lowcosti=cost0i; lowcost0=0; (i=1,2,3, n-1;) (

32、2) 每次掃描數(shù)組lowcosti，找出值最小且不為0的lowcostk，得到 最小生成樹的一條邊（ closestk,k),將其輸出。（3）令lowcostk=0,將k并入U 中（4）修改數(shù)組closesti和 lowcosti（ lowcosti！=0 及i V-U（5）重復(fù)（2）（3）（4），直到U=V（或循環(huán) n-1 次）結(jié)束 7.4 最小的生成樹用普里姆算法viud PRIM( int costN, int start_v ) int closestN,lowcostN,i,j,k,min; for (i=0; jN; i+) lowcosti=coststart_vi; close

33、sti=start_v; for (i=1; iN; i+) / 循環(huán)n-1次，每次求出最小生成樹的一條邊 min=MAX; for (j=0; jN; j+) if (lowcostj!=0 & lowcostjmin) min= lowcostj;k=j; / 找出值最小的 lowcostk printf(“%d,%d:%dn”,closestk,k, lowcostk); lowcostk=0; / 將 k 并入U 中 for (j=0; jN; j+) / 修改 lowcost 和closest if (costkj!=0 & costkj lowcostj) lowcostj=cos

34、tkj;closestj=k; 7.4 最小的生成樹 基本步驟設(shè)G=（V，E）為一個具有n個頂點的帶權(quán)的連通網(wǎng)絡(luò)，最小生成樹的初始狀態(tài)為有n 個頂點但無邊的非連通圖 T=（V， ）。（1）將E 中的邊按權(quán)值的遞增順序排序，選擇權(quán)值最小的邊，若與相關(guān)的頂點落在T 中不同的連通分量上，則將其加入T 中，否則，將其棄舍。（2）循環(huán)至所有頂點在同一的連通分量上。如何識別一條邊所相關(guān)的頂點是否落在同一個連通分量上？可將一個連通分量的所有頂點看成一個集合，當從E中取出一條邊（ xi, xj ）時，若xi, xj 在同一集合u 中，則將該邊棄舍；否則，則將該邊加入到T 中，并將xj 所在的集合v 并入集合u

35、 中。三 克魯斯卡爾算法 7.4 最小的生成樹V2V0V3V5V4要引入輔助數(shù)組 sets （1）初始化：圖 G 中的n 個頂點，構(gòu)成n 個連通分量，頂點xi 對應(yīng)的連通分量用集合i 表示，所以 sets i =i, 即表示第 i 個頂點在集合 i 中。（2）依次取出E 中的邊（按邊權(quán)值遞增順序），設(shè)取出的邊為（ xi, xj ）。（3）判斷：若sets i = sets j , 則表示xi 和 xj 在同一集合中，返回（2）；否則，轉(zhuǎn)到（4）。（4）將邊 （ xi, xj ）并入T，同時將xj 所在的集合v （與xj 連通的頂點）并入xi 所在的集合 u （與xi

36、連通的頂點），即：由v=setsj和u =setsi ，掃描輔助數(shù)組 sets ，若 setsk=v, 則 令 setsk=u 。返回（2）。（7）重復(fù)（2）、（3）、（4），取出n-1條邊。7.4 最小的生成樹V2V0V3V5V4V136521655460 1 2 3 4 5 0 1 2 3 4 5下標sets。V2V0V3V5V4V136521655460 1 2 3 4 5 0 1 2 3 4 5下標setsV2V0V3V5V4V10 1 2 3 4 5 0 1 2 3 4 5下標sets12345克魯斯卡爾算法中，數(shù)據(jù)結(jié)構(gòu)定義為： struct node int begin, end;

37、 / 邊的相關(guān)頂點編號 int cost; ; /邊的權(quán)值 typedef struct node EDGE; EDGE edgesMAX; /存放邊的數(shù)組 int num; /數(shù)組中實際存放的邊數(shù) int kruskal (EDGE edges ,int num) int setsN,t,i,j,k,u,v; for(i=0; iN; i+) setsi=i; /初始化 k=0;t=0;7.4 最小的生成樹克魯斯卡爾算法： while(tN)&(knum) i=edgesk.begin; j=edgesk.end;k+; /按順序取出一條邊 u=setsi; v=setsj; / xi 在集

38、合 u 中, xj在集合 v 中 if(u!=v) / xi, xj 不在同一集合中 printf(“%d,%d: %dn”,u,v,edgesk.cost); t+; for (i=0; iN; i+) if(setsi= =v)seti=u; / xi在集合的v并入在集合的u中 if (t= =N-1)return(1); else return(0); 7.4 最小的生成樹7.5 最短路徑 交通咨詢系統(tǒng)、通訊網(wǎng)、計算機網(wǎng)絡(luò)常要尋找兩結(jié)點間最短路徑.交通咨詢系統(tǒng)：A 到 B 最短路徑計算機網(wǎng): 發(fā)送Email節(jié)省費用 A到B沿最短路徑傳送路徑長度：路徑上邊數(shù) 路徑上邊的權(quán)值之和最短路徑：兩

39、結(jié)點間權(quán)值之和最小的路徑一 問題的提出7.7 最短路徑例：求V0到V4最短路徑 V0到V4 路徑：V0 V4 47 V0 V1 V4 60 V0 V2 V3 V4 60 V0 V2 V3 V1 V4 554750102010152053035 V1 V4 V0 V2 V3 V5從某源點到其余各點的最短路徑帶權(quán)值的有向圖的單源最短路徑問題如何求從某源點到其余各點的最短路徑？7.7 最短路徑Dijkstra算法的基本思想 按路徑長度遞增順序求最短路徑算法 。與求最小生成樹的普里姆算法類似1 迪杰斯特拉算法（Dijkstra）Dijkstra 算法的基本步驟設(shè)V0是起始源點，U = 已求得最短路徑終

40、點集合。V-U = 未確定最短路徑的頂點的集合 初始時 U =V0 1）長度最短的最短路徑是邊數(shù)為1的長度最小的路徑。 2）下一條長度最短的路徑： Vi V - U ，先求出V0 到Vi 中間只經(jīng) U 中結(jié)點的最短路徑； 上述最短路徑中長度最小者即為下一條長度最短的路徑； 將所求最短路徑的終點加入U 中； 3）重復(fù)2）直到求出所有的最短路徑7.7 最短路徑7.6 最短路徑1006010105305020 V5 V4 V0 V1 V2 V3始點 終點 最短路徑 路徑長度V0 V1 無 V2 （V0，V2） 10 V3 （V0，V4，V3） 50 V4 （V0，V4） 30 V5 （V0，V4，V

41、3，V5） 60 有關(guān)數(shù)據(jù)的存儲結(jié)構(gòu) 有向連通網(wǎng)絡(luò): G ，采用帶權(quán)鄰接矩陣cost 存儲具體步驟： （1）初始U=v0, 用輔助數(shù)組 distN。對已經(jīng)找到最短路徑終點的頂點 vi ( i U )，vi 所對應(yīng)的數(shù)組分量disti的值為負數(shù)；對從v0出發(fā)，尚未確定為最短路徑終點的頂點vj （j V - U )，vj 所對應(yīng)的數(shù)組分量distj的值為Wvj，而Wvj為從v0出發(fā)，考慮途經(jīng)已確定為終點的頂點，到達vj ( V - U )的最短路徑。初始時，對j V - U ，有distj=costvj; 而對U=v, 則有distv= - costvv。 （2）掃描dist 數(shù)組，找出非0、非負

42、且最小的distj（j V - U )，即從v0出發(fā)到vj（j V - U )的路徑是最短的。 （3）vj并入U ，則distj=-distj. （4）調(diào)整distk(k V - U )，考慮 從v0出發(fā)，途經(jīng)vj到達vk是否更短。比較： 若-distj+costjkdiskk 則distk= -diskj+ costjk (5)重復(fù)（2）（3）（4）。共 n-1次。 迪杰斯特拉算法涉及的數(shù)據(jù)和操作：7.6 最短路徑求解步驟dist1路徑終點1dist2路徑終點2dist3路徑終點3dist4路徑終點4dist5路徑終點5最短路徑的終點U：V輔助數(shù)組max100（V0,V5）10（V0,V2）

43、max 30（v0,v4）V2V0.V2i=1max-10（V0,V2）60（V0,V2,V3）30（V0，V4）V4V0,V2,V4i=2100（V0,V5）-10（V0,v2）50(V0,v4,v3）-30（V0,V4）maxV3V0,V2,V4,V3i=390（V0,V4,v5）-30（V0,V4）-50（V0,V4,v3）-10（V0,V2）maxV5V0,V2,V4,V3,V5i=460（V0,v4,v3,V5）7.6 最短路徑i=7max-60（V0,v4,v3,V5）-30（V0,V4）-50（V0,V4,v3）-10（V0,V2）迪杰斯特拉算法的求解過程void dijstra

44、( int costN, int v ) int distN,i,j,w for (i=0; iN; i+) disti=costvi; /初始化 distv=-distv; for( i=0; iN; i+) j=mincost(dist); /找非0、非負且最小的distj if( j=0);break; distj=-distj; / vj并入U中 for(k=0;k0) / vk是尚未到達的終點 if(-distj+costjkdistk) distk=-distj+costjk; /途經(jīng)vj到達vk的距離更短 for ( i=0; iN; i+) if(distj0)printf(“

45、%d, %d: %dn”,v,i,-disti);Dijkstra算法7.6 最短路徑 int mincost( int dist )/ 在V-U 集合中找頂點j，distj是dist 中的最小值 int i, min, j; min=MAX;j=0; for(i=0;i=0& distimin) min=disti;j=i; return(j); 7.6 最短路徑7.5.2所有頂點對之間的最短路徑 1 頂點對之間的最短路徑概念 所有頂點對之間的最短路徑是指：對于給定的有向網(wǎng)G=(V,E),要對G中任意一對頂點有序?qū) 、v ( u v ),找出u 到v 的最短距離和v 到u 的最短距離。解決

46、此問題的一個有效方法是:輪流以每一個頂點為源點,重復(fù)執(zhí)行迪杰斯特拉算法n次,即可求得每一對頂點之間的最短路徑,總的時間復(fù)雜度為O(n3)。下面將介紹用弗洛伊德(Floyd)算法來實現(xiàn)此功能,時間復(fù)雜度仍為O(n3),但該方法比調(diào)用n次迪杰斯特拉方法更直觀一些。2 弗洛伊德算法的基本思想 弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣costNN來存儲帶權(quán)有向圖。算法的基本思想是: 設(shè)置一個NxN的矩陣ANN，其中除對角線的元素都等于0外，其它元素Aij的值表示頂點i到頂點j的最短路徑長度，運算步驟為： 開始時，以任意兩個頂點之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為，此時, A ij

47、=costij, 以后逐步嘗試在原路徑中加入其它頂點作為中間頂點，如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為： 第一步，讓所有邊上加入中間頂點0，取Aij與Ai0+A0j中較小的值作Aij的值.因此，弗洛伊德算法可以描述為: A(0)ij=costij; /cost為圖的鄰接矩陣 A(k)ij=minA(k-1) ij, A(k-1) ik+A(k-1) kj其中 k=0,1,2, n-1 第二步，讓所有邊上加入中間頂點1，取Aij與Ai1+A1j中較小的值，完成后得到Aij ，如此進行下去，當?shù)趎步完成后，得到 Aij ,即為我們所

48、求結(jié)果, A ij表示頂點i到頂點j的最短距離。3 弗洛伊德算法實現(xiàn)Void floyd (int cost N ) int aNN, i, j,k; for ( i=0; iN; i+) for ( j=0; jN; j+) aij=costij; /初始化 for ( k=0; kN; k+) /考慮途經(jīng) vk(k=0,1,.n-1) for ( i =0; iN;i+) for (j=0; jN; j+) /圖中每對頂點 if (aik+akjaij) aij=aik+akj;for (i=0;iN; i+) /輸出路徑長度及路徑 for (j=0; jN; j+) printf( “(

49、%d, %d):%d”,i, j, aij);算法的時間復(fù)雜度為O（N 3 ), N為圖的頂點數(shù)。第七 章 圖 7.6 有向無環(huán)圖的應(yīng)用 一AOV網(wǎng)、AOE網(wǎng) 二 拓撲排序 三 關(guān)鍵路徑7.6 有向無環(huán)圖的應(yīng)用有向無環(huán)圖：沒有回路的有向圖 AOV網(wǎng)( activity on vertex net ) 用頂點表示活動，邊表示活動的順序關(guān)系的有向圖稱為AOV網(wǎng)應(yīng)用： 工程流程、生產(chǎn)過程中各道工序的流程、程序流程、課程的流程一 AOV網(wǎng) 某工程可分為7個子工程，若用頂點表示子工程（也稱活動）， 用弧表示子工程間的順序關(guān)系。工程流程可用如下AOV網(wǎng)表示例 V5 V3 V2 V0 V1 V4 V6對工程

50、問題，人們至少關(guān)心如下兩類問題：1）工程能否順序進行，即工程流程是否“合理”2）完成整項工程至少需要多少時間，哪些子工程是影響工程進度的關(guān)鍵子工程 為求解工程流程是否“合理”，通常用AOV網(wǎng)的有向圖表示工程流程二 AOV網(wǎng)與拓撲排序 1 拓撲排序 7.6 有向無環(huán)圖的應(yīng)用例1 某工程可分為V0、V1、V2、V3、V4、V5、V6 7個子工程， 工程流程可用如下AOV網(wǎng)表示。其中頂點：表示子工程（也稱活動）， 弧：表示子工程間的順序關(guān)系。 V5 V3 V2 V0 V1 V4 V6例 課程流程圖 某校計算機專業(yè)課程流程可AOV網(wǎng)表示。其中頂點：表示課程（也稱活動）， ?。罕硎菊n程間的先修關(guān)系；7.

51、6 有向無環(huán)圖的應(yīng)用c1c2c3c4c5c6c7C8c9c10c11c12程序設(shè)計離散數(shù)學數(shù)據(jù)結(jié)構(gòu)匯編語言算法分析計算機體系編譯方法操作系統(tǒng)高等數(shù)學線性代數(shù)電子電路數(shù)值分析無 c1c1,c2c1c3,c4c11c5,c3c3,c6無c9c9c9,c10,c1課程編號 課程名稱 先決條件 c4c1c2c3c12c9c10c11c6c7c8c5如何安排施工計劃？如何安排教學計劃？ 一個可行的施工計劃為：V0,V1,V2, V4,V3,V5,V6, 一個可行的學習計劃為：C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8 可行的計劃的特點：若在流程圖中頂點v是頂點u 的前趨

52、，則在計劃序列中頂點v 也是u的前趨。7.6 有向無環(huán)圖的應(yīng)用 V5 V3 V2 V0 V1 V4 V6c4c1c2c3c12c9c10c11c6c7c8c5拓撲序列：有向圖D的一個頂點序列稱作一個拓撲序列，如果該序列中任兩頂點v 、u ，若在D中v是u前趨，則在序列中v也是u前趨。拓撲排序： 就是將有向圖中頂點排成拓撲序列。拓撲排序的應(yīng)用 安排施工計劃（如上） 判斷工程流程的是否合理 如何判斷AOV網(wǎng)（有向圖）是否存在有向回路？AOV網(wǎng)（有向圖）不存在有向回路當且僅當能對AOV網(wǎng)進行拓撲排序7.6 有向無環(huán)圖的應(yīng)用 V5 V3 V2 V0 V1 V4 V62 拓撲排序方法：1）在有向圖選一無

53、前趨的頂點v，輸出；2）從有向圖中刪除v及以v為尾的孤；3）重復(fù)1、2、直接全部輸出全部頂點或有向圖中不存在無前趨頂點；例：V0,V1,V2,V3,V4,V5,V6如何在計算機上實現(xiàn)對有向圖的拓撲排序？7.6 有向無環(huán)圖的應(yīng)用 V5 V3 V2 V0 V1 V4 V61）拓撲排序方法的另一種描述(等價描述) （1） 選擇一入度為 0 頂點 v，輸出；（2） 將 v 鄰接到的頂點的入度減1；（3）重復(fù)1、2 直到輸出全部頂點或有向圖沒有入度為0的頂點；2）拓撲排序涉及的數(shù)據(jù)和操作：數(shù)據(jù)：有向圖，頂點的入度；操作： （1） 選擇一入度為 0 頂點v，輸出； （2） 將 v 鄰接到的頂點 u 的入度

54、減1； struct node int degree; struct node *link; ;typedef struct node NODE;3 拓撲排序算法7.6 有向無環(huán)圖的應(yīng)用3）有關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)01234562456334556 有向圖(AOV網(wǎng)) ： G 頂點的入度：int degree 整數(shù)棧int stack ：用于存儲入度為0的頂點的編號下標 入度 link0012232base654321010top初始時，只有v0,v1兩頂點的入度為07.6 有向無環(huán)圖的應(yīng)用 V5 V3 V2 V0 V1 V4 V64）建立AOV網(wǎng)的鄰接表算法 int create( NODE adjlist ) NODE *p; int num, i, v1,v2; sanf( “%dn”, &num); for (i=0; inum; i+) /初始化空關(guān)系圖 adjlisti.link=NULL; adjlisti.degree=0; for(; ;) scanf(“%d to %dn”, &v1, &v2);