第八章圖⒈教學(xué)內(nèi)容：8.1圖的基本概念8.2圖的存儲(chǔ)表示8.3圖的遍歷8.4圖的連通性8.5最小生成樹8.6最短路徑8.7有向無環(huán)圖及其應(yīng)用⒉教學(xué)目的：⑴理解圖的基本概念及術(shù)語；⑵掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；⑶熟練掌握?qǐng)D的兩種遍歷的算法思想、步驟；⑷理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；⑸領(lǐng)會(huì)并掌握拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑的算法思想。⒊教學(xué)重點(diǎn)：⑴理解圖的定義、術(shù)語及其含義；⑵掌握各種圖的鄰接矩陣表示法及其類型說明；⑶理解并掌握?qǐng)D的按深度優(yōu)先搜索遍歷方法和按廣度優(yōu)先搜索遍歷方法；⑷領(lǐng)會(huì)生成樹和最小生成樹的概念；⑸掌握由Prim算法思想構(gòu)造最小生成樹按Prim算法思想；⑹領(lǐng)會(huì)拓?fù)湫蛄泻屯負(fù)渑判虻母拍睿虎死斫獠⒄莆胀負(fù)渑判虻乃惴ㄋ枷?；⑻理解并掌握關(guān)鍵路徑的算法思想；⑼理解并掌握最短路徑的算法思想。⒋教學(xué)難點(diǎn)：⑴正確理解與區(qū)別圖的常用術(shù)語；⑵區(qū)別圖的兩種存儲(chǔ)結(jié)構(gòu)的不同點(diǎn)及其應(yīng)用場(chǎng)合；⑶關(guān)鍵路徑的算法思想；⑷最短路徑的算法思想。⒌學(xué)時(shí)安排：

12學(xué)時(shí)2/5/20231數(shù)據(jù)結(jié)構(gòu)講義8.1圖的基本概念圖的定義和術(shù)語圖的基本操作2/5/20232數(shù)據(jù)結(jié)構(gòu)講義8.1.1圖的定義和術(shù)語1．圖的定義圖(Graph)是由非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間關(guān)系——邊（或者弧）的集合組成，其形式化定義為：

G＝（V，E）V＝{vi|vi∈dataobject}，E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}

其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條直接連線，即偶對(duì)(vi,vj)表示一條邊。2/5/20233數(shù)據(jù)結(jié)構(gòu)講義2.圖的相關(guān)術(shù)語

⑴無向圖。在一個(gè)圖中，如果任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(duì)（vi,vj）∈E是無序的，即頂點(diǎn)之間的連線沒有方向，則稱該圖為無向圖。如前圖所示是一個(gè)無向圖G1。

⑵有向圖。在一個(gè)圖中，如果任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(duì)（vi,vj）∈E是有序的，即頂點(diǎn)之間的連線是有方向的，則稱該圖為有向圖。如下圖所示是一個(gè)有向圖G2：G2=(V2,E2)。2/5/20234數(shù)據(jù)結(jié)構(gòu)講義

⑶頂點(diǎn)、邊、弧、弧頭、弧尾。圖中，數(shù)據(jù)元素vi稱為頂點(diǎn)(vertex)；P(vi,vj)表示在頂點(diǎn)vi和頂點(diǎn)vj之間有一條直接連線。如果是在無向圖中，則稱這條連線為邊；如果是在有向圖中，一般稱這條連線為弧。邊用頂點(diǎn)的無序偶對(duì)（vi,vj）來表示，稱頂點(diǎn)vi和頂點(diǎn)vj互為鄰接點(diǎn)，邊（vi,vj）依附于頂點(diǎn)vi與頂點(diǎn)vj；弧用頂點(diǎn)的有序偶對(duì)<vi,vj>來表示，有序偶對(duì)的第一個(gè)結(jié)點(diǎn)vi被稱為始點(diǎn)（或弧尾），在圖中就是不帶箭頭的一端；有序偶對(duì)的第二個(gè)結(jié)點(diǎn)vj被稱為終點(diǎn)（或弧頭），在圖中就是帶箭頭的一端。

⑷無向完全圖。在一個(gè)無向圖中，如果任意兩頂點(diǎn)都有一條直接邊相連接，則稱該圖為無向完全圖。可以證明，在一個(gè)含有n個(gè)頂點(diǎn)的無向完全圖中，有n(n-1)/2條邊。

⑸有向完全圖。在一個(gè)有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，有n(n-1)條邊。2/5/20235數(shù)據(jù)結(jié)構(gòu)講義⑹稠密圖、稀疏圖。若一個(gè)圖接近完全圖，稱為稠密圖；稱邊數(shù)很少的圖為稀疏圖。

⑺頂點(diǎn)的度、入度、出度。頂點(diǎn)的度（degree）是指依附于某頂點(diǎn)v的邊數(shù)，通常記為TD(v)。在有向圖中，要區(qū)別頂點(diǎn)的入度與出度的概念。頂點(diǎn)v的入度是指以頂點(diǎn)為終點(diǎn)的弧的數(shù)目。記為ID(v)；頂點(diǎn)v出度是指以頂點(diǎn)v為始點(diǎn)的弧的數(shù)目，記為OD(v)。有TD(v)=ID(v)＋OD(v)。

可以證明，對(duì)于具有n個(gè)頂點(diǎn)、e條邊的圖，頂點(diǎn)vi的度TD(vi)與頂點(diǎn)的個(gè)數(shù)以及邊的數(shù)目滿足關(guān)系：2e=

2/5/20236數(shù)據(jù)結(jié)構(gòu)講義

⑻邊的權(quán)、網(wǎng)圖。與邊有關(guān)的數(shù)據(jù)信息稱為權(quán)（weight）。在實(shí)際應(yīng)用中，權(quán)值可以有某種含義。比如，在一個(gè)反映城市交通線路的圖中，邊上的權(quán)值可以表示該條線路的長(zhǎng)度或者等級(jí)；對(duì)于一個(gè)電子線路圖，邊上的權(quán)值可以表示兩個(gè)端點(diǎn)之間的電阻、電流或電壓值；對(duì)于反映工程進(jìn)度的圖而言，邊上的權(quán)值可以表示從前一個(gè)工程到后一個(gè)工程所需要的時(shí)間等等。邊上帶權(quán)的圖稱為網(wǎng)圖或網(wǎng)絡(luò)（network）。如果邊是有方向的帶權(quán)圖，則就是一個(gè)有向網(wǎng)圖。

⑼路徑、路徑長(zhǎng)度。頂點(diǎn)vp到頂點(diǎn)vq之間的路徑（path）是指頂點(diǎn)序列vp,vi1,vi2,…,vim,vq。其中，（vp,vi1），(vi1,vi2)，…,(vim,vq)分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長(zhǎng)度。2/5/20237數(shù)據(jù)結(jié)構(gòu)講義

⑽回路、簡(jiǎn)單路徑、簡(jiǎn)單回路。稱vi的路徑為回路或者環(huán)（cycle）。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。除第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)之外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路，或者簡(jiǎn)單環(huán)。

⑾子圖。對(duì)于圖G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，則稱圖G’是G的一個(gè)子圖。下圖示出了G2和G1的兩個(gè)子圖G’和G’’。2/5/20238數(shù)據(jù)結(jié)構(gòu)講義

