數(shù)據(jù)結(jié)構(gòu)實(shí)例教程（C語(yǔ)言版）：第7章 圖的結(jié)構(gòu)分析與應(yīng)用

1、第7章圖的結(jié)構(gòu)分析與應(yīng)用 學(xué)習(xí)目標(biāo) 了解圖的定義及基本術(shù)語(yǔ)。 熟練掌握?qǐng)D的鄰接矩陣和鄰接鏈表存儲(chǔ)方法。 熟練掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷。 熟練掌握最小生成樹實(shí)現(xiàn)方法：普里姆算法(Prim)和克 魯斯卡爾(Kruskal)算法。 掌握求單源最短路徑的迪杰斯特拉(Dijkstra)算法，了解 求每對(duì)頂點(diǎn)間最短路徑的弗洛伊德(Floyd)算法。7.1圖的概念及相關(guān)術(shù)語(yǔ) 一、圖的概念 1、圖的定義：記為G=(V，E)，其中V是頂點(diǎn)的有窮非空集 合，E是邊的有窮集合。 2、無向圖的定義：每條邊都是沒有方向的圖。 3、有向圖的定義：每條邊都是有方向的圖。7.1圖的概念及相關(guān)術(shù)語(yǔ) 二、圖的相關(guān)術(shù)語(yǔ) 1、

2、無向完全圖的定義 ：無向圖中任意兩個(gè)頂點(diǎn)之間均有邊 相連接 。n個(gè)頂點(diǎn)的無向完全圖中有n(n-1)/2條邊。 2、有向完全圖的定義：有向圖中任意兩個(gè)頂點(diǎn)之間均有方 向互為相反兩條邊相連接 。有向完全圖中有n(n-1)條邊。 3、無向圖中度的定義：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目 。 4、有向圖中度的定義：出度是以該頂點(diǎn)為始點(diǎn)的邊的數(shù)目， 入度是以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目。頂點(diǎn)1的度為2頂點(diǎn)1的出度為2頂點(diǎn)1的入度為17.1圖的概念及相關(guān)術(shù)語(yǔ) 二、圖的相關(guān)術(shù)語(yǔ) 4、子圖的定義 ：若圖G=(V，E)，G=(V,E)，若V是 V的子集，E是E的子集，則稱圖G是G的一個(gè)子圖。 子圖子圖7.1圖的概念及相關(guān)術(shù)語(yǔ)

3、二、圖的相關(guān)術(shù)語(yǔ) 5、路徑、簡(jiǎn)單路徑和回路 路徑的定義：在無向圖中，若頂點(diǎn)Vp到頂點(diǎn)Vq存在一個(gè)頂 點(diǎn)序列Vp，V1，V2，Vi，Vq，使得Vp和頂點(diǎn)Vq相通。路徑1、3、2、4 簡(jiǎn)單路徑的定義：若Vp到Vq存在一條路徑，除了Vp和Vq可 以相同外，其余頂點(diǎn)均不相同，此路徑為一條簡(jiǎn)單路徑。簡(jiǎn)單路徑 簡(jiǎn)單回路或簡(jiǎn)單環(huán)的定義：起點(diǎn)與終點(diǎn)相同的簡(jiǎn)單路徑。簡(jiǎn)單環(huán)7.1圖的概念及相關(guān)術(shù)語(yǔ) 二、圖的相關(guān)術(shù)語(yǔ) 6、連通、連通圖、連通分量 連通的定義：若從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)互有路徑。 連通圖的定義：無向圖中任意兩頂點(diǎn)連通。 連通分量的定義：無向圖的極大連通子圖。頂點(diǎn)1和4連通頂點(diǎn)2和6非連通此圖為非連通圖連

4、通分量注：連通圖的連通分量就是本身。7.1圖的概念及相關(guān)術(shù)語(yǔ) 二、圖的相關(guān)術(shù)語(yǔ) 7、強(qiáng)連通圖和強(qiáng)連通分量 強(qiáng)連通圖的定義：在有向圖中任意兩個(gè)的頂點(diǎn)都連通 。 強(qiáng)連通分量的定義：有向圖的極大連通子圖。頂點(diǎn)2和1非連通頂點(diǎn)2和3非連通此圖為非強(qiáng)連通圖強(qiáng)連通分量注：強(qiáng)連通圖的強(qiáng)連通分量就是本身。7.2圖的存儲(chǔ)結(jié)構(gòu) 一、鄰接矩陣表示法 1、鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣(二維數(shù)組)。鄰接矩陣鄰接矩陣V0V1V2V30110101111010110對(duì)稱矩陣7.2圖的存儲(chǔ)結(jié)構(gòu) 一、鄰接矩陣表示法 2、頂點(diǎn)存儲(chǔ)：需要一個(gè)一維數(shù)組來完成。 3、圖的類型定義typedef struct char vexs

5、Num；/ vexs用于存放頂點(diǎn)信息 int edgesNumNum；/鄰接矩陣，edges存儲(chǔ)邊信息 int n,e；/分別代表圖的頂點(diǎn)數(shù)和邊數(shù) MGraph；/結(jié)構(gòu)體類型無向圖的鄰接矩陣建立算法源程序鏈接7.2圖的存儲(chǔ)結(jié)構(gòu) 二、鄰接表表示法 1、鄰接表表示法類似與樹的孩子鏈表表示法。 2、鄰接表的結(jié)點(diǎn)結(jié)構(gòu)和數(shù)組的結(jié)點(diǎn)結(jié)構(gòu)。adjvexnextvertexlink 鄰接表的結(jié)點(diǎn)結(jié)構(gòu) 數(shù)組的結(jié)點(diǎn)結(jié)構(gòu) 鄰接表無向圖的鄰接表建立算法源程序鏈接7.3圖的遍歷 一、深度優(yōu)先遍歷 1、實(shí)例描述：選擇從淮安出發(fā)，然后青島、煙臺(tái)、大連、西安、開封、上海、蘇州和揚(yáng)州旅游路線，每一條路線盡量延伸到所有城市。首先

