離散數(shù)學(xué)中的圖論是專門研究圖性質(zhì)的一個(gè)數(shù)學(xué)分支

1、第七章 圖離散數(shù)學(xué)中的圖論是專門研究圖性質(zhì)的一個(gè)數(shù)學(xué)分支，但圖論注重研究圖的純數(shù)學(xué)性質(zhì)，而數(shù)據(jù)結(jié)構(gòu)中對圖的討論則側(cè)重于在計(jì)算機(jī)中如何表示圖以及如何實(shí)現(xiàn)圖的操作和應(yīng)用等。圖是較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因此和線性表、樹不同，雖然在遍歷圖的同時(shí)可以對頂點(diǎn)或弧進(jìn)行各種操作，但更多圖的應(yīng)用問題如求最小生成樹和最短路徑等在圖論的研究中都早已有了特定算法，在本章中主要是介紹它們在計(jì)算機(jī)中的具體實(shí)現(xiàn)。這些算法乍一看都比較難，應(yīng)多對照具體圖例的存儲(chǔ)結(jié)構(gòu)進(jìn)行學(xué)習(xí)。而圖遍歷的兩種搜索路徑和樹遍歷的兩種搜索路徑極為相似，應(yīng)將兩者的算法對照學(xué)習(xí)以便提高學(xué)習(xí)的效益。 第一節(jié) 圖的類型定義圖由一個(gè)頂點(diǎn)集和弧集構(gòu)成，通

2、常寫作：Graph=(V,VR)V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。VR<v,w>| v,wV，<v,w>表示從v到w的弧<v,w>表示從頂點(diǎn) v 到頂點(diǎn) w 的一條弧，其中頂點(diǎn) v 被稱為弧尾，頂點(diǎn) w 被稱作弧頭。由于弧是有方向的，故稱有向圖。(有向圖G1)例如下列定義的有向圖如上圖所示。G1=(V1, VR1)其中：V1 = A, B, C, D, EVR1 =<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>若<v,w&

3、gt;R 必有<w,v>R，則稱 (v,w) 為頂點(diǎn) v 和頂點(diǎn) w 之間存在一條邊。由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向圖。(無向圖G2)例如下列定義的無向圖如上所示。G2=(V2, VR2)其中：V2=A, B, C, D, E, FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F) 由于空的圖在實(shí)際應(yīng)用中沒有意義，因此一般不討論空的圖，即V是頂點(diǎn)的有窮非空集合。圖的抽象數(shù)據(jù)類型定義如下：ADT Graph 數(shù)據(jù)對象：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系：VR<v,w>| v,wV且P(v,w)，<v,w&g

4、t;表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息 基本操作P：結(jié)構(gòu)初始化CreateGraph(&G, V, VR);初始條件：V 是圖的頂點(diǎn)集，VR 是圖中弧的集合。操作結(jié)果：按 V 和 VR 的定義構(gòu)造圖 G。銷毀結(jié)構(gòu)DestroyGraph(&G);初始條件：圖 G 存在。操作結(jié)果：銷毀圖 G。 引用型操作LocateVex(G, u);初始條件：圖 G 存在，u 和 G 中頂點(diǎn)有相同特征。操作結(jié)果：若 G 中存在和 u 相同的頂點(diǎn)，則返回該頂點(diǎn)在圖中位置；否則返回其它信息。頂點(diǎn)在圖中的"位置"指的是，在圖的存儲(chǔ)結(jié)構(gòu)中頂

5、點(diǎn)之間自然形成的相對位置。GetVex(G, v);初始條件：圖 G 存在，v 是 G 中某個(gè)頂點(diǎn)。操作結(jié)果：返回 v 的值。 FirstAdjVex(G, v);初始條件：圖 G 存在，v 是 G 中某個(gè)頂點(diǎn)。操作結(jié)果：返回 v 的第一個(gè)鄰接點(diǎn)。若該頂點(diǎn)在 G 中沒有鄰接點(diǎn)，則返回"空"。若<v,w>G，則稱 w 為 v 的鄰接點(diǎn)，若(v,w)G，則稱 w 和 v 互為鄰接點(diǎn)。NextAdjVex(G, v, w);初始條件：圖 G 存在，v 是 G 中某個(gè)頂點(diǎn)，w 是 v 的鄰接頂點(diǎn)。操作結(jié)果：返回 v 的（相對于 w 的）下一個(gè)鄰接點(diǎn)。若 w 是 v 的最