⑿連通的、連通圖、連通分量。在無向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩頂點(diǎn)都是連通的，則稱該圖是連通圖。無向圖的極大連通子圖稱為連通分量。下圖(a)中有兩個(gè)連通分量，如圖(b)所示。2/5/20239數(shù)據(jù)結(jié)構(gòu)講義⒀強(qiáng)連通圖、強(qiáng)連通分量。對(duì)于有向圖來說，若圖中任意一對(duì)頂點(diǎn)vi和vj(i≠j)均有從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj有路徑，也有從vj到vi的路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。左下圖中有兩個(gè)強(qiáng)連通分量，分別是{v1,v2,v3}和{v4}，如右下圖所示。2/5/202310數(shù)據(jù)結(jié)構(gòu)講義

⒁生成樹。所謂連通圖G的生成樹，是G的包含其全部n個(gè)頂點(diǎn)的一個(gè)極小連通子圖。它必定包含且僅包含G的n-1條邊。下圖示出了圖G1的一棵生成樹。⒂生成森林。在非連通圖中，由每個(gè)連通分量都可得到一個(gè)極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個(gè)非連通圖的生成森林。2/5/202311數(shù)據(jù)結(jié)構(gòu)講義8.1.2圖的基本操作⑴CreatGraph（G）輸入圖G的頂點(diǎn)和邊，建立圖G的存儲(chǔ)。⑵DestroyGraph（G）釋放圖G占用的存儲(chǔ)空間。⑶GetVex（G，v）在圖G中找到頂點(diǎn)v，并返回頂點(diǎn)v的相關(guān)信息。⑷PutVex（G，v，value）在圖G中找到頂點(diǎn)v，并將value值賦給頂點(diǎn)v。⑸InsertVex（G，v）在圖G中增添新頂點(diǎn)v。⑹DeleteVex（G，v）在圖G中，刪除頂點(diǎn)v以及所有和頂點(diǎn)v相關(guān)聯(lián)的邊或弧。⑺InsertArc（G，v，w）在圖G中增添一條從頂點(diǎn)v到頂點(diǎn)w的邊或弧。⑻DeleteArc（G，v，w）在圖G中刪除一條從頂點(diǎn)v到頂點(diǎn)w的邊或弧。2/5/202312數(shù)據(jù)結(jié)構(gòu)講義⑼DFSTraverse（G，v）在圖G中，從頂點(diǎn)v出發(fā)深度優(yōu)先遍歷圖G。⑽BFSTtaverse（G，v）在圖G中，從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖G。

在圖中，頂點(diǎn)是沒有先后次序的，但當(dāng)采用某一種確定的存儲(chǔ)方式存儲(chǔ)后，存儲(chǔ)結(jié)構(gòu)中頂點(diǎn)的存儲(chǔ)次序構(gòu)成了頂點(diǎn)之間的相對(duì)次序；同樣的道理，對(duì)一個(gè)頂點(diǎn)的所有鄰接點(diǎn)，采用該頂點(diǎn)的第i個(gè)鄰接點(diǎn)表示與該頂點(diǎn)相鄰接的某個(gè)頂點(diǎn)的存儲(chǔ)順序，在這種意義下，圖的基本操作還有：⑾LocateVex（G，u）在圖G中找到頂點(diǎn)u，返回該頂點(diǎn)在圖中位置。⑿FirstAdjVex（G，v）在圖G中，返回v的第一個(gè)鄰接點(diǎn)。若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回“空”。⒀NextAdjVex（G，v，w）在圖G中，返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。2/5/202313數(shù)據(jù)結(jié)構(gòu)講義8.2圖的存儲(chǔ)表示鄰接矩陣鄰接表十字鏈表鄰接多重表2/5/202314數(shù)據(jù)結(jié)構(gòu)講義8.2.1鄰接矩陣所謂鄰接矩陣（AdjacencyMatrix）的存儲(chǔ)結(jié)構(gòu)，就是用一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，用矩陣表示圖中各頂點(diǎn)之間的鄰接關(guān)系。假設(shè)圖G＝（V，E）有n個(gè)確定的頂點(diǎn)，即V＝{v0,v1,…,vn-1},則表示G中各頂點(diǎn)相鄰關(guān)系為一個(gè)n×n的矩陣，矩陣的元素為：

A[i][j]=若G是網(wǎng)圖，則鄰接矩陣可定義為：

A[i][j]=

其中，wij表示邊(vi,vj)或<vi,vj>上的權(quán)值；∞表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。{1若(vi,vj)或<vi,vj>是E(G)中的邊0若(vi,vj)或<vi,vj>不是E(G)中的邊{wij若(vi,vj)或<vi,vj>是E(G)中的邊0或∞若(vi,vj)或<vi,vj>不是E(G)中的邊2/5/202315數(shù)據(jù)結(jié)構(gòu)講義用鄰接矩陣表示法表示的無向圖和網(wǎng)圖如下圖所示。2/5/202316數(shù)據(jù)結(jié)構(gòu)講義從圖的鄰接矩陣存儲(chǔ)方法容易看出這種表示具有以下特點(diǎn)：①無向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此，在具體存放鄰接矩陣時(shí)只需存放上（或下）三角矩陣的元素即可。②對(duì)于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度TD(vi)。③對(duì)于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度OD(vi)（或入度ID(vi)）。④用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測(cè)，所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲(chǔ)圖的局限性。2/5/202317數(shù)據(jù)結(jié)構(gòu)講義在用鄰接矩陣存儲(chǔ)圖時(shí)，除了用一個(gè)二維數(shù)組存儲(chǔ)用于表示頂點(diǎn)間相鄰關(guān)系的鄰接矩陣外，還需用一個(gè)一維數(shù)組來存儲(chǔ)頂點(diǎn)信息，另外還有圖的頂點(diǎn)數(shù)和邊數(shù)。故可將其形式描述如下：#defineMaxVertexNum100

/*最大頂點(diǎn)數(shù)設(shè)為100*/

typedefcharVertexType;

/*頂點(diǎn)類型設(shè)為字符型*/

typedefintEdgeType;

/*邊的權(quán)值設(shè)為整型*/

typedefstruct{VertexTypevexs[MaxVertexNum];/*頂點(diǎn)表*/

EdeTypeedges[MaxVertexNum][MaxVertexNum];/*鄰接矩陣，即邊表*/

intn,e;

/*頂點(diǎn)數(shù)和邊數(shù)*/}Mgragh;

/*Maragh是以鄰接矩陣存儲(chǔ)的圖類型*/2/5/202318數(shù)據(jù)結(jié)構(gòu)講義建立一個(gè)圖的鄰接矩陣存儲(chǔ)的算法如下：

voidCreateMGraph(MGraph*G)

/*建立有向圖G的鄰接矩陣存儲(chǔ)*/{inti,j,k,w;charch;

printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù)):\n");scanf("%d,%d",&(G->n),&(G->e));/*輸入頂點(diǎn)數(shù)和邊數(shù)*/

printf("請(qǐng)輸入頂點(diǎn)信息(輸入格式為:頂點(diǎn)號(hào)<CR>):\n");for(i=0;i<G->n;i++)/*輸入頂點(diǎn)信息，建立頂點(diǎn)表*/

scanf("\n%c",&(G->vexs[i]));for(i=0;i<G->n;i++)/*初始化鄰接矩陣*/

for(j=0;j<G->n;j++)G->edges[i][j]=0;

printf("請(qǐng)輸入每條邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)的序號(hào)(輸入格式為:i,j):\n");for(k=0;k<G->e;k++)

{

scanf("\n%d,%d",&i,&j);/*輸入e條邊，建立鄰接矩陣*/

G->edges[i][j]=1;

/*若加入G->edges[j][i]=1;，則為無向圖的鄰接矩陣存儲(chǔ)建立*/}}2/5/202319數(shù)據(jù)結(jié)構(gòu)講義8.2.2鄰接表鄰接表(AdjacencyList)是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對(duì)于圖G中的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表，再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。2/5/202320數(shù)據(jù)結(jié)構(gòu)講義在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)，如下圖所示。

