圖的定義和基本術(shù)語(yǔ)

1、目 錄第6章 圖2 圖的定義和基本術(shù)語(yǔ)2 圖的存儲(chǔ)和創(chuàng)建36.2.1 圖的存儲(chǔ)表示36.2.2 圖的創(chuàng)建6 圖的遍歷66.3.1 深度優(yōu)先搜索66.3.2 廣度優(yōu)先搜索7 遍歷算法的應(yīng)用86.4.1 應(yīng)用問題概述86.4.2 求一條包含圖中所有頂點(diǎn)的簡(jiǎn)單路徑96.4.3 求距v0最短路徑長(zhǎng)度最長(zhǎng)的一個(gè)頂點(diǎn)10 圖的連通性問題116.5.1 無向圖的連通分量和生成樹116.5.2 最小生成樹13 有向無環(huán)圖及其應(yīng)用13第6章 圖6.1 圖的定義和基本術(shù)語(yǔ)1、 圖的特征任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。結(jié)點(diǎn)之間的關(guān)系是多對(duì)多的。G = (V,E)2、 基本術(shù)語(yǔ)結(jié)點(diǎn)：頂點(diǎn)結(jié)點(diǎn)間的關(guān)系：無向圖：邊(v,

2、w)，v與w互為鄰接點(diǎn)，邊(v,w)依附于頂點(diǎn)v,w，邊(v,w)和頂點(diǎn)v,w相關(guān)聯(lián)v的度：和v相關(guān)聯(lián)的邊的數(shù)目。有向圖：弧<v,w>，v弧尾，w弧頭，頂點(diǎn)v鄰接到頂點(diǎn)w，頂點(diǎn)w鄰接自頂點(diǎn)v，弧<v,w>和頂點(diǎn)v,w相關(guān)聯(lián)。v的入度：以v為頭的弧的數(shù)目；v的出度：以v為尾的弧的數(shù)目；v的度：v的入度與出度之和。路徑、回路(環(huán))、簡(jiǎn)單路徑、簡(jiǎn)單回路(簡(jiǎn)單環(huán))連通性：若從頂點(diǎn)v到頂點(diǎn)v有路徑，則稱v和v是連通的圖的規(guī)模：頂點(diǎn)數(shù)n、邊(弧)數(shù)e、頂點(diǎn)的度(有向圖：入度/出度)子圖：G= (V,E), G = (V,E)，若VÍV且E ÍE，則稱G是G的子圖

3、。圖的分類：1）關(guān)系的方向性（無向/有向）、關(guān)系上是否有附加的數(shù)權(quán)(圖/網(wǎng))有向圖、無向圖、有向網(wǎng)、無向網(wǎng)2）邊(弧)數(shù)：完全圖(邊數(shù)=n(n-1)/2的無向圖)、有向完全圖(弧數(shù)=n(n-1)的有向圖)稀疏圖(e<nlogn)、稠密圖(e>nlogn)3）連通性：無向圖：連通圖(任意兩頂點(diǎn)都是連通的)、連通分量(極大連通子圖)、生成樹(極小連通子圖)、生成森林有向圖：強(qiáng)/弱連通圖、強(qiáng)連通分量、生成樹(極小連通子圖)、生成森林3、 抽象數(shù)據(jù)類型定義ADT Graph數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R = VRVR = <v,w>|v