6、后一個(gè)鄰接點(diǎn)，則返回"空"。若 v 有多個(gè)鄰接點(diǎn)，則在圖的存儲(chǔ)結(jié)構(gòu)建立之后，其鄰接點(diǎn)之間的相對次序也就自然形成了。 加工型操作PutVex(&G, v, value);初始條件：圖 G 存在，v 是 G 中某個(gè)頂點(diǎn)。操作結(jié)果：對 v 賦值 value。InsertVex(&G, v);初始條件：圖 G 存在，v 和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖 G 中增添新頂點(diǎn) v。DeleteVex(&G, v);初始條件：圖 G 存在，v 是 G 中某個(gè)頂點(diǎn)。操作結(jié)果：刪除 G 中頂點(diǎn) v 及其相關(guān)的弧。InsertArc(&G, v, w);初始條

7、件：圖 G 存在，v 和 w 是 G 中兩個(gè)頂點(diǎn)。操作結(jié)果：在 G 中增添弧<v,w>，若 G 是無向的，則還增添對稱弧<w,v>。DeleteArc(&G, v, w);初始條件：圖 G 存在，v 和 w 是 G 中兩個(gè)頂點(diǎn)。操作結(jié)果：在 G 中刪除弧<v,w>，若 G 是無向的，則還刪除對稱弧<w,v>。DFSTraverse(G, Visit();初始條件：圖 G 存在，Visit 是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對圖 G 進(jìn)行深度優(yōu)先遍歷。遍歷過程中對每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit 一次且僅一次。一旦 visit() 失敗，則操作失敗。B

8、FSTraverse(G, Visit();初始條件：圖 G 存在，Visit 是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對圖 G 進(jìn)行廣度優(yōu)先遍歷。遍歷過程中對每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit 一次且僅一次。一旦 visit() 失敗，則操作失敗。 ADT Graph介紹幾個(gè)有關(guān)圖的常用術(shù)語。頂點(diǎn)的度對無向圖而言，鄰接點(diǎn)的個(gè)數(shù)定義為頂點(diǎn)的度。例如(無向圖G2)中頂點(diǎn)B的度為3，頂點(diǎn)C的度為2。對有向圖而言，頂點(diǎn)的度為其出度和入度之和，其中出度定義為以該頂點(diǎn)為弧尾的弧的個(gè)數(shù)，入度定義為以該頂點(diǎn)為弧頭的弧的個(gè)數(shù)。例如(有向圖G1)中頂點(diǎn)D的度為3，其中出度為2，入度為1，頂點(diǎn)B的度為3，其中出度為1，入度為2。子圖

9、假設(shè)有兩個(gè)圖 G=(V,E) 和 G'=(V',E')，如果V'V 且 E'E，則稱 G'為G的子圖(subgraph)。例如，(有向圖G1) 的子圖的一些例子。路徑和回路若有向圖 G 中 k+1 個(gè)頂點(diǎn)之間都有弧存在（即<,>,<,>，<,>是圖 G 中的弧），則這個(gè)頂點(diǎn)的序列 , 為從頂點(diǎn)到頂點(diǎn)的一條有向路徑，路徑中弧的數(shù)目定義為路徑長度，若序列中的頂點(diǎn)都不相同，則為簡單路徑。對無向圖，相鄰頂點(diǎn)之間存在邊的 k+1 個(gè)頂點(diǎn)序列構(gòu)成一條長度為 k 的無向路徑。如果和是同一個(gè)頂點(diǎn)，則是一條由某個(gè)頂點(diǎn)出發(fā)又回到自

10、身的路徑，稱這種路徑為回路或環(huán)。例如(有向圖G1)中頂點(diǎn)序列 A,E,C,D 是一條路徑長度為3的簡單路徑，頂點(diǎn)序列 A,B,C,D,A 是一條長度為4的簡單回路。(無向圖G2)中頂點(diǎn)序列 A,B,F,C,D 是一條長度為4的無向路徑。連通圖和連通分量、強(qiáng)連通圖和強(qiáng)連通分量若無向圖中任意兩個(gè)頂點(diǎn)之間都存在一條無向路徑，則稱該無向圖為連通圖，否則稱為非連通圖。若有向圖中任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱該有向圖為強(qiáng)連通圖。例如(無向圖G2)和(有向圖G1)分別為連通圖和強(qiáng)連通圖。非連通圖中各個(gè)極大連通子圖稱作該圖的連通分量。如下圖為由兩個(gè)連通分量構(gòu)成的非連通圖。非強(qiáng)連通的有向圖中的極大強(qiáng)連通子圖稱作有向圖的強(qiáng)連通分量。例如下圖中的有向圖含有三個(gè)強(qiáng)連通分量。生成樹和生成森林一個(gè)含 n 個(gè)頂點(diǎn)的連通圖的生成樹是該圖中的一個(gè)極小連通子圖，它包含圖中 n 個(gè)頂點(diǎn)和足以構(gòu)成一棵樹的