一種是頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域（vertex）和指向第一條鄰接邊的指針域（firstedge）構(gòu)成，另一種是邊表（即鄰接表）結(jié)點(diǎn)，它由鄰接點(diǎn)域(adjvex)和指向下一條鄰接邊的指針域(next)構(gòu)成。對(duì)于網(wǎng)圖的邊表需再增設(shè)一個(gè)存儲(chǔ)邊上信息（如權(quán)值等）的域（info），網(wǎng)圖的邊表結(jié)構(gòu)如下圖所示。2/5/202321數(shù)據(jù)結(jié)構(gòu)講義下圖給出無向圖及對(duì)應(yīng)的鄰接表表示。2/5/202322數(shù)據(jù)結(jié)構(gòu)講義鄰接表表示的形式描述如下：＃defineMaxVerNum100/*最大頂點(diǎn)數(shù)為100*/

typedefstructnode{/*邊表結(jié)點(diǎn)*/

intadjvex;/*鄰接點(diǎn)域*/

structnode*next;/*指向下一個(gè)鄰接點(diǎn)的指針域*/

/*若要表示邊上信息，則應(yīng)增加一個(gè)數(shù)據(jù)域info*/}EdgeNode;

typedefstructvnode{/*頂點(diǎn)表結(jié)點(diǎn)*/

VertexTypevertex;/*頂點(diǎn)域*/

EdgeNode*firstedge;/*邊表頭指針*/}VertexNode;

typedefVertexNodeAdjList[MaxVertexNum];

/*AdjList是鄰接表類型*/

typedefstruct{

AdjListadjlist;/*鄰接表*/

intn,e;/*頂點(diǎn)數(shù)和邊數(shù)*/}ALGraph;/*ALGraph是以鄰接表方式存儲(chǔ)的圖類型*/2/5/202323數(shù)據(jù)結(jié)構(gòu)講義建立一個(gè)有向圖的鄰接表存儲(chǔ)的算法如下：

voidCreateALGraph(ALGraph*G)

/*建立有向圖的鄰接表存儲(chǔ)*/{inti,j,k;EdgeNode*s;printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù))：\n");scanf("%d,%d",&(G->n),&(G->e));/*讀入頂點(diǎn)數(shù)和邊數(shù)*/

printf("請(qǐng)輸入頂點(diǎn)信息(輸入格式為:頂點(diǎn)號(hào)<CR>)：\n");for(i=0;i<G->n;i++)/*建立有n個(gè)頂點(diǎn)的頂點(diǎn)表*/

{scanf("\n%c",&(G->adjlist[i].vertex));/*讀入頂點(diǎn)信息*/

G->adjlist[i].firstedge=NULL;/*頂點(diǎn)的邊表頭指針設(shè)為空*/}2/5/202324數(shù)據(jù)結(jié)構(gòu)講義

printf("請(qǐng)輸入邊的信息(輸入格式為:i,j)：\n");for(k=0;k<G->e;k++)/*建立邊表*/

{scanf("\n%d,%d",&i,&j);

/*讀入邊<Vi,Vj>的頂點(diǎn)對(duì)應(yīng)序號(hào)*/

s=(EdgeNode*)malloc(sizeof(EdgeNode));

/*生成新邊表結(jié)點(diǎn)s*/

s->adjvex=j;/*鄰接點(diǎn)序號(hào)為j*/

s->next=G->adjlist[i].firstedge;

/*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部*/

G->adjlist[i].firstedge=s;}}2/5/202325數(shù)據(jù)結(jié)構(gòu)講義若無向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。顯然，在邊稀疏(e<<n(n-1)/2)的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲(chǔ)空間，當(dāng)和邊相關(guān)的信息較多時(shí)更是如此。在無向圖的鄰接表中，頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)；而在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)vi的出度，為求入度，必須遍歷整個(gè)鄰接表。在所有鏈表中其鄰接點(diǎn)域的值為i的結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的入度。有時(shí)，為了便于確定頂點(diǎn)的入度或以頂點(diǎn)vi為頭的弧，可以建立一個(gè)有向圖的逆鄰接表，即對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)鏈接以vi為頭的弧的鏈表。2/5/202326數(shù)據(jù)結(jié)構(gòu)講義下圖所示為有向圖G2的鄰接表和逆鄰接表。2/5/202327數(shù)據(jù)結(jié)構(gòu)講義在建立鄰接表或逆鄰接表時(shí)，若輸入的頂點(diǎn)信息即為頂點(diǎn)的編號(hào)，則建立鄰接表的復(fù)雜度為O（n+e），否則，需要通過查找才能得到頂點(diǎn)在圖中位置，則時(shí)間復(fù)雜度為O（n·e）。

在鄰接表上容易找到任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)，但要判定任意兩個(gè)頂點(diǎn)（vi和vj）之間是否有邊或弧相連，則需搜索第i個(gè)或第j個(gè)鏈表，因此，不及鄰接矩陣方便。2/5/202328數(shù)據(jù)結(jié)構(gòu)講義8.2.3十字鏈表十字鏈表（OrthogonalList）是有向圖的一種存儲(chǔ)方法，它實(shí)際上是鄰接表與逆鄰接表的結(jié)合，即把每一條邊的邊結(jié)點(diǎn)分別組織到以弧尾頂點(diǎn)為頭結(jié)點(diǎn)的鏈表和以弧頭頂點(diǎn)為頭頂點(diǎn)的鏈表中。在十字鏈表表示中，頂點(diǎn)表和邊表的結(jié)點(diǎn)結(jié)構(gòu)分別如下圖的(a)和(b)所示。2/5/202329數(shù)據(jù)結(jié)構(gòu)講義在弧結(jié)點(diǎn)中有五個(gè)域：其中尾域(tailvex)和頭(headvex)分別指示弧尾和弧頭這兩個(gè)頂點(diǎn)在圖中的位置，鏈域hlink指向弧頭相同的下一條弧，鏈域tlink指向弧尾相同的下一條弧，info域指向該弧的相關(guān)信息?；☆^相同的弧在同一鏈表上，弧尾相同的弧也在同一鏈表上。它們的頭結(jié)點(diǎn)即為頂點(diǎn)結(jié)點(diǎn)，它由三個(gè)域組成：其中vertex域存儲(chǔ)和頂點(diǎn)相關(guān)的信息；firstin和firstout為兩個(gè)鏈域，分別指向以該頂點(diǎn)為弧頭或弧尾的第一個(gè)弧結(jié)點(diǎn)。若將有向圖的鄰接矩陣看成是稀疏矩陣的話，則十字鏈表也可以看成是鄰接矩陣的鏈表存儲(chǔ)結(jié)構(gòu)，在圖的十字鏈表中，弧結(jié)點(diǎn)所在的鏈表非循環(huán)鏈表，結(jié)點(diǎn)之間相對(duì)位置自然形成，不一定按頂點(diǎn)序號(hào)有序，表頭結(jié)點(diǎn)即頂點(diǎn)結(jié)點(diǎn)，它們之間是順序存儲(chǔ)。2/5/202330數(shù)據(jù)結(jié)構(gòu)講義例如，下圖所示為有向圖及其十字鏈表。2/5/202331數(shù)據(jù)結(jié)構(gòu)講義有向圖的十字鏈表存儲(chǔ)表示的形式描述如下：#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvex;