6、將出發(fā)點(diǎn)V標(biāo)記為已訪問過，然后依次從V出發(fā)搜索 V的某個(gè)鄰接點(diǎn)W，若W未曾訪問過，則以W為新的出發(fā) 點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)V有路徑 相通的頂點(diǎn)均被訪問為止。7.3圖的遍歷 一、深度優(yōu)先遍歷 2、深度優(yōu)先遍歷過程V1V2V3V6V5V0V4V7V8回溯假設(shè)圖G的初始狀態(tài)是所有頂點(diǎn)均未曾訪問過，在G中 任選一頂點(diǎn)為出發(fā)點(diǎn)(源點(diǎn))。遍歷結(jié)果： V0,V1,V2,V3,V6,V4,V7,V8,V5注：遍歷結(jié)果不唯一深度優(yōu)先遍歷算法源程序鏈接7.3圖的遍歷 二、廣度優(yōu)先遍歷 1、實(shí)例描述：選擇從淮安出發(fā)， 然后青島、開封、揚(yáng)州、上海、煙臺(tái)、西安、蘇州和大連旅游路線，盡量先旅游附近的城

7、市，然后逐漸擴(kuò)大范圍。首先將出發(fā)點(diǎn)V標(biāo)記為已訪問過，然后依次從V出發(fā)搜索 V的每個(gè)鄰接點(diǎn)W1，W2，Wn，再依次訪問與W1， W2，Wn鄰接的所有未曾訪問過的頂點(diǎn)，至圖中所 有和源點(diǎn)V有路徑相通的頂點(diǎn)都已訪問到為止。7.3圖的遍歷 二、廣度優(yōu)先遍歷 2、廣度優(yōu)先遍歷過程V1V2V3V6V5V0V4V7V8假設(shè)圖G的初始狀態(tài)是所有頂點(diǎn)均未曾訪問過，在G中 任選一頂點(diǎn)為出發(fā)點(diǎn)(源點(diǎn))。遍歷結(jié)果： V0,V1, V3, V4, V5, V2,V6,V7,V8注：遍歷結(jié)果不唯一廣度優(yōu)先遍歷算法源程序鏈接7.4最小生成樹 一、相關(guān)概念 1、生成樹的定義：連通圖G的一個(gè)子圖如果是一棵包含G 的所有頂點(diǎn)的樹

8、。 2、樹的權(quán)的定義：生成樹各邊的權(quán)值總和。 3、最小生成樹的定義：權(quán)最小的生成樹，可簡(jiǎn)記為MST。 舉例：圖G的頂點(diǎn)表示城市，邊表示連接兩個(gè)城市之間的公路，假設(shè)城市之間沒有修建任何公路，那么為了把n個(gè)城市連接起來，最多可修建n(n-1)/2條公路，最少可修建n-1條公路，則圖G的生成樹表示了修建公路的可行方案。如果考慮修建造價(jià)，那么如何選擇n-1條線路，使得修建公路的總造價(jià)最小呢？這就是要構(gòu)造該圖的一棵最小生成樹。 4、作用 7.4最小生成樹 二、普里姆(Prim)算法 選擇一個(gè)頂點(diǎn)Vi作為源點(diǎn)， 并納入集合Vi；ABEDC58416237頂點(diǎn)集合： A選擇與Vi鄰接的頂點(diǎn)中，與Vi構(gòu)成所有

9、邊中權(quán)值最小的頂 點(diǎn)Vj并納入集合Vi，Vj； A,C選擇與Vi或者Vj鄰接的頂點(diǎn)中，與Vi或者Vj構(gòu)成所有邊中 的權(quán)值最小的頂點(diǎn)Vw并納入集合Vi，V，Vw；重復(fù)第三步，直到包含所有頂點(diǎn)（不允許出現(xiàn)回路）。 A,C,E A,C,E,D A,C,E,D,BABEDC41237.4最小生成樹 三、克魯斯卡爾(Kruskal)算法 選擇一條權(quán)值最小的邊，并納入集合E1 ；ABEDC58416237邊集合： (A,C)在剩下的邊當(dāng)中再選擇一條權(quán)值最小的邊，并納入集合E1，E2；(A,C),(D,E)重復(fù)執(zhí)行第二步，直到邊集合中已經(jīng)包含圖G所有頂點(diǎn)為止（不允許出現(xiàn)回路）。 (A,C),(D,E),(C

10、,E) (A,C),(D,E),(C,E),(B,C)ABEDC4132107.5最短路徑 一、單源最短路徑 1、單源最短路徑的定義:在有向網(wǎng)中，從某個(gè)源點(diǎn)V0出發(fā) 到其它各個(gè)頂點(diǎn)的最短路徑。12354209050302040 2、單源最短路徑求解方法： 迪杰斯特拉(Dijkstra) 方法循 環(huán)SWd2 d3 d4 d5p2 p3 p4 p5初始化1-20 30 90 1 1 1 111,2220 70 30 901 2 1 121,2,4420 40 30 701 4 1 431,2,4,3320 40 30 601 4 1 341,2,4,3,5520 40 30 601 4 1 37.5最短路徑 二、每一對(duì)頂點(diǎn)之間的最短路徑