4、,wÎV且P(v,w)，<v,w>表示從v到w的弧，謂詞P(v,w) 定義了弧<v,w>的意義或信息 基本操作：CreateGraph(&G, V, VR)初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合操作結(jié)果：按V和VR的定義構(gòu)造圖GDestroyGraph(&G)初始條件：圖G存在操作結(jié)果：銷毀圖GLocateVex(G,u)初始條件：圖G已存在，u和G中頂點(diǎn)有相同特征操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置，否則返回其它信息GetVex(G, v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：返回v的值PutVex(&G,

5、 v, value)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：對(duì)v賦值valueFirstAdjVex(G, v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：返回v的第一個(gè)鄰接頂點(diǎn)。若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回“空”NextAdjVex(G, v, w)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)操作結(jié)果：返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”InsertVex(&G, v)初始條件：圖G存在，v和G中頂點(diǎn)有相同特征操作結(jié)果：在圖中增添新頂點(diǎn)vDeleteVex(&G, v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：

6、刪除G中頂點(diǎn)v及其相關(guān)的弧InsertArc(&G, v, w)初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)操作結(jié)果：在圖G中增添弧<v,w>，若G是無向的，則還應(yīng)增添對(duì)稱弧<w,v>DeleteArc(&G, v, w)初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)操作結(jié)果：刪除G中的弧<v,w>，若G是無向的，則還應(yīng)刪除對(duì)稱弧DFSTraverse(G, v, visit()初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，visit是對(duì)頂點(diǎn)的應(yīng)用函數(shù)操作結(jié)果：從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗

7、，則操作失敗BFSTraverse(G, v, visit()初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，visit是對(duì)頂點(diǎn)的應(yīng)用函數(shù)操作結(jié)果：從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗ADT Graph6.2 圖的存儲(chǔ)和創(chuàng)建6.2.1 圖的存儲(chǔ)表示1、 圖的存儲(chǔ)表示分析頂點(diǎn)之間的關(guān)系是多對(duì)多的(m:n)，由于m和n都是不定的，無法給出一個(gè)這種多對(duì)多的關(guān)系向線性關(guān)系的映射公式圖中的關(guān)系不能通過順序映像(即通過頂點(diǎn)之間的存儲(chǔ)位置反映頂點(diǎn)之間的邏輯關(guān)系)反映；必須另外引入存儲(chǔ)空間反映頂點(diǎn)之間的鄰接關(guān)系。圖的存儲(chǔ)結(jié)構(gòu)：1）頂點(diǎn)信息；2）

8、邊(弧)信息；3）整體信息：頂點(diǎn)數(shù)、邊(弧)數(shù)、圖的種類(有向圖、無向圖、有向網(wǎng)、無向網(wǎng))頂點(diǎn)集的存儲(chǔ)：圖的應(yīng)用中，頂點(diǎn)集動(dòng)態(tài)變化的幾率十分小頂點(diǎn)集可以采用順序表存儲(chǔ)，按預(yù)先估計(jì)的最大頂點(diǎn)數(shù)分配空間（順序表和鏈表：若數(shù)據(jù)元素集是靜態(tài)的，采用順序表要好(隨機(jī)存取)；若數(shù)據(jù)元素集是動(dòng)態(tài)的，則采用鏈表要好(動(dòng)態(tài)分配與釋放)）#defineMAX_VERTEX_NUM20/* 最大頂點(diǎn)數(shù)*/注意：順序表與順序映像之間的區(qū)別關(guān)系集的存儲(chǔ)：在頂點(diǎn)確定的情況下，邊或弧的數(shù)目也是不定的，且在實(shí)際應(yīng)用中，可能會(huì)改變圖中的頂點(diǎn)之間的關(guān)系。鄰接矩陣表示法：矩陣中的第i行第j列的元素反映圖中第i個(gè)頂點(diǎn)到第j個(gè)頂點(diǎn)是否

9、存在弧，若存在其附加的信息是什么。鄰接表表示法：將每一頂點(diǎn)的鄰接點(diǎn)位置串成一個(gè)鏈，稱為鄰接表。對(duì)于有向圖/網(wǎng)來說，該鄰接表反映的是頂點(diǎn)的出邊表。typedefenumDG, DN, AG, AN GraphKind;/*有向圖，有向網(wǎng)，無向圖，無向網(wǎng)*/2、 鄰接矩陣表示法（數(shù)組表示法）無向圖/網(wǎng)：對(duì)稱矩陣有向圖/網(wǎng)：非對(duì)稱矩陣圖：鄰接關(guān)系用1/0表示網(wǎng)：鄰接關(guān)系需要進(jìn)一步反映權(quán)值，用INFINITY表示無窮大，反映頂點(diǎn)之間無鄰接關(guān)系#defineINT_MAX32767/* 最大整數(shù)*/#defineINFINITYINT_MAX1) 鄰接矩陣typedef struct ArcCellin

10、tadj;/*頂點(diǎn)間關(guān)系，無權(quán)圖：0-不相鄰，1-相鄰有權(quán)圖，權(quán)值，INFINITY-不相鄰*/InfoType*info;/* 該弧相關(guān)信息的指針*/ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; 2) 圖的整體結(jié)構(gòu)typedef struct charvexsMAX_VERTEX_NUM; /* 有效的頂點(diǎn)下標(biāo)從0開始 */AdjMatrixarcs;/* 關(guān)系集 */intvexnum, arcnum;/* 頂點(diǎn)數(shù)、邊/弧數(shù) */GraphKindkind;/* 圖的種類*/MGraph;3、 鄰接表表示法無向圖/網(wǎng)：邊表，表結(jié)點(diǎn)的個(gè)數(shù)為邊

11、數(shù)的兩倍有向圖/網(wǎng)：出邊表，表結(jié)點(diǎn)的個(gè)數(shù)為弧數(shù)1) 鄰接表的表結(jié)點(diǎn)typedef struct ArcNodeintadjvex;/* 弧所指向的頂點(diǎn)的位置*/struct ArcNode*nextarc;/* 指向下一條弧的指針*/InfoType*info;ArcNode;2) 鄰接表的頭結(jié)點(diǎn)typedef struct VNodechardata;/* 頂點(diǎn)信息*/ArcNode*firstarc;/*鄰接表指針*/VNode, AdjListMAX_VERTEX_NUM;3) 圖的整體結(jié)構(gòu)typedef struct AdjListvertices;intvexnum, arcnum;