/*該弧的尾和頭頂點(diǎn)的位置*/

structArcBox*hlink,*tlink;

/*分別為弧頭相同和弧尾相同的弧的鏈域*/

InfoTypeinfo;

/*該弧相關(guān)信息的指針*/}ArcBox;typedefstructVexNode{VertexTypevertex:ArcBoxfisrin,firstout;

/*分別指向該頂點(diǎn)第一條入弧和出弧*/}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];/*表頭向量*/

intvexnum,arcnum;/*有向圖的頂點(diǎn)數(shù)和弧數(shù)*/}OLGraph;2/5/202332數(shù)據(jù)結(jié)構(gòu)講義下面給出建立一個(gè)有向圖的十字鏈表存儲(chǔ)的算法。通過該算法，只要輸入n個(gè)頂點(diǎn)的信息和e條弧的信息，便可建立該有向圖的十字鏈表，其算法內(nèi)容如下。voidCreateDG(LOGraph**G)/*采用十字鏈表表示，構(gòu)造有向圖G(G.kind=DG)*/{scanf(&(*G->brcnum),&(*G->arcnum),&IncInfo);/*IncInfo為0則各弧不含其實(shí)信息*/

for(i=0;i<*G->vexnum;++i)/*構(gòu)造表頭向量*/{

scanf(&(G->xlist[i].vertex));/*輸入頂點(diǎn)值*/*G->xlist[i].firstin=NulL;*G->xlist[i].firstout=NULL;

/*初始化指針*/}2/5/202333數(shù)據(jù)結(jié)構(gòu)講義

for(k=0;k<G.arcnum;++k)/*輸入各弧并構(gòu)造十字鏈表*/{scanf(&v1,&v2);

/*輸入一條弧的始點(diǎn)和終點(diǎn)*/

i=LocateVex(*G,v1);j=LocateVex(*G,v2);

/*確定v1和v2在G中位置*/

p=(ArcBox*)malloc(sizeof(ArcBox));/*假定有足夠空間*/*p={i,j,*G->xlist[j].fistin,*G->xlist[i].firstout,NULL}/*對(duì)弧結(jié)點(diǎn)賦值*/*G->xlist[j].fisrtin=*G->xlist[i].firstout=p;/*完成在入弧和出弧鏈頭的插入*/

if(IncInfo)/*若弧含有相關(guān)信息，則輸入*/

Input(p->info);}}2/5/202334數(shù)據(jù)結(jié)構(gòu)講義在十字鏈表中既容易找到以為尾的弧，也容易找到以vi為頭的弧，因而容易求得頂點(diǎn)的出度和入度（或需要，可在建立十字鏈表的同時(shí)求出）。同時(shí)，由建立一個(gè)有向圖的十字鏈表存儲(chǔ)的算法可知，建立十字鏈表的時(shí)間復(fù)雜度和建立鄰接表是相同的。在某些有向圖的應(yīng)用中，十字鏈表是很有用的工具。2/5/202335數(shù)據(jù)結(jié)構(gòu)講義8.2.4鄰接多重表鄰接多重表(AdjacencyMultilist)主要用于存儲(chǔ)無向圖。因?yàn)椋绻绵徑颖泶鎯?chǔ)無向圖，每條邊的兩個(gè)邊結(jié)點(diǎn)分別在以該邊所依附的兩個(gè)頂點(diǎn)為頭結(jié)點(diǎn)的鏈表中，這給圖的某些操作帶來不便。例如，對(duì)已訪問過的邊做標(biāo)記，或者要?jiǎng)h除圖中某一條邊等，都需要找到表示同一條邊的兩個(gè)結(jié)點(diǎn)。因此，在進(jìn)行這一類操作的無向圖的問題中采用鄰接多重表作存儲(chǔ)結(jié)構(gòu)更為適宜。2/5/202336數(shù)據(jù)結(jié)構(gòu)講義鄰接多重表的存儲(chǔ)結(jié)構(gòu)和十字鏈表類似，也是由頂點(diǎn)表和邊表組成，每一條邊用一個(gè)結(jié)點(diǎn)表示，其頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)和邊表結(jié)點(diǎn)結(jié)構(gòu)如下圖所示。2/5/202337數(shù)據(jù)結(jié)構(gòu)講義其中，頂點(diǎn)表由兩個(gè)域組成，vertex域存儲(chǔ)和該頂點(diǎn)相關(guān)的信息firstedge域指示第一條依附于該頂點(diǎn)的邊；邊表結(jié)點(diǎn)由六個(gè)域組成，mark為標(biāo)記域，可用以標(biāo)記該條邊是否被搜索過；ivex和jvex為該邊依附的兩個(gè)頂點(diǎn)在圖中的位置；ilink指向下一條依附于頂點(diǎn)ivex的邊;jlink指向下一條依附于頂點(diǎn)jvex的邊，info為指向和邊相關(guān)的各種信息的指針域。2/5/202338數(shù)據(jù)結(jié)構(gòu)講義例如，下圖所示為無向圖G1的鄰接多重表。在鄰接多重表中，所有依附于同一頂點(diǎn)的邊串聯(lián)在同一鏈表中，由于每條邊依附于兩個(gè)頂點(diǎn)，則每個(gè)邊結(jié)點(diǎn)同時(shí)鏈接在兩個(gè)鏈表中。對(duì)無向圖而言，其鄰接多重表和鄰接表的差別，僅僅在于同一條邊在鄰接表中用兩個(gè)結(jié)點(diǎn)表示，而在鄰接多重表中只有一個(gè)結(jié)點(diǎn)。因此，除了在邊結(jié)點(diǎn)中增加一個(gè)標(biāo)志域外，鄰接多重表所需的存儲(chǔ)量和鄰接表相同。在鄰接多重表上，各種基本操作的實(shí)現(xiàn)亦和鄰接表相似。2/5/202339數(shù)據(jù)結(jié)構(gòu)講義鄰接多重表存儲(chǔ)表示的形式描述如下：#defineMAX_VERTEX_NUM20typedefemnu{unvisited,visited}VisitIf;typedefstructEBox{VisitIfmark:

/*訪問標(biāo)記*/

intivex,jvex;

/*該邊依附的兩個(gè)頂點(diǎn)的位置*/

structEBoxilink,jlink;/*分別指向依附這兩個(gè)頂點(diǎn)的下一條邊*/

