數(shù)據(jù)結(jié)構(gòu)(第8章)-清華大學(xué)

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

12學(xué)時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)是由非空的頂點集合和一個描述頂點之間關(guān)系——邊（或者弧）的集合組成，其形式化定義為：

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

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

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

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

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

⑷無向完全圖。在一個無向圖中，如果任意兩頂點都有一條直接邊相連接，則稱該圖為無向完全圖?？梢宰C明，在一個含有n個頂點的無向完全圖中，有n(n-1)/2條邊。

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

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

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

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

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

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

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

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

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

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

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

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

A[i][j]=

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

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

typedefcharVertexType;

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

typedefintEdgeType;

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

typedefstruct{VertexTypevexs[MaxVertexNum];/*頂點表*/

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

intn,e;

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

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

voidCreateMGraph(MGraph*G)

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

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

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

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("請輸入每條邊對應(yīng)的兩個頂點的序號(輸入格式為: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;，則為無向圖的鄰接矩陣存儲建立*/}}2/5/202319數(shù)據(jù)結(jié)構(gòu)講義8.2.2鄰接表鄰接表(AdjacencyList)是圖的一種順序存儲與鏈式存儲結(jié)合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖G中的每個頂點vi，將所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表，再將所有點的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。2/5/202320數(shù)據(jù)結(jié)構(gòu)講義在鄰接表表示中有兩種結(jié)點結(jié)構(gòu)，如下圖所示。

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

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

intadjvex;/*鄰接點域*/

structnode*next;/*指向下一個鄰接點的指針域*/

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

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

VertexTypevertex;/*頂點域*/

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

typedefVertexNodeAdjList[MaxVertexNum];

/*AdjList是鄰接表類型*/

typedefstruct{

AdjListadjlist;/*鄰接表*/

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

voidCreateALGraph(ALGraph*G)

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

printf("請輸入頂點信息(輸入格式為:頂點號<CR>)：\n");for(i=0;i<G->n;i++)/*建立有n個頂點的頂點表*/

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

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

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

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

/*讀入邊<Vi,Vj>的頂點對應(yīng)序號*/

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

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

s->adjvex=j;/*鄰接點序號為j*/

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

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

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

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

/*該弧的尾和頭頂點的位置*/

structArcBox*hlink,*tlink;

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

InfoTypeinfo;

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

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

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

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

scanf(&(G->xlist[i].vertex));/*輸入頂點值*/*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);

/*輸入一條弧的始點和終點*/

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

/*訪問標記*/

intivex,jvex;

/*該邊依附的兩個頂點的位置*/

structEBoxilink,jlink;/*分別指向依附這兩個頂點的下一條邊*/

InfoTypeinfo;

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

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

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

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

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

voidDFSTraverseAL(ALGraph*G)

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

{inti;

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

visited[i]=FALSE;/*標志向量初始化*/

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ā)點對鄰接表存儲的圖G進行DFS搜索*/{EdgeNode*p;printf("visitvertex:V%c\n",G->adjlist[i].vertex);

/*訪問頂點Vi*/

visited[i]=TRUE;/*標記Vi已訪問*/

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

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

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

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

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

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

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

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

while(!QueueEmpty(Q)){DeQueue(Q,u);/*隊頭元素出隊并置為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的尚未訪問的鄰接頂點w入隊列Q*/

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

voidBFSTraverseAL(MGraph*G)

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

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

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ā)點，對鄰接矩陣存儲的圖G進行BFS搜索*/{inti,j;CirQueueQ;InitQueue(&Q);printf("visitvertex:V%c\n",G->vexs[k]);/*訪問原點Vk*/visited[k]=TRUE;EnQueue(&Q,k);/*原點Vk入隊列*/

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

for(j=0;j<G->n;j++)/*依次搜索Vi的鄰接點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入隊列*/}}

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

ABFE

CE

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

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

在這一小節(jié)里，我們將給出通過對圖的遍歷，得到圖的生成樹或生成森林的算法。設(shè)E(G)為連通圖G中所有邊的集合，則從圖中任一頂點出發(fā)遍歷圖時，必定將E(G)分成兩個集合T(G)和B(G)，其中T(G)是遍歷圖過程中歷經(jīng)的邊的集合；B(G)是剩余的邊的集合。顯然，T(G)和圖G中所有頂點一起構(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)中的邊，實線為集合T(G)中的邊。2/5/202364數(shù)據(jù)結(jié)構(gòu)講義對于非連通圖，通過這樣的遍歷，將得到的是生成森林。例如，下圖所示為一個無向圖及其深度優(yōu)先生成森林，它由三棵深度優(yōu)先生成樹組成。2/5/202365數(shù)據(jù)結(jié)構(gòu)講義假設(shè)以孩子兄弟鏈表作生成森林的存儲結(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])/*頂點v為新的生成樹的根結(jié)點*/{p=(CSTree)malloc(sixeof(CSNode));

/*分配根結(jié)點*/

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

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

if(!T)

(*T)=p;

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

else

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

q=p;

/*q指示當前生成樹的根*/

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

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

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

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

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

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

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

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

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

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

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

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)/*從頂點v0出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點*/{visited[v0]=min=++count;/*v0是第count個訪問的頂點*/

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

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

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

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

i

012

34

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

1512101113869472

3low[i]11155

1558251

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