12、GraphKindkind;ALGraph;4、 鄰接矩陣與鄰接表的對(duì)比假設(shè)圖為G，頂點(diǎn)數(shù)為n，邊/弧數(shù)為e。A鄰接矩陣B鄰接表存儲(chǔ)空間O(n+n2)O(n+e)圖的創(chuàng)建算法T1(n)=O(e+n2)或T2(n)=O(e*n+n2)T1(n)=O(n+e)或T2(n)=O(e*n)T1(n)是指在輸入邊/弧時(shí)，輸入的頂點(diǎn)信息為頂點(diǎn)的編號(hào)；而T2(n)則指在輸入邊/弧時(shí)，輸入的為頂點(diǎn)本身的信息，此時(shí)需要查找頂點(diǎn)在圖中的位置無向圖中求第i頂點(diǎn)的度(第i行之和)或(第i列之和)G.verticesi.firstarc所指向的鄰接表包含的結(jié)點(diǎn)個(gè)數(shù)無向網(wǎng)中求第i頂點(diǎn)的度第i行/列中adj值不為INFIN

13、ITY的元素個(gè)數(shù)有向圖中求第i頂點(diǎn)的入/出度入度：(第i列)出度：(第i行)入度：掃描各頂點(diǎn)的鄰接表，統(tǒng)計(jì)表結(jié)點(diǎn)的adjvex為i的表結(jié)點(diǎn)個(gè)數(shù)T(n)=O(n+e)出度：G.verticesi.firstarc所指向的鄰接表包含的結(jié)點(diǎn)個(gè)數(shù)有向網(wǎng)中求第i頂點(diǎn)的入/出度入度：第i列中adj值不為INFINITY的元素個(gè)數(shù)出度：第i行中adj值不為INFINITY的元素個(gè)數(shù)統(tǒng)計(jì)邊/弧數(shù)無向圖：)無向網(wǎng)：中adj值不為INFINITY的元素個(gè)數(shù)的一半有向圖：有向網(wǎng)：中adj值不為INFINITY的元素個(gè)數(shù)無向圖/網(wǎng)：圖中表結(jié)點(diǎn)數(shù)目的一半有向圖/網(wǎng)：圖中表結(jié)點(diǎn)的數(shù)目結(jié)論：鄰接矩陣適于稠密圖，鄰接表適于稀