InfoTypeinfo;

/*該邊信息指針*/}EBox;typedefstructVexBox{VertexTypedata;EBoxfistedge;

/*指向第一條依附該頂點(diǎn)的邊*/}VexBox;typedefstruct{VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;/*無向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)*/}AMLGraph;2/5/202340數(shù)據(jù)結(jié)構(gòu)講義8.3圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索2/5/202341數(shù)據(jù)結(jié)構(gòu)講義圖的遍歷是指從圖中的任一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪問一次且只訪問一次。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎(chǔ)之上。由于圖結(jié)構(gòu)本身的復(fù)雜性，所以圖的遍歷操作也較復(fù)雜，主要表現(xiàn)在以下四個(gè)方面：①在圖結(jié)構(gòu)中，沒有一個(gè)“自然”的首結(jié)點(diǎn)，圖中任意一個(gè)頂點(diǎn)都可作為第一個(gè)被訪問的結(jié)點(diǎn)。②在非連通圖中，從一個(gè)頂點(diǎn)出發(fā)，只能夠訪問它所在的連通分量上的所有頂點(diǎn)，因此，還需考慮如何選取下一個(gè)出發(fā)點(diǎn)以訪問圖中其余的連通分量。③在圖結(jié)構(gòu)中，如果有回路存在，那么一個(gè)頂點(diǎn)被訪問之后，有可能沿回路又回到該頂點(diǎn)。④在圖結(jié)構(gòu)中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)這樣的頂點(diǎn)訪問過后，存在如何選取下一個(gè)要訪問的頂點(diǎn)的問題。2/5/202342數(shù)據(jù)結(jié)構(gòu)講義8.3.1深度優(yōu)先搜索深度優(yōu)先搜索（Depth_FisrstSearch）遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，則深度優(yōu)先搜索可從圖中某個(gè)頂點(diǎn)發(fā)v出發(fā)，訪問此頂點(diǎn)，然后依次從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。2/5/202343數(shù)據(jù)結(jié)構(gòu)講義以下圖的無向圖G5為例，進(jìn)行圖的深度優(yōu)先搜索。假設(shè)從頂點(diǎn)v1出發(fā)進(jìn)行搜索，在訪問了頂點(diǎn)v1之后，選擇鄰接點(diǎn)v2。因?yàn)関2未曾訪問，則從v2出發(fā)進(jìn)行搜索。依次類推，接著從v4、v8、v5出發(fā)進(jìn)行搜索。在訪問了v5之后，由于v5的鄰接點(diǎn)都已被訪問，則搜索回到v8。由于同樣的理由，搜索繼續(xù)回到v4，v2直至v1，此時(shí)由于v1的另一個(gè)鄰接點(diǎn)未被訪問，則搜索又從v1到v3，再繼續(xù)進(jìn)行下去由此，得到的頂點(diǎn)訪問序列為：

v1→v2→v4→v8→v5→v3→v6→v72/5/202344數(shù)據(jù)結(jié)構(gòu)講義顯然，這是一個(gè)遞歸的過程。為了在遍歷過程中便于區(qū)分頂點(diǎn)是否已被訪問，需附設(shè)訪問標(biāo)志數(shù)組visited[0:n-1]，其初值為FALSE，一旦某個(gè)頂點(diǎn)被訪問，則其相應(yīng)的分量置為TRUE。

從圖的某一點(diǎn)v出發(fā)，遞歸地進(jìn)行深度優(yōu)先遍歷的算法。voidDFS(GraphG,intv)/*從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/{visited[v]=TRUE;VisitFunc(v);/*訪問第v個(gè)頂點(diǎn)*/

for(w=FisrAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);/*對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFS*/}2/5/202345數(shù)據(jù)結(jié)構(gòu)講義以下算法給出了對(duì)以鄰接表為存儲(chǔ)結(jié)構(gòu)的整個(gè)圖G進(jìn)行深度優(yōu)先遍歷實(shí)現(xiàn)的C語言描述。

voidDFSTraverseAL(ALGraph*G)

/*深度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖G*/

{inti;

for(i=0;i<G->n;i++)

visited[i]=FALSE;/*標(biāo)志向量初始化*/

for(i=0;i<G->n;i++)if(!visited[i])DFSAL(G,i);/*vi未訪問過，從vi開始DFS搜索*/}2/5/202346數(shù)據(jù)結(jié)構(gòu)講義

voidDFSAL(ALGraph*G,inti)

/*以Vi為出發(fā)點(diǎn)對(duì)鄰接表存儲(chǔ)的圖G進(jìn)行DFS搜索*/{EdgeNode*p;printf("visitvertex:V%c\n",G->adjlist[i].vertex);

/*訪問頂點(diǎn)Vi*/

visited[i]=TRUE;/*標(biāo)記Vi已訪問*/

p=G->adjlist[i].firstedge;/*取Vi邊表的頭指針*/

while(p)/*依次搜索Vi的鄰接點(diǎn)Vj，j=p->adjva*/{if(!visited[p->adjvex])

/*若Vj尚未訪問，則以Vj為出發(fā)點(diǎn)向縱深搜索*/

DFSAL(G,p->adjvex); p=p->next;/*找Vi的下一個(gè)鄰接點(diǎn)*/}}2/5/202347數(shù)據(jù)結(jié)構(gòu)講義分析上述算法，在遍歷時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。因此，遍歷圖的過程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。當(dāng)用二維數(shù)組表示鄰接矩陣圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(n2)，其中n為圖中頂點(diǎn)數(shù)。而當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為O(e)，其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當(dāng)以鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n+e)。2/5/202348數(shù)據(jù)結(jié)構(gòu)講義8.3.2廣度優(yōu)先搜索廣度優(yōu)先搜索（Breadth_FirstSearch）遍歷類似于樹的按層次遍歷的過程。假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個(gè)未曾訪問過和鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程中以v為起始點(diǎn)，由近至遠(yuǎn)，依次訪問和v有路徑相通且路徑長(zhǎng)度為1,2,…的頂點(diǎn)。2/5/202349數(shù)據(jù)結(jié)構(gòu)講義例如，對(duì)下圖所示無向圖G5進(jìn)行廣度優(yōu)先搜索遍歷，首先訪問v1和v1的鄰接點(diǎn)v2和v3，然后依次訪問v2的鄰接點(diǎn)v4和v5及v3的鄰接點(diǎn)v6和v7，最后訪問v4的鄰接點(diǎn)v8。由于這些頂點(diǎn)的鄰接點(diǎn)均已被訪問，并且圖中所有頂點(diǎn)都被訪問，由些完成了圖的遍歷。得到的頂點(diǎn)訪問序列為：

v1→v2→v3→v4→v5→v6→v7→v82/5/202350數(shù)據(jù)結(jié)構(gòu)講義和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個(gè)訪問標(biāo)志數(shù)組。并且，為了順次訪問路徑長(zhǎng)度為2、3、…的頂點(diǎn)，需附設(shè)隊(duì)列以存儲(chǔ)已被訪問的路徑長(zhǎng)度為1、2、…的頂點(diǎn)。從圖的某一點(diǎn)v出發(fā)，遞歸地進(jìn)行廣度優(yōu)先遍歷的過程如算法所示。2/5/202351數(shù)據(jù)結(jié)構(gòu)講義voidBFSTraverse(GraphG,Status(*Visit)(intv))

/*按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited*/{for(v=0;v<G,vexnum;++v)visited[v]=FALSEInitQueue(Q);/*置空的輔助隊(duì)列Q*

if(!visited[v])/*v尚未訪問*/

{EnQucue(Q,v);/*v入隊(duì)列*/

while(!QueueEmpty(Q)){DeQueue(Q,u);/*隊(duì)頭元素出隊(duì)并置為u*/visited[u]=TRUE;visit(u);/*訪問u*/

for(w=FistAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w])EnQueue(Q,w);/*u的尚未訪問的鄰接頂點(diǎn)w入隊(duì)列Q*/

}}}2/5/202352數(shù)據(jù)結(jié)構(gòu)講義以下算法給出了對(duì)以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的整個(gè)圖G進(jìn)行深度優(yōu)先遍歷實(shí)現(xiàn)的C語言描述。

voidBFSTraverseAL(MGraph*G)

/*廣度優(yōu)先遍歷以鄰接矩陣存儲(chǔ)的圖G*/

{inti;for(i=0;i<G->n;i++) visited[i]=FALSE;/*標(biāo)志向量初始化*/

for(i=0;i<G->n;i++) if(!visited[i])BFSM(G,i);

/*vi未訪問過，從vi開始BFS搜索*/

}2/5/202353數(shù)據(jù)結(jié)構(gòu)講義voidBFSM(MGraph*G,intk)

/*以Vi為出發(fā)點(diǎn)，對(duì)鄰接矩陣存儲(chǔ)的圖G進(jìn)行BFS搜索*/{inti,j;CirQueueQ;InitQueue(&Q);printf("visitvertex:V%c\n",G->vexs[k]);/*訪問原點(diǎn)Vk*/visited[k]=TRUE;EnQueue(&Q,k);/*原點(diǎn)Vk入隊(duì)列*/

while(!QueueEmpty(&Q)){i=DeQueue(&Q);/*Vi出隊(duì)列*/

for(j=0;j<G->n;j++)/*依次搜索Vi的鄰接點(diǎn)Vj*/

if(G->edges[i][j]==1&&!visited[j])/*若Vj未訪問*/

{printf("visitvertex:V%c\n",G->vexs[j]);/*訪問Vj*/visited[j]=TRUE;

EnQueue(&Q,j);/*訪問過的Vj入隊(duì)列*/}}

}2/5/202354數(shù)據(jù)結(jié)構(gòu)講義分析上述算法，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)質(zhì)是通過邊或弧找鄰接點(diǎn)的過程，因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪問的順序不同。2/5/202355數(shù)據(jù)結(jié)構(gòu)講義8.4圖的連通性有向圖的連通性有向圖的連通性生成樹和生成森林關(guān)節(jié)點(diǎn)和重連通分量2/5/202356數(shù)據(jù)結(jié)構(gòu)講義8.4.1無向圖的連通性在對(duì)無向圖進(jìn)行遍歷時(shí)，對(duì)于連通圖，僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有頂點(diǎn)。對(duì)非連通圖，則需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為其各個(gè)連通分量中的頂點(diǎn)集。例如，一個(gè)非連通圖G3，按照G3的鄰接表進(jìn)行深度優(yōu)先搜索遍歷，需由算法調(diào)用兩次DFS（即分別從頂點(diǎn)A和D出發(fā)），得到的頂點(diǎn)訪問序列分別為：

ABFE

CE

這兩個(gè)頂點(diǎn)集分別加上所有依附于這些頂點(diǎn)的邊，便構(gòu)成了非連通圖G3的兩個(gè)連通分量。2/5/202357數(shù)據(jù)結(jié)構(gòu)講義因此，要想判定一個(gè)無向圖是否為連通圖，或有幾個(gè)連通分量，就可設(shè)一個(gè)計(jì)數(shù)變量count，初始時(shí)取值為0，在算法8.5的第二個(gè)for循環(huán)中，每調(diào)用一次DFS，就給count增1。這樣，當(dāng)整個(gè)算法結(jié)束時(shí)，依據(jù)count的值，就可確定圖的連通性了。2/5/202358數(shù)據(jù)結(jié)構(gòu)講義8.4.2有向圖的連通性有向圖的連通性不同于無向圖的連通性，可分為弱連通、單側(cè)連通和強(qiáng)連通。這里僅就有向圖的強(qiáng)連通性以及強(qiáng)連通分量的判定進(jìn)行介紹。深度優(yōu)先搜索是求有向圖的強(qiáng)連通分量的一個(gè)有效方法。假設(shè)以十字鏈表作有向圖的存儲(chǔ)結(jié)構(gòu)，則求強(qiáng)連通分量的步驟如下：2/5/202359數(shù)據(jù)結(jié)構(gòu)講義⑴在有向圖G上，從某個(gè)頂點(diǎn)出發(fā)沿以該頂點(diǎn)為尾的弧進(jìn)行深度優(yōu)先搜索遍歷，并按其所有鄰接點(diǎn)的搜索都完成(即退出DFS函數(shù))的順序?qū)㈨旤c(diǎn)排列起來。此時(shí)需對(duì)8.3.1中的算法作如下兩點(diǎn)修改：①在進(jìn)入DFSTraverseAL函數(shù)時(shí)首先進(jìn)行計(jì)數(shù)變量的初始化，即在入口處加上count=0的語句；②在退出函數(shù)之前將完成搜索的頂點(diǎn)號(hào)記錄在另一個(gè)輔助數(shù)組finished[vexnum]中，即在函數(shù)DFSAL結(jié)束之前加上finished[++count]=v的語句。⑵在有向圖G上，從最后完成搜索的頂點(diǎn)（即finished[vexnum-1]中的頂點(diǎn)）出發(fā)，沿著以該頂點(diǎn)為頭的弧作逆向的深度搜索遍歷，若此次遍歷不能訪問到有向圖中所有頂點(diǎn)，則從余下頂點(diǎn)中最后完成搜索的那個(gè)頂點(diǎn)出發(fā)，繼續(xù)作逆向的深度優(yōu)先搜索遍歷。依次類推，直至有向圖中所有頂點(diǎn)都被訪問到為止。此時(shí)調(diào)用DFSTraverseAL時(shí)需作如下修改：函數(shù)中第二個(gè)循環(huán)語句的邊界條件應(yīng)改為v從finished[vexnum-1]至finished[0]。