14、疏圖；鄰接表求有向圖的頂點(diǎn)的入度不方便，要遍歷全部的鄰接表。6.2.2 圖的創(chuàng)建基本過程：1） 輸入圖的類型，根據(jù)類型選擇相應(yīng)的創(chuàng)建算法2） 輸入圖的頂點(diǎn)數(shù)，邊/弧數(shù)3） 輸入并存儲(chǔ)頂點(diǎn)信息4） 輸入邊/弧所關(guān)聯(lián)的頂點(diǎn)對(duì)，將邊或弧的信息存儲(chǔ)到鄰接矩陣/鄰接表中圖的存儲(chǔ)結(jié)構(gòu)不同、圖的類型不同，都會(huì)影響創(chuàng)建算法的實(shí)現(xiàn)細(xì)節(jié)；但是，圖的總體創(chuàng)建流程是一致的（如上）。示例：用鄰接矩陣表示法構(gòu)造有向網(wǎng)GStatusCreateMDG(MGraph &G)/* 步驟2：輸入圖的頂點(diǎn)數(shù)、邊/弧數(shù)*/scanf(&G.vexnum, &G.arcnum, &IncInfo);/*

15、 IncInfo為0則各弧不含其它信息 */* 步驟3：輸入并存儲(chǔ)頂點(diǎn)信息*/for ( i = 0; i < G.vexnum ; i+)scanf ( &G.vexsi );/* 步驟4：輸入并存儲(chǔ)邊/弧信息*/for ( i = 0; i < G.vexnum ; i+)/* 鄰接矩陣初始化*/for ( j = 0; j < G.vexnum ; j+)G.arcsij = INFINITY, NULL;for ( k = 0; k < G.arcnum ; k+)scanf(&v1, &v2, &w);i = LocateVex

16、(G, v1); j = LocateVex(G, v2);G.arcsij.adj = w;if ( IncInfo) Input( *G.); /* *G.要求G.指向的空間在調(diào)用Input()前分配*/6.3 圖的遍歷6.3.1 深度優(yōu)先搜索1、 分析·類似于樹的先序遍歷·引入訪問標(biāo)志數(shù)組visit0:n-1，區(qū)分頂點(diǎn)是否已被訪問·非連通圖，需引入多個(gè)深度優(yōu)先搜索的起始頂點(diǎn)·遞歸算法或基于棧的非遞歸算法2、 基于邏輯結(jié)構(gòu)的算法BooleanvisitedMAX_VERTEX_NUM;

17、void DFSTraverse(Graph G)for ( v = 0; v < G.vexnum; + v) visitedv = FALSE;for ( v = 0; v < G.vexnum; + v)if ( !visitedv )DFS(G, v);void DFS(Graph G, int v)visitedv = TRUE; Visit(G, v);for ( w = FirstAdjVex( G, v); w; w = NextAdjVex(G, v, w) )if ( !visitedw )DFS(G, w);3、 基于某種存儲(chǔ)結(jié)構(gòu)的算法根據(jù)選擇的存儲(chǔ)結(jié)構(gòu)，決定

18、 FirstAdjVex()和NextAdjVex()的實(shí)現(xiàn)，重新整合算法。如采用鄰接矩陣表示法表示的圖，則DFS算法如下：void DFS (MGraph G, int v)visitedv = TRUE; Visit(G, v);for ( w = 0; w < G.vexnum; w +)if ( G.arcsvw.adj && !visitedw )DFS(G, w);如采用鄰接表表示法表示的圖，則DFS算法如下：void DFS (ALGraph G, int v)visitedv = TRUE; Visit(G, v);for ( p = G.vertices

19、v.firstarc; p; p = p->nextarc)if (!visitedp->adjvex )DFS(G, p->adjvex);6.3.2 廣度優(yōu)先搜索1、 分析·類似于樹的層次遍歷·引入visited訪問標(biāo)志數(shù)組·非連通圖，需引入多個(gè)廣度優(yōu)先搜索的起始頂點(diǎn)·引入隊(duì)列保存“頂點(diǎn)已訪問，但其鄰接點(diǎn)未全訪問”的頂點(diǎn)編號(hào)2、 基于邏輯結(jié)構(gòu)的算法void BFSTraverse(Graph G)for ( v = 0; v < G.vexnum; + v) visitedv = FALSE;InitQueue(Q);for