由此，每一次調(diào)用DFSAL作逆向深度優(yōu)先遍歷所訪問到的頂點(diǎn)集便是有向圖G中一個(gè)強(qiáng)連通分量的頂點(diǎn)集。2/5/202360數(shù)據(jù)結(jié)構(gòu)講義例如下圖所示的有向圖，假設(shè)從頂點(diǎn)v1出發(fā)作深度優(yōu)先搜索遍歷，得到finished數(shù)組中的頂點(diǎn)號(hào)為(1,3,2,0)；則再從頂點(diǎn)v1出發(fā)作逆向的深度優(yōu)先搜索遍歷，得到兩個(gè)頂點(diǎn)集{v1,v3,v4}和{v2}，這就是該有向圖的兩個(gè)強(qiáng)連通分量的頂點(diǎn)集。2/5/202361數(shù)據(jù)結(jié)構(gòu)講義上述求強(qiáng)連通分量的第二步，其實(shí)質(zhì)為：⑴構(gòu)造一個(gè)有向圖Gr，設(shè)G=(V,{A})，則Gr=(Vr，{Ar})對(duì)于所有<vi,vj>∈A，必有<vj,vi>∈Ar。即Gr中擁有和G方向相反的??；⑵在有向圖Gr上，從頂點(diǎn)finished[vexnum-1]出發(fā)作深度優(yōu)先遍歷?？梢宰C明，在Gr上所得深度優(yōu)先生成森林中每一棵樹的頂點(diǎn)集即為G的強(qiáng)連通分量的頂點(diǎn)集。顯然，利用遍歷求強(qiáng)連通分量的時(shí)間復(fù)雜度亦和遍歷相同。2/5/202362數(shù)據(jù)結(jié)構(gòu)講義8.4.3生成樹和生成森林

在這一小節(jié)里，我們將給出通過對(duì)圖的遍歷，得到圖的生成樹或生成森林的算法。設(shè)E(G)為連通圖G中所有邊的集合，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，必定將E(G)分成兩個(gè)集合T(G)和B(G)，其中T(G)是遍歷圖過程中歷經(jīng)的邊的集合；B(G)是剩余的邊的集合。顯然，T(G)和圖G中所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通子圖。按照8.1.2節(jié)的定義，它是連通圖的一棵生成樹，并且由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹；由廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹。2/5/202363數(shù)據(jù)結(jié)構(gòu)講義例如，圖8.17(a)和(b)所示分別為連通圖G5的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖中虛線為集合B(G)中的邊，實(shí)線為集合T(G)中的邊。2/5/202364數(shù)據(jù)結(jié)構(gòu)講義對(duì)于非連通圖，通過這樣的遍歷，將得到的是生成森林。例如，下圖所示為一個(gè)無向圖及其深度優(yōu)先生成森林，它由三棵深度優(yōu)先生成樹組成。2/5/202365數(shù)據(jù)結(jié)構(gòu)講義假設(shè)以孩子兄弟鏈表作生成森林的存儲(chǔ)結(jié)構(gòu)，則下面算法生成非連通圖的深度優(yōu)先生成森林。voidDFSForest(GraphG,CSTree*T)

/*建立無向圖G的深度優(yōu)先生成森林的孩子兄弟鏈表T。visited[]是全局變量。*/

{

T=NULL;for(v=0;v<G.vexnum;++v)

visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v])/*頂點(diǎn)v為新的生成樹的根結(jié)點(diǎn)*/{p=(CSTree)malloc(sixeof(CSNode));

/*分配根結(jié)點(diǎn)*/

p={GetVex(G,v).NULL,NULL};

/*給根結(jié)點(diǎn)賦值*/

if(!T)

(*T)=p;

/*T是第一棵生成樹的根*/

else

q->nextsibling=p;/*前一棵的根的兄弟是其它生成樹的根*/

q=p;

/*q指示當(dāng)前生成樹的根*/

DFSTree(G,v,&p);/*建立以p為根的生成樹*/}}2/5/202366數(shù)據(jù)結(jié)構(gòu)講義voidDFSTree(GraphG,intv,CSTree*T)/*從第v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立以*T為根的生成樹。*/{visited[v]=TRUE;first=TRUE;/*first用于標(biāo)記是否訪問了第一個(gè)孩子*/

for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w]){p=(CSTree)malloc(sizeof(CSNode));/*分配孩子結(jié)點(diǎn)*/*p={GetVex(G,w),NULL,NULL};if(first)/*w是v的第一個(gè)未被訪問的鄰接頂點(diǎn)，作為根的左孩子結(jié)點(diǎn)*/{T->lchild=p;first=FALSE;}else{/*w是v的其它未被訪問的鄰接頂點(diǎn)，作為上一鄰接頂點(diǎn)的右兄弟*/

q->nextsibling=p;}q=p;

DFSTree(G,w,&q);}}2/5/202367數(shù)據(jù)結(jié)構(gòu)講義8.4.4關(guān)節(jié)點(diǎn)和重連通分量假若在刪去頂點(diǎn)v以及和v相關(guān)聯(lián)的各邊之后，將圖的一個(gè)連通分量分割成兩個(gè)或兩個(gè)以上的連通分量，則稱頂點(diǎn)v為該圖的一個(gè)關(guān)節(jié)點(diǎn)。一個(gè)沒有關(guān)節(jié)點(diǎn)的連通圖稱為重連通圖。在重連通圖上，任意一對(duì)頂點(diǎn)之間至少存在兩條路徑，則在刪去某個(gè)頂點(diǎn)以及依附于該頂點(diǎn)的各邊時(shí)也不破壞圖的連通性。若在連通圖上至少刪去k個(gè)頂點(diǎn)才能破壞圖的連通性，則稱此圖的連通度為k。關(guān)節(jié)點(diǎn)和重連通圖在實(shí)際中較多應(yīng)用。顯然，一個(gè)表示通信網(wǎng)絡(luò)的圖的連通度越高，其系統(tǒng)越可靠，無論是哪一個(gè)站點(diǎn)出現(xiàn)故障或遭到外界破壞，都不影響系統(tǒng)的正常工作；又如，一個(gè)航空網(wǎng)若是重連通的，則當(dāng)某條航線因天氣等某種原因關(guān)閉時(shí)，旅客仍可從別的航線繞道而行；再如，若將大規(guī)模的集成電路的關(guān)鍵線路設(shè)計(jì)成重連通的話，則在某些元件失效的情況下，整個(gè)片子的功能不受影響，反之，在戰(zhàn)爭(zhēng)中，若要摧毀敵方的運(yùn)輸線，僅需破壞其運(yùn)輸網(wǎng)中的關(guān)節(jié)點(diǎn)即可。2/5/202368數(shù)據(jù)結(jié)構(gòu)講義例如，圖(a)中圖G7是連通圖，但不是重連通圖。圖中有四個(gè)關(guān)節(jié)點(diǎn)A、B和G。若刪去頂點(diǎn)B以及所有依附頂點(diǎn)B的邊，G7就被分割成三個(gè)連通分量{A、C、F、L、M、J}、{G、H、I、K}和{D、E}。類似地，若刪去頂點(diǎn)A或G以及所依附于它們的邊，則G7被分割成兩個(gè)連通分量，由此，關(guān)節(jié)點(diǎn)亦稱為割點(diǎn)。2/5/202369數(shù)據(jù)結(jié)構(gòu)講義利用深度優(yōu)先搜索便可求得圖的關(guān)節(jié)點(diǎn)，并由此可判別圖是否是重連通的。上圖(b)所示為從頂點(diǎn)A出發(fā)深優(yōu)先生成樹，圖中實(shí)線表示樹邊，虛線表示回邊（即不在生成樹上的邊）。對(duì)樹中任一頂點(diǎn)v而言，其孩子結(jié)點(diǎn)為在它之后搜索到的鄰接點(diǎn)，而其雙親結(jié)點(diǎn)和由回邊連接的祖先結(jié)點(diǎn)是在它之前搜索到的鄰接點(diǎn)。由深度優(yōu)先生成樹可得出兩類關(guān)節(jié)點(diǎn)的特性：⑴若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點(diǎn)必為關(guān)節(jié)點(diǎn)。因?yàn)閳D中不存在連接不同子樹中頂點(diǎn)的邊，因此，若刪去根頂點(diǎn)，生成樹便變成生成森林。⑵若生成樹中某個(gè)非葉子頂點(diǎn)v，其某棵子樹的根和子樹中的其它結(jié)點(diǎn)均沒有指向v的祖先的回邊，則v為關(guān)節(jié)點(diǎn)。因?yàn)椋魟h去v，則其子樹和圖的其它部分被分割開來。2/5/202370數(shù)據(jù)結(jié)構(gòu)講義若對(duì)圖Graph＝(V，{Edge})重新定義遍歷時(shí)的訪問函數(shù)visited，并引入一個(gè)新的函數(shù)low，則由一次深度優(yōu)先遍歷便可求得連通圖中存在的所有關(guān)節(jié)點(diǎn)。定義visited[v]為深度優(yōu)先搜索遍歷連通圖時(shí)訪問頂點(diǎn)v的次序號(hào)；定義：

w是v在DFS生成樹上的孩子結(jié)點(diǎn);

low(v)=Minvisited[v],low[w],visited[k]k是v在DFS生成樹上由回邊聯(lián)結(jié)的祖先結(jié)點(diǎn);(v,w)∈Edge;(v,k)∈Edge,

若對(duì)于某個(gè)頂點(diǎn)v，存在孩子結(jié)點(diǎn)w且low[w]≧visited[v]，則該頂點(diǎn)v必為關(guān)節(jié)點(diǎn)。因?yàn)楫?dāng)w是v的孩子結(jié)點(diǎn)時(shí)，low[w]≧visited[v]，表明w及其子孫均無指向v的祖先的回邊。2/5/202371數(shù)據(jù)結(jié)構(gòu)講義由定義可知，visited[v]值即為v在深度優(yōu)先生成樹的前序序列的序號(hào)，只需將DFS函數(shù)中頭兩個(gè)語句改為visited[v0]=++count（在DFSTraverse中設(shè)初值count=1）即可；low[v]可由后序遍歷深度優(yōu)先生成樹求得，而v在后序序列中的次序和遍歷時(shí)退出DFS函數(shù)的次序相同，由此修改深度優(yōu)先搜索遍歷的算法便可得到求關(guān)節(jié)點(diǎn)的算法。2/5/202372數(shù)據(jù)結(jié)構(gòu)講義voidFindArticul(ALGraphG)

/*連通圖G以鄰接表作存儲(chǔ)結(jié)構(gòu)，查找并輸出G上全部關(guān)節(jié)點(diǎn)*/{count=1;/*全局變量count用于對(duì)訪問計(jì)數(shù)*/

visited[0]=1;/*設(shè)定鄰接表上0號(hào)頂點(diǎn)為生成樹的根*/

for(i=1;i<G.vexnum;++i)/*其余頂點(diǎn)尚未訪問*/

visited[i]=0;p=G.adjlist[0].first;v=p->adjvex;DFSArticul(g,v);/*從頂點(diǎn)v出發(fā)深度優(yōu)先查找關(guān)節(jié)點(diǎn)*/if(count<G.vexnum)/*生成樹的根至少有兩棵子樹*/{printf(0,G.adjlist[0].vertex);/*根是關(guān)節(jié)點(diǎn)，輸出，是第一類關(guān)節(jié)點(diǎn)*/

while(p->next){p=p->next;v=p->adjvex;if(visited[v]==0)DFSArticul(g,v);}}}2/5/202373數(shù)據(jù)結(jié)構(gòu)講義voidDFSArticul(ALGraphG,intv0)/*從頂點(diǎn)v0出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)*/{visited[v0]=min=++count;/*v0是第count個(gè)訪問的頂點(diǎn)*/

for(p=G.adjlist[v0].firstedge;p;p=p->next;)/*對(duì)v0的每個(gè)鄰接點(diǎn)檢查*/{w=p->adjvex;/*w為v0的鄰接點(diǎn)*/

if(visited[w]==0)/*若w未曾訪問，則w為v0的孩子*/{DFSArticul(G,w);/*返回前求得low[w]*/if(low[w]<min)min=low[w];/*從w深入完成，要返回v0時(shí)，判定第二類關(guān)節(jié)點(diǎn)*/

if(low[w]>=visited[v0])printf(v0,G.adjlist[v0].vertex);/*輸出關(guān)節(jié)點(diǎn)*/}

elseif(visited[w]<min)min=visited[w];/*w已訪問，w是v0在生成樹上的祖先*/}low[v0]=min;}2/5/202374數(shù)據(jù)結(jié)構(gòu)講義例如，圖G7中各頂點(diǎn)計(jì)算所得visited和low的函數(shù)值如下所列：

i

012

34

56789101112G.adjlist[i].vertexABCDEFGHIJKLMvisited[i]

1512101113869472

3low[i]11155

1558251

1求得low值的順序13987612352141110其中J是第一個(gè)求得low值的頂點(diǎn)，由于存在回邊（J,L），則low[J]=Min{visited[J]、visited[L]}=2。順便提一句，上述算法中將指向雙親的樹邊也看成是回邊，由于不影響關(guān)節(jié)點(diǎn)的判別，因此，為使算法簡(jiǎn)明起見，在算法中沒有區(qū)別之。由于上述算法的過程就是一個(gè)遍歷的過程，因此，求關(guān)節(jié)點(diǎn)的時(shí)間復(fù)雜度仍為O（n+e）。2/5/202375數(shù)據(jù)結(jié)構(gòu)講義8.5最小生成樹最小生成樹的基本概念構(gòu)造最小生成樹的Prim算法構(gòu)造最小生成樹的Kruskal算法2/5/202376數(shù)據(jù)結(jié)構(gòu)講義8.5.1最小生成樹的基本概念由生成樹的定義可知，無向連通圖的生成樹不是唯一的。連通圖的一次遍歷所經(jīng)過的向前邊的集合及圖中所有頂點(diǎn)的集合就構(gòu)成了該圖的一棵生成樹，對(duì)連通圖的不同遍歷，如遍歷出發(fā)點(diǎn)不同或存儲(chǔ)點(diǎn)的順序不同，就可能得到不同的生成樹。下圖(a)、(b)和(c)所示的均為無向連通圖G5的生成樹。2/5/202377數(shù)據(jù)結(jié)構(gòu)講義可以證明，對(duì)于有n個(gè)頂點(diǎn)的無向連通圖，無論其生成樹的形態(tài)如何，所有生成樹中都有且僅有n－1條邊。如果無向連通圖是一個(gè)網(wǎng)，那么，它的所有生成樹中必有一棵邊的權(quán)值總和最小的生成樹，我們稱這棵生成樹為最小生成樹，簡(jiǎn)稱為最小生成樹。最小生成樹的概念可以應(yīng)用到許多實(shí)際問題中。例如有這樣一個(gè)問題：以盡可能抵的總造價(jià)建造城市間的通訊網(wǎng)絡(luò)，把十個(gè)城市聯(lián)系在一起。在這十個(gè)城市中，任意兩個(gè)城市之間都可以建造通訊線路，通訊線路的造價(jià)依據(jù)