20、( v = 0; v < G.vexnum; + v)if ( !visitedv )/* 訪問某連通分量的起始頂點(diǎn)，起點(diǎn)入隊(duì)*/visitedv = TRUE; Visit(G, v);EnQueue(Q, v);while(!QueueEmpty(Q)/* 出隊(duì)，訪問出隊(duì)元素的鄰接點(diǎn)*/DeQueue(Q,u);for ( w = FirstAdjVex( G, u) ; w ; w = NextAdjVex(G, u, w)if ( !visitedw )/* 訪問頂點(diǎn)u的尚未訪問的鄰接點(diǎn)并入隊(duì)*/visitedw = TRUE; Visit(G, w);EnQueue(Q, w)

21、;3、 基于某種存儲(chǔ)結(jié)構(gòu)的算法如采用鄰接矩陣表示法表示的網(wǎng)，則算法如下：void BFSTraverse(MGraph G)for ( v = 0; v < G.vexnum; + v) visitedv = FALSE;InitQueue(Q);for ( v = 0; v < G.vexnum; + v)if ( !visitedv )/* 訪問某連通分量的起始頂點(diǎn)，起點(diǎn)入隊(duì)*/visitedv = TRUE; Visit(G, v);EnQueue(Q, v);while(!QueueEmpty(Q)/* 出隊(duì)，訪問出隊(duì)元素的鄰接點(diǎn)*/DeQueue(Q,u);for ( w

22、 = 0 ; w < G.vexnum; w + )if ( G.arcsuw.adj != INFINITY && !visitedw )/* 訪問頂點(diǎn)u的尚未訪問的鄰接點(diǎn)并入隊(duì)*/visitedw = TRUE; Visit(G, w);EnQueue(Q, w);如采用鄰接表表示法表示的網(wǎng)，則算法如下：void BFSTraverse(ALGraph G)for ( v = 0; v < G.vexnum; + v) visitedv = FALSE;InitQueue(Q);for ( v = 0; v < G.vexnum; + v)if ( !vi

23、sitedv )/* 訪問某連通分量的起始頂點(diǎn)，起點(diǎn)入隊(duì)*/visitedv = TRUE; Visit(G, v);EnQueue(Q, v);while(!QueueEmpty(Q)/* 出隊(duì)，訪問出隊(duì)元素的鄰接點(diǎn)*/DeQueue(Q,u);for ( p = G.verticesu.firstarc ; p ; p = p->nextarc )if ( !visitedp->adjvex )/* 訪問頂點(diǎn)u的尚未訪問的鄰接點(diǎn)并入隊(duì)*/visitedp->adjvex = TRUE; Visit(G, p->adjvex);EnQueue(Q, p->adj

24、vex);6.4 遍歷算法的應(yīng)用6.4.1 應(yīng)用問題概述圖的深度優(yōu)先遍歷：1、 求一條包含圖中所有頂點(diǎn)的簡(jiǎn)單路徑(簡(jiǎn)單回路)2、 判斷圖中是否存在環(huán)3、 求圖中通過給定頂點(diǎn)vk的簡(jiǎn)單回路 4、 判斷是否存在從頂點(diǎn)vi到頂點(diǎn)vj的的路徑圖的廣度優(yōu)先遍歷：1、 判斷是否存在從頂點(diǎn)vi到頂點(diǎn)vj的的路徑2、 求距v0最短路徑長(zhǎng)度最長(zhǎng)的一個(gè)頂點(diǎn)。3、 求v0和v1之間的最短路徑.4、 在頂點(diǎn)子集U中找出距離頂點(diǎn)v0最近的頂點(diǎn)5、 求頂點(diǎn)v0到其余每個(gè)頂點(diǎn)的最短路徑6、 求距離頂點(diǎn)v0的最短路徑長(zhǎng)度為k的所有頂點(diǎn)7、 判別v0和v1之間是否存在一條長(zhǎng)度為k的路徑（也可以用深度優(yōu)先搜索算法，結(jié)合回溯法）6

25、.4.2 求一條包含圖中所有頂點(diǎn)的簡(jiǎn)單路徑1、 思路對(duì)于任意的有向圖或無向圖G，并不一定都能找到符合題意的簡(jiǎn)單路徑。這樣的簡(jiǎn)單路徑要求包含個(gè)頂點(diǎn)，且互不相同。它的查找可以基于深度優(yōu)先遍歷。12345671234567(a)(b)在一個(gè)存在包含全部頂點(diǎn)的簡(jiǎn)單路徑的圖中，以下因素會(huì)影響該簡(jiǎn)單路徑是否能順利地查到：1） 起點(diǎn)的選擇：如圖(a)，其符合題意的一條簡(jiǎn)單路徑如圖(b)。若起點(diǎn)為1，則不能找到符合題意的簡(jiǎn)單路徑；2） 頂點(diǎn)的鄰接點(diǎn)次序：進(jìn)一步考察圖(a)，即使以2為起點(diǎn)，但是2的鄰接點(diǎn)選擇的是1，而不是5，此時(shí)也不能找到符合題意的解。在基于DFS的查找算法中，由于起點(diǎn)和鄰接點(diǎn)的選取是與頂點(diǎn)和

26、鄰接點(diǎn)的存儲(chǔ)次序以及算法的搜索次序有關(guān)，不可能依據(jù)特定的圖給出特定的解決算法。因此，在整個(gè)搜索中應(yīng)允許有查找失敗，此時(shí)可采取回溯到上一層的方法，繼續(xù)查找其他路徑。這樣，引入數(shù)組Path用來保存當(dāng)前已搜索的簡(jiǎn)單路徑上的頂點(diǎn)，引入計(jì)數(shù)器n用來記錄當(dāng)前該路徑上的頂點(diǎn)數(shù)。對(duì)DFS算法的修改如下：1） 計(jì)數(shù)器n的初始化，放在visited的初始化前后；2） 訪問頂點(diǎn)時(shí)，增加將該頂點(diǎn)序號(hào)入數(shù)組Path中，計(jì)數(shù)器n+；判斷是否已獲得所求路徑，是則輸出結(jié)束，否則繼續(xù)遍歷鄰接點(diǎn)；3） 某頂點(diǎn)的全部鄰接點(diǎn)都訪問后，仍未得到簡(jiǎn)單路徑，則回溯，將該頂點(diǎn)置為未訪問，計(jì)數(shù)器n-。2、 算法/* 鄰接矩陣表示法, 粗體字部

27、分為在深度優(yōu)先遍歷上的增加或修改的步驟*/voidHamilton(MGraph G)for(i=0; i<G.vexnum; i+)visitedi=FALSE; n=0;for(i=0; i<G.vexnum; i+)if ( !visitedi) DFS (G, i); voidDFS(MGraph G, int i)visitedi=TRUE; Pathn=i;n+;if(n=G.vexnum)Print(Path);/* 符合條件，輸出該簡(jiǎn)單路徑*/for(j=0; j<G.vexnum; j+)if( G.arcsij.adj && !visite

28、dj) DFS( G, j); visitedi=FALSE;n-;3、 思考1） 若圖中存在多條符合條件的路徑，本算法是輸出一條，還是輸出全部？2） 如何修改算法，變成判斷是否有包含全部頂點(diǎn)的簡(jiǎn)單路徑？3） 如何修改算法，輸出包含全部頂點(diǎn)的簡(jiǎn)單路徑的條數(shù)？4） 如何修改算法，輸出所有的簡(jiǎn)單回路？5） 考慮其他圖的存儲(chǔ)方法對(duì)算法的影響；6） 考慮在非遞歸的深度優(yōu)先遍歷算法上，如何修改使之適應(yīng)本問題的求解。6.4.3 求距v0最短路徑長(zhǎng)度最長(zhǎng)的一個(gè)頂點(diǎn)1、 思路由于題意強(qiáng)調(diào)為最短路徑，因此應(yīng)當(dāng)考慮BFS的算法應(yīng)用。本問題的求解轉(zhuǎn)變成：從v0出發(fā)進(jìn)行BFS，最后一層的頂點(diǎn)距離v0的最短路徑長(zhǎng)度最長(zhǎng)

29、。由于BFS類似于樹的按層次遍歷，需要引入隊(duì)列用來保存本身已訪問但其鄰接點(diǎn)尚未全部訪問的頂點(diǎn)。BFS遍歷中最后一層的頂點(diǎn)一定是最后出隊(duì)的若干頂點(diǎn)，隊(duì)列中最后一個(gè)出隊(duì)的頂點(diǎn)必定是符合題意的頂點(diǎn)。這樣，只需調(diào)用BFS的算法，將最后出隊(duì)的元素返回即可。2、 算法int MaxDistance(MGraph G, int v0)/* 初始化各頂點(diǎn)的訪問標(biāo)志，設(shè)置為未訪問*/for(i=0; i<G.vexnum; i+)visitedi=FALSE;InitQueue(Q);/* 不需要考慮其他的連通分量，因?yàn)樗蟮捻旤c(diǎn)必定與v0在同一個(gè)連通分量中 */EnQueue(Q, v0);visite

30、dv0 = TRUE;while( !QueueEmpty(Q)DeQueue(Q, v);for(w = 0; w < G.vexnum; w+)if(G.arcsvw.adj && !visitedw )visitedw=TRUE;EnQueue(Q, w);return(v);3、 思考1） 若要求輸出滿足條件的全部頂點(diǎn)，則如何修改上述算法；2） 考慮其它圖的存儲(chǔ)表示下的算法實(shí)現(xiàn)。4、 其它類似的應(yīng)用·求v0和v1之間的最短路徑；·在頂點(diǎn)子集U中找出距離頂點(diǎn)v0最近的頂點(diǎn)；·求頂點(diǎn)v0到其余每個(gè)頂點(diǎn)的最短路徑；·求距離頂點(diǎn)v0

31、的最短路徑長(zhǎng)度為K的所有頂點(diǎn)；·判別v0和v1之間是否存在長(zhǎng)度為K的路徑。6.5 圖的連通性問題6.5.1 無向圖的連通分量和生成樹1、 基本概念·連通分量的頂點(diǎn)集：即從該連通分量的某一頂點(diǎn)出發(fā)進(jìn)行搜索所得到的頂點(diǎn)訪問序列；·生成樹：·某連通分量的極小連通子圖·深度優(yōu)先搜索生成樹、廣度優(yōu)先搜索生成樹·由該連通分量的頂點(diǎn)集和搜索所經(jīng)過的邊組成·生成森林：非連通圖的各個(gè)連通分量的極小連通子圖構(gòu)成的集合2、 算法思路·也是圖的遍歷算法的應(yīng)用·將訪問頂點(diǎn)變成創(chuàng)建生成樹或增加一個(gè)結(jié)點(diǎn)到生成樹中的操作·生成

32、樹/森林的存儲(chǔ)表示采用孩子-兄弟表示法3、 深度優(yōu)先搜索生成樹/森林算法思路/* 基于抽象數(shù)據(jù)類型(邏輯結(jié)構(gòu))的算法*/void DFSForest(Graph G, CSTree &T)T = NULL;for ( v = 0; v < G.vexnum; + v) visitedv = FALSE;for ( v = 0; v < G.vexnum; + v)if ( !visitedv )p = ( CSTree ) malloc(sizeof(CSNode);*p = GetVex(G, v), NULL, NULL;if ( !T ) T = p;/* 第一棵生成

33、樹的根(T的根)*/else q->nextsbling = p;/* 其它生成樹的根(前一棵的“兄弟”) */q = p;/* q指示當(dāng)前生成樹的根 */DFSTree(G, v, p);/* 建立以p指向的結(jié)點(diǎn)為根結(jié)點(diǎn)的生成樹 */void DFSTree(Graph G, int v, CSTree & T)visitedv = TRUE; Visit(G, v);first = TRUE;/* 標(biāo)識(shí)下一個(gè)訪問的鄰接點(diǎn)是否為第一個(gè)未訪問的鄰接點(diǎn) */for ( w = FirstAdjVex( G, v); w; w = NextAdjVex(G, v, w) )if (

34、!visitedw )p = ( CSTree ) malloc(sizeof(CSNode);/* 分配孩子結(jié)點(diǎn)*/p = GetVex(G, w), NULL, NULL;if ( first )/* w是v的第一個(gè)未訪問的鄰接點(diǎn) */T->firstchild = p; first = FALSE;/*是根的第一個(gè)孩子 */ else q->nextsbling = p;/* 是上一鄰接點(diǎn)的右兄弟結(jié)點(diǎn) */q = p;/* 修改上一孩子結(jié)點(diǎn)的指針*/DFSTree(G, w, q);4、 廣度優(yōu)先搜索生成樹/森林算法思路引入隊(duì)列，除了保存“頂點(diǎn)已訪問，但其鄰接點(diǎn)未全訪問”的頂點(diǎn)編號(hào)以外，還須保存該頂點(diǎn)在生成樹中的對(duì)應(yīng)結(jié)點(diǎn)的指針。void BFSForest(Graph G, CSTree &T)T = NULL;for ( v = 0; v < G.vexnum; + v) v