數(shù)據(jù)結構和原理

第7

圖(Graph)是一種比線性表和樹更為復雜的數(shù)據(jù)結構。線性結構：是研究數(shù)據(jù)元素之間的一對一關系。在這種結構中，除第一個和最后一個元素外，任何一個元素都有唯一的一個直接前驅和直接后繼。樹結構：是研究數(shù)據(jù)元素之間的一對多的關系。在這種結構中，每個元素對下(層)可以有0個或多個元素相聯(lián)系，對上(層)只有唯一的一個元素相關，數(shù)據(jù)元素之間有明顯的層次關系。數(shù)據(jù)結構和原理全文共152頁，當前為第1頁。

圖結構：是研究數(shù)據(jù)元素之間的多對多的關系。在這種結構中，任意兩個元素之間可能存在關系。即結點之間的關系可以是任意的，圖中任意元素之間都可能相關。圖的應用極為廣泛，已滲入到諸如語言學、邏輯學、物理、化學、電訊、計算機科學以及數(shù)學的其它分支。數(shù)據(jù)結構和原理全文共152頁，當前為第2頁。7.1

圖的基本概念7.1.1圖的定義和術語

一個圖(G)定義為一個偶對(V,E)，記為G=(V,E)。其中：V是頂點(Vertex)的非空有限集合，記為V(G)；E是無序集V&V的一個子集，記為E(G)，其元素是圖的弧(Arc)。將頂點集合為空的圖稱為空圖。其形式化定義為：G=(V，E)V={v|vdataobject}E={<v,w>|v,wV∧p(v,w)}P(v,w)表示從頂點v到頂點w有一條直接通路。數(shù)據(jù)結構和原理全文共152頁，當前為第3頁。弧(Arc)

：表示兩個頂點v和w之間存在一個關系，用頂點偶對<v,w>表示。通常根據(jù)圖的頂點偶對將圖分為有向圖和無向圖。有向圖(Digraph)：若圖G的關系集合E(G)中，頂點偶對<v,w>的v和w之間是有序的，稱圖G是有向圖。在有向圖中，若<v,w>E(G)，表示從頂點v到頂點w有一條弧。其中：v稱為弧尾(tail)或始點(initialnode)，w稱為弧頭(head)或終點(terminalnode)。無向圖(Undigraph)：若圖G的關系集合E(G)中，頂點偶對<v,w>的v和w之間是無序的，稱圖G是無向圖。數(shù)據(jù)結構和原理全文共152頁，當前為第4頁。在無向圖中，若<v,w>E(G)，有<w,v>E(G)，即E(G)是對稱，則用無序對(v,w)表示v和w之間的一條邊(Edge)，因此(v,w)和(w,v)代表的是同一條邊。例1：設有有向圖G1和無向圖G2，形式化定義分別是：G1=(V1，E1)V1={a,b,c,d,e}E1={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>}G2=(V2，E2)V2={a,b,c,d}E2={(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)}它們所對應的圖如圖7-1所示。數(shù)據(jù)結構和原理全文共152頁，當前為第5頁。

完全無向圖：對于無向圖，若圖中頂點數(shù)為n，用e表示邊的數(shù)目，則e[0，n(n-1)/2]。具有n(n-1)/2條邊的無向圖稱為完全無向圖。完全無向圖另外的定義是：對于無向圖G=(V，E)，若vi，vj

V，當vi≠vj時，有(vi,vj)E，即圖中任意兩個不同的頂點間都有一條無向邊，這樣的無向圖稱為完全無向圖。abcd(b)無向圖G2

圖7-1圖的示例(a)有向圖G1

acbde數(shù)據(jù)結構和原理全文共152頁，當前為第6頁。完全有向圖：對于有向圖，若圖中頂點數(shù)為n，用e表示弧的數(shù)目，則e[0，n(n-1)]。具有n(n-1)條邊的有向圖稱為完全有向圖。完全有向圖另外的定義是：對于有向圖G=(V，E)，若vi，vjV，當vi≠vj時，有<vi,vj>E∧<vj,

vi>E，即圖中任意兩個不同的頂點間都有一條弧，這樣的有向圖稱為完全有向圖。有很少邊或弧的圖（e<n㏒n）的圖稱為稀疏圖，反之稱為稠密圖。權(Weight)：與圖的邊和弧相關的數(shù)。權可以表示從一個頂點到另一個頂點的距離或耗費。數(shù)據(jù)結構和原理全文共152頁，當前為第7頁。子圖和生成子圖：設有圖G=(V，E)和G’=(V’，E’)，若V’V且E’E，則稱圖G’是G的子圖；若V’=V且E’E，則稱圖G’是G的一個生成子圖。頂點的鄰接(Adjacent)：對于無向圖G=(V，E)，若邊(v,w)E，則稱頂點v和w互為鄰接點，即v和w相鄰接。邊(v,w)依附(incident)與頂點v和w。對于有向圖G=(V，E)，若有向弧<v,w>E，則稱頂點v“鄰接到”頂點w，頂點w“鄰接自”頂點v，弧<v,w>與頂點v和w“相關聯(lián)”。頂點的度、入度、出度：對于無向圖G=(V，E)，viV，圖G中依附于vi的邊的數(shù)目稱為頂點vi的度(degree)，記為TD(vi)。數(shù)據(jù)結構和原理全文共152頁，當前為第8頁。

顯然，在無向圖中，所有頂點度的和是圖中邊的2倍。即∑TD(vi)=2ei=1,2,…,n，e為圖的邊數(shù)。對有向圖G=(V，E)，若viV，圖G中以vi作為起點的有向邊(弧)的數(shù)目稱為頂點vi的出度(Outdegree)，記為OD(vi)；以vi作為終點的有向邊(弧)的數(shù)目稱為頂點vi的入度(Indegree)，記為ID(vi)。頂點vi的出度與入度之和稱為vi的度，記為TD(vi)。即TD(vi)=OD(vi)+ID(vi)

路徑(Path)、路徑長度、回路(Cycle)：對無向圖G=(V，E)，若從頂點vi經(jīng)過若干條邊能到達vj，稱頂點vi和vj是連通的，又稱頂點vi到vj有路徑。對有向圖G=(V，E)，從頂點vi到vj有有向路徑，指的是從頂點vi經(jīng)過若干條有向邊(弧)能到達vj。數(shù)據(jù)結構和原理全文共152頁，當前為第9頁?；蚵窂绞菆DG中連接兩頂點之間所經(jīng)過的頂點序列。即Path=vi0vi1…vim，vijV且(vij-1,vij)Ej=1,2,…,m或Path=vi0vi1…vim，vijV且<vij-1,vij>Ej=1,2,…,m

路徑上邊或有向邊(弧)的數(shù)目稱為該路徑的長度。在一條路徑中，若沒有重復相同的頂點，該路徑稱為簡單路徑；第一個頂點和最后一個頂點相同的路徑稱為回路(環(huán))；在一個回路中，若除第一個與最后一個頂點外，其余頂點不重復出現(xiàn)的回路稱為簡單回路(簡單環(huán))。數(shù)據(jù)結構和原理全文共152頁，當前為第10頁。連通圖、圖的連通分量：對無向圖G=(V，E)，若vi，vjV，vi和vj都是連通的，則稱圖G是連通圖，否則稱為非連通圖。若G是非連通圖，則極大的連通子圖稱為G的連通分量。對有向圖G=(V，E)，若vi，vjV，都有以vi為起點，vj

為終點以及以vj為起點，vi為終點的有向路徑，稱圖G是強連通圖，否則稱為非強連通圖。若G是非強連通圖，則極大的強連通子圖稱為G的強連通分量。

“極大”的含義：指的是對子圖再增加圖G中的其它頂點，子圖就不再連通。數(shù)據(jù)結構和原理全文共152頁，當前為第11頁。生成樹、生成森林：一個連通圖(無向圖)的生成樹是一個極小連通子圖，它含有圖中全部n個頂點和只有足以構成一棵樹的n-1條邊，稱為圖的生成樹，如圖7-2所示。關于無向圖的生成樹的幾個結論：

◆一棵有n個頂點的生成樹有且僅有n-1條邊；

◆如果一個圖有n個頂點和小于n-1條邊，則是非連通圖；adbc圖7-2圖G2的一棵生成樹◆如果多于n-1條邊，則一定有環(huán)；

◆有n-1條邊的圖不一定是生成樹。數(shù)據(jù)結構和原理全文共152頁，當前為第12頁。

有向圖的生成森林是這樣一個子圖，由若干棵有向樹組成，含有圖中全部頂點。有向樹是只有一個頂點的入度為0，其余頂點的入度均為1的有向圖，如圖7-3所示。網(wǎng)：每個邊(或弧)都附加一個權值的圖，稱為帶權圖。帶權的連通圖(包括弱連通的有向圖)稱為網(wǎng)或網(wǎng)絡。網(wǎng)絡是工程上常用的一個概念，用來表示一個工程或某種流程，如圖7-4所示。圖7-3有向圖及其生成森林abcdedce(a)有向圖(b)生成森林acbcb354126abcde3圖7-4帶權有向圖數(shù)據(jù)結構和原理全文共152頁，當前為第13頁。7.1.2

圖的抽象數(shù)據(jù)類型定義

圖是一種數(shù)據(jù)結構，加上一組基本操作就構成了圖的抽象數(shù)據(jù)類型。圖的抽象數(shù)據(jù)類型定義如下：ADTGraph{數(shù)據(jù)對象V：具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關系R：R={VR}VR={<v,w>|<v,w>|v,wV∧p(v,w)，<v,w>表示從v到w的弧，P(v,w)定義了弧<v,w>的信息}數(shù)據(jù)結構和原理全文共152頁，當前為第14頁?；静僮鱌：Create_Graph()：圖的創(chuàng)建操作。初始條件：無。操作結果：生成一個沒有頂點的空圖G。GetVex(G,v)：求圖中的頂點v的值。初始條件：圖G存在，v是圖中的一個頂點。操作結果：生成一個沒有頂點的空圖G。

…

…DFStraver(G,V)：從v出發(fā)對圖G深度優(yōu)先遍歷。初始條件：圖G存在。操作結果：對圖G深度優(yōu)先遍歷，每個頂點訪問且只訪問一次。數(shù)據(jù)結構和原理全文共152頁，當前為第15頁。??BFStraver(G,V)：從v出發(fā)對圖G廣度優(yōu)先遍歷。初始條件：圖G存在。操作結果：對圖G廣度優(yōu)先遍歷，每個頂點訪問且只訪問一次。}ADTGraph詳見p156~157。數(shù)據(jù)結構和原理全文共152頁，當前為第16頁。7.2

圖的存儲結構

圖的存儲結構比較復雜，其復雜性主要表現(xiàn)在：◆任意頂點之間可能存在聯(lián)系，無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關系?！魣D中頂點的度不一樣，有的可能相差很大，若按度數(shù)最大的頂點設計結構，則會浪費很多存儲單元，反之按每個頂點自己的度設計不同的結構，又會影響操作。圖的常用的存儲結構有：鄰接矩陣、鄰接鏈表、十字鏈表、鄰接多重表和邊表。數(shù)據(jù)結構和原理全文共152頁，當前為第17頁。7.2.1鄰接矩陣(數(shù)組)表示法基本思想：對于有n個頂點的圖，用一維數(shù)組vexs[n]存儲頂點信息，用二維數(shù)組A[n][n]存儲頂點之間關系的信息。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點在vexs數(shù)組中的下標代表頂點，鄰接矩陣中的元素A[i][j]存放的是頂點i到頂點j之間關系的信息。數(shù)據(jù)結構和原理全文共152頁，當前為第18頁。1無向圖的數(shù)組表示(1)無權圖的鄰接矩陣

無向無權圖G=(V，E)有n(n≧1)個頂點，其鄰接矩陣是n階對稱方陣，如圖7-5所示。其元素的定義如下：1若(vi,vj)E，即vi,vj鄰接0若(vi,vj)E，即vi,vj不鄰接A[i][j]=(a)無向圖

abcd圖7-5無向無權圖的數(shù)組存儲(b)頂點矩陣vexsabcd0111101111011110(c)鄰接矩陣數(shù)據(jù)結構和原理全文共152頁，當前為第19頁。(2)帶權圖的鄰接矩陣

無向帶權圖G=(V，E)的鄰接矩陣如圖7-6所示。其元素的定義如下：(a)帶權無向圖

(b)頂點矩陣圖7-6無向帶權圖的數(shù)組存儲(c)鄰接矩陣354126abcde3vexsabcde∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞Wij

若(vi,vj)E，即vi,vj鄰接，權值為wij∞若(vi,vj)E，即vi,vj不鄰接時A[i][j]=數(shù)據(jù)結構和原理全文共152頁，當前為第20頁。(3)無向圖鄰接矩陣的特性◆鄰接矩陣是對稱方陣；

◆

對于頂點vi，其度數(shù)是第i行的非0元素的個數(shù)；

◆

無向圖的邊數(shù)是上(或下)三角形矩陣中非0元素個數(shù)。2有向圖的數(shù)組表示(1)無權圖的鄰接矩陣

若有向無權圖G=(V，E)有n(n≧1)個頂點，則其鄰接矩陣是n階對稱方陣，如圖7-7所示。元素定義如下：1若<vi,vj>E，從vi到vj有弧A[i][j]=0若<vi,vj>E從vi到vj沒有弧數(shù)據(jù)結構和原理全文共152頁，當前為第21頁。(a)有向圖acbde圖7-7有向無權圖的數(shù)組存儲(b)頂點矩陣vexsabcde(c)鄰接矩陣0110100000000111100000010(2)帶權圖的鄰接矩陣

有向帶權圖G=(V，E)的鄰接矩陣如圖7-8所示。其元素的定義如下：wij

若<vi,vj>E，即vi,vj鄰接，權值為wij∞若<vi,vj>E，即vi,vj不鄰接時A[i][j]=數(shù)據(jù)結構和原理全文共152頁，當前為第22頁。圖7-8帶權有向圖的數(shù)組存儲(b)頂點矩陣vexsabcde(c)鄰接矩陣∞62∞∞∞∞

∞

∞

3∞

3∞1∞∞4

∞∞5∞∞

∞∞∞(a)帶權有向圖

354126abcde3⑶有向圖鄰接矩陣的特性◆對于頂點vi，第i行的非0元素的個數(shù)是其出度OD(vi)；第i列的非0元素的個數(shù)是其入度ID(vi)?！?/p>

鄰接矩陣中非0元素的個數(shù)就是圖的弧的數(shù)目。數(shù)據(jù)結構和原理全文共152頁，當前為第23頁。3圖的鄰接矩陣的操作

圖的鄰接矩陣的實現(xiàn)比較容易，定義兩個數(shù)組分別存儲頂點信息(數(shù)據(jù)元素)和邊或弧的信息(數(shù)據(jù)元素之間的關系)。其存儲結構形式定義如下：#defineINFINITYMAX_VAL/*最大值∞*//*根據(jù)圖的權值類型，分別定義為最大整數(shù)或實數(shù)*/#defineMAX_VEX30/*最大頂點數(shù)目*/typedefenum{DG,AG,WDG,WAG}GraphKind;/*{有向圖，無向圖，帶權有向圖，帶權無向圖}*/數(shù)據(jù)結構和原理全文共152頁，當前為第24頁。typedefstructArcType{VexTypevex1,vex2;/*弧或邊所依附的兩個頂點*/ArcValTypeArcVal;/*弧或邊的權值*/ArcInfoTypeArcInfo;/*弧或邊的其它信息*/}ArcType;/*弧或邊的結構定義*/typedefstruct{GraphKindkind;/*圖的種類標志*/intvexnum,arcnum;/*圖的當前頂點數(shù)和弧數(shù)*/VexTypevexs[MAX_VEX];/*頂點向量*/AdjTypeadj[MAX_VEX][MAX_VEX];}MGraph;/*圖的結構定義*/數(shù)據(jù)結構和原理全文共152頁，當前為第25頁。利用上述定義的數(shù)據(jù)結構，可以方便地實現(xiàn)圖的各種操作。(1)圖的創(chuàng)建AdjGraph*Create_Graph(MGraph*G){printf(“請輸入圖的種類標志：”);scanf(“%d”,&G->kind);G->vexnum=0;/*初始化頂點個數(shù)*/return(G);}數(shù)據(jù)結構和原理全文共152頁，當前為第26頁。(2)圖的頂點定位圖的頂點定位操作實際上是確定一個頂點在vexs數(shù)組中的位置(下標)，其過程完全等同于在順序存儲的線性表中查找一個數(shù)據(jù)元素。算法實現(xiàn)：intLocateVex(MGraph*G,VexType*vp){intk;for(k=0;k<G->vexnum;k++)if(G->vexs[k]==*vp)return(k);return(-1);/*圖中無此頂點*/}數(shù)據(jù)結構和原理全文共152頁，當前為第27頁。(3)向圖中增加頂點向圖中增加一個頂點的操作，類似在順序存儲的線性表的末尾增加一個數(shù)據(jù)元素。算法實現(xiàn)：intAddVertex(MGraph*G,VexType*vp){intk,j;if(G->vexnum>=MAX_VEX){printf(“VertexOverflow!\n”);return(-1);}if(LocateVex(G,vp)!=-1){printf(“Vertexhasexisted!\n”);return(-1);}k=G->vexnum;G->vexs[G->vexnum++]=*vp;數(shù)據(jù)結構和原理全文共152頁，當前為第28頁。if(G->kind==DG||G->kind==AG)for(j=0;j<G->vexnum;j++)G->adj[j][k].ArcVal=G->adj[k][j].ArcVal=0;

/*是不帶權的有向圖或無向圖*/elsefor(j=0;j<G->vexnum;j++){G->adj[j][k].ArcVal=INFINITY;G->adj[k][j].ArcVal=INFINITY;

/*是帶權的有向圖或無向圖*/}return(k);}數(shù)據(jù)結構和原理全文共152頁，當前為第29頁。(4)向圖中增加一條弧根據(jù)給定的弧或邊所依附的頂點，修改鄰接矩陣中所對應的數(shù)組元素。算法實現(xiàn)：

intAddArc(MGraph*G,ArcType*arc){intk,j;k=LocateVex(G,&arc->vex1);j=LocateVex(G,&arc->vex1);if(k==-1||j==-1){printf(“Arc’sVertexdonotexisted!\n”);return(-1);}數(shù)據(jù)結構和原理全文共152頁，當前為第30頁。if(G->kind==DG||G->kind==WDG){G->adj[k][j].ArcVal=arc->ArcVal;G->adj[k][j].ArcInfo=arc->ArcInfo;

/*是有向圖或帶權的有向圖*/}else{G->adj[k][j].ArcVal=arc->ArcVal;G->adj[j][k].ArcVal=arc->ArcVal;G->adj[k][j].ArcInfo=arc->ArcInfo;G->adj[j][k].ArcInfo=arc->ArcInfo;

/*是無向圖或帶權的無向圖,需對稱賦值*/}return(1);}數(shù)據(jù)結構和原理全文共152頁，當前為第31頁。7.2.2

鄰接鏈表法

基本思想：對圖的每個頂點建立一個單鏈表，存儲該頂點所有鄰接頂點及其相關信息。每一個單鏈表設一個表頭結點。第i個單鏈表表示依附于頂點Vi的邊(對有向圖是以頂點Vi為頭或尾的弧)。數(shù)據(jù)結構和原理全文共152頁，當前為第32頁。1結點結構與鄰接鏈表示例

鏈表中的結點稱為表結點，每個結點由三個域組成，如圖7-9(a)所示。其中鄰接點域(adjvex)指示與頂點Vi鄰接的頂點在圖中的位置(頂點編號)，鏈域(nextarc)指向下一個與頂點Vi鄰接的表結點，數(shù)據(jù)域(info)存儲和邊或弧相關的信息，如權值等。對于無權圖，如果沒有與邊相關的其他信息，可省略此域。每個鏈表設一個表頭結點(稱為頂點結點)，由兩個域組成，如圖7-9(b)所示。鏈域(firstarc)指向鏈表中的第一個結點，數(shù)據(jù)域(data)存儲頂點名或其他信息。adjvexinfonextarc表結點：datafirstarc頂點結點：圖7-9鄰接鏈表結點結構數(shù)據(jù)結構和原理全文共152頁，當前為第33頁。在圖的鄰接鏈表表示中，所有頂點結點用一個向量以順序結構形式存儲，可以隨機訪問任意頂點的鏈表，該向量稱為表頭向量，向量的下標指示頂點的序號。用鄰接鏈表存儲圖時，對無向圖，其鄰接鏈表是唯一的，如圖7-10所示；對有向圖，其鄰接鏈表有兩種形式，如圖7-11所示。圖7-10無向圖及其鄰接鏈表v1v2v3v4v501234MAX_VEX-1v1

v2v3

v4┇┇v5

213?02?0314?204?23?數(shù)據(jù)結構和原理全文共152頁，當前為第34頁。(a)有向圖v1v2v3v4v513?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51(b)正鄰接鏈表，出度直觀2?02?2?01234MAX_VEX-1v11v22v31v42┇┇┇v513?04?(c)逆鄰接鏈表，入度直觀圖7-11有向圖及其鄰接鏈表數(shù)據(jù)結構和原理全文共152頁，當前為第35頁。2鄰接表法的特點

◆表頭向量中每個分量就是一個單鏈表的頭結點，分量個數(shù)就是圖中的頂點數(shù)目；

◆在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間；

◆在無向圖，頂點Vi的度是第i個鏈表的結點數(shù)；◆對有向圖可以建立正鄰接表或逆鄰接表。正鄰接表是以頂點Vi為出度(即為弧的起點)而建立的鄰接表；逆鄰接表是以頂點Vi為入度(即為弧的終點)而建立的鄰接表；◆在有向圖中，第i個鏈表中的結點數(shù)是頂點Vi的出(或入)度；求入(或出)度，須遍歷整個鄰接表；數(shù)據(jù)結構和原理全文共152頁，當前為第36頁。◆在鄰接表上容易找出任一頂點的第一個鄰接點和下一個鄰接點；3結點及其類型定義#defineMAX_VEX30/*最大頂點數(shù)*/typedefintInfoType;typedefenum{DG,AG,WDG,WAG}GraphKind;typedefstructLinkNode{intadjvex;//鄰接點在頭結點數(shù)組中的位置(下標)InfoTypeinfo;//與邊或弧相關的信息,如權值structLinkNode*nextarc;//指向下一個表結點}LinkNode;/*表結點類型定義*/數(shù)據(jù)結構和原理全文共152頁，當前為第37頁。typedefstructVexNode{VexTypedata;//頂點信息intindegree;//頂點的度,有向圖是入度或出度或沒有LinkNode*firstarc;//指向第一個表結點}VexNode;/*頂點結點類型定義*/typedefstructArcType{VexTypevex1,vex2;/*弧或邊所依附的兩個頂點*/InfoTypeinfo;//與邊或弧相關的信息,如權值}ArcType;/*弧或邊的結構定義*/數(shù)據(jù)結構和原理全文共152頁，當前為第38頁。typedefstruct{GraphKindkind;/*圖的種類標志*/intvexnum;VexNodeAdjList[MAX_VEX];}ALGraph;/*圖的結構定義*/數(shù)據(jù)結構和原理全文共152頁，當前為第39頁。利用上述的存儲結構描述，可方便地實現(xiàn)圖的基本操作。(1)圖的創(chuàng)建ALGraph*Create_Graph(ALGraph*G){printf(“請輸入圖的種類標志：”);scanf(“%d”,&G->kind);G->vexnum=0;/*初始化頂點個數(shù)*/return(G);}數(shù)據(jù)結構和原理全文共152頁，當前為第40頁。(2)圖的頂點定位圖的頂點定位實際上是確定一個頂點在AdjList數(shù)組中的某個元素的data域內容。算法實現(xiàn)：intLocateVex(ALGraph*G,VexType*vp){intk;for(k=0;k<G->vexnum;k++)if(G->AdjList[k].data==*vp)return(k);return(-1);/*圖中無此頂點*/}數(shù)據(jù)結構和原理全文共152頁，當前為第41頁。(3)向圖中增加頂點

向圖中增加一個頂點的操作，在AdjList數(shù)組的末尾增加一個數(shù)據(jù)元素。算法實現(xiàn)：intAddVertex(ALGraph*G,VexType*vp){intk,j;if(G->vexnum>=MAX_VEX){printf(“VertexOverflow!\n”);return(-1);}if(LocateVex(G,vp)!=-1){printf(“Vertexhasexisted!\n”);return(-1);}G->AdjList[G->vexnum].data=*vp;數(shù)據(jù)結構和原理全文共152頁，當前為第42頁。G->AdjList[G->vexnum].degree=0;G->AdjList[G->vexnum].firstarc=NULL;k=++G->vexnum;return(k);}(4)向圖中增加一條弧

根據(jù)給定的弧或邊所依附的頂點，修改單鏈表：無向圖修改兩個單鏈表；有向圖修改一個單鏈表。算法實現(xiàn)：intAddArc(ALGraph*G,ArcType*arc){intk,j;LinkNode*p,*q;數(shù)據(jù)結構和原理全文共152頁，當前為第43頁。k=LocateVex(G,&arc->vex1);j=LocateVex(G,&arc->vex2);if(k==-1||j==-1){printf(“Arc’sVertexdonotexisted!\n”);return(-1);}p=(LinkNode*)malloc(sizeof(LinkNode));p->adjvex=arc->vex1;p->info=arc->info;p->nextarc=NULL;/*邊的起始表結點賦值*/q=(LinkNode*)malloc(sizeof(LinkNode));q->adjvex=arc->vex2;q->info=arc->info;q->nextarc=NULL;/*邊的末尾表結點賦值*/數(shù)據(jù)結構和原理全文共152頁，當前為第44頁。if(G->kind==AG||G->kind==WAG){q->nextarc=G->adjlist[k].firstarc;G->adjlist[k].firstarc=q;p->nextarc=G->adjlist[j].firstarc;G->adjlist[j].firstarc=p;}/*是無向圖,用頭插入法插入到兩個單鏈表*/else/*建立有向圖的鄰接鏈表,用頭插入法*/{q->nextarc=G->adjlist[k].firstarc;G->adjlist[k].firstarc=q;/*建立正鄰接鏈表用*///q->nextarc=G->adjlist[j].firstarc;//G->adjlist[j].firstarc=q;/*建立逆鄰接鏈表用*/}return(1);}數(shù)據(jù)結構和原理全文共152頁，當前為第45頁。7.2.3

十字鏈表法十字鏈表(OrthogonalList)是有向圖的另一種鏈式存儲結構，是將有向圖的正鄰接表和逆鄰接表結合起來得到的一種鏈表。在這種結構中，每條弧的弧頭結點和弧尾結點都存放在鏈表中，并將弧結點分別組織到以弧尾結點為頭(頂點)結點和以弧頭結點為頭(頂點)結點的鏈表中。這種結構的結點邏輯結構如圖7-12所示?；〗Y點tailvexheadvexinfohlinktlink頂點結點Datafirstinfirstout圖7-12十字鏈表結點結構數(shù)據(jù)結構和原理全文共152頁，當前為第46頁?！?/p>

data域：存儲和頂點相關的信息；◆指針域firstin：指向以該頂點為弧頭的第一條弧所對應的弧結點；◆指針域firstout：指向以該頂點為弧尾的第一條弧所對應的弧結點；◆尾域tailvex：指示弧尾頂點在圖中的位置；◆頭域headvex：指示弧頭頂點在圖中的位置；◆指針域hlink：指向弧頭相同的下一條??；◆指針域tlink：指向弧尾相同的下一條??；◆Info域：指向該弧的相關信息；數(shù)據(jù)結構和原理全文共152頁，當前為第47頁。結點類型定義#defineINFINITYMAX_VAL/*最大值∞*/#defineMAX_VEX30//

最大頂點數(shù)typedefstructArcNode{inttailvex,headvex;//尾結點和頭結點在圖中的位置InfoTypeinfo;//與弧相關的信息,如權值structArcNode*hlink,*tlink;}ArcNode;/*弧結點類型定義*/typedefstructVexNode{VexTypedata;//頂點信息ArcNode*firstin,*firstout;}VexNode;/*頂點結點類型定義*/數(shù)據(jù)結構和原理全文共152頁，當前為第48頁。typedefstruct{intvexnum;VexNodexlist[MAX_VEX];}OLGraph;/*圖的類型定義*/

圖7-13所示是一個有向圖及其十字鏈表(略去了表結點的info域)。從這種存儲結構圖可以看出，從一個頂點結點的firstout出發(fā)，沿表結點的tlink指針構成了正鄰接表的鏈表結構，而從一個頂點結點的firstin出發(fā)，沿表結點的hlink指針構成了逆鄰接表的鏈表結構。數(shù)據(jù)結構和原理全文共152頁，當前為第49頁。V0V1V2V30102∧2023∧∧30∧31∧32∧∧0213V0V1∧V2V3圖7-13有向圖的十字鏈表結構數(shù)據(jù)結構和原理全文共152頁，當前為第50頁。7.2.4

鄰接多重表鄰接多重表(AdjacencyMultilist)是無向圖的另一種鏈式存儲結構。鄰接表是無向圖的一種有效的存儲結構，在無向圖的鄰接表中，一條邊(v,w)的兩個表結點分別初選在以v和w為頭結點的鏈表中，很容易求得頂點和邊的信息，但在涉及到邊的操作會帶來不便。鄰接多重表的結構和十字鏈表類似，每條邊用一個結點表示；鄰接多重表中的頂點結點結構與鄰接表中的完全相同，而表結點包括六個域如圖7-14所示。datafirstedge頂點結點圖7-14鄰接多重表的結點結構表結點markivexjvexinfoilinkjlink數(shù)據(jù)結構和原理全文共152頁，當前為第51頁?！?/p>

Data域：存儲和頂點相關的信息；◆指針域firstedge：指向依附于該頂點的第一條邊所對應的表結點；◆標志域mark：用以標識該條邊是否被訪問過；◆ivex和jvex域：分別保存該邊所依附的兩個頂點在圖中的位置；◆info域：保存該邊的相關信息；◆指針域ilink：指向下一條依附于頂點ivex的邊；◆指針域jlink：指向下一條依附于頂點jvex的邊；數(shù)據(jù)結構和原理全文共152頁，當前為第52頁。結點類型定義#defineINFINITYMAX_VAL/*最大值∞*/#defineMAX_VEX30/*最大頂點數(shù)*/typedefemnu{unvisited,visited}Visitting;typedefstructEdgeNode{Visittingmark;//訪問標記intivex,jvex;//該邊依附的兩個結點在圖中的位置InfoTypeinfo;//與邊相關的信息,如權值structEdgeNode*ilink,*jlink;

//分別指向依附于這兩個頂點的下一條邊}EdgeNode;/*弧邊結點類型定義*/數(shù)據(jù)結構和原理全文共152頁，當前為第53頁。typedefstructVexNode{VexTypedata;//頂點信息ArcNode*firsedge;//指向依附于該頂點的第一條邊}VexNode;/*頂點結點類型定義*/typedefstruct{intvexnum;VexNodemullist[MAX_VEX];}AMGraph;

圖7-15所示是一個無向圖及其鄰接多重表。數(shù)據(jù)結構和原理全文共152頁，當前為第54頁。鄰接多重表與鄰接表的區(qū)別：

后者的同一條邊用兩個表結點表示，而前者只用一個表結點表示；除標志域外，鄰接多重表與鄰接表表達的信息是相同的，因此，操作的實現(xiàn)也基本相似。圖7-15無向圖及其多重鄰接鏈表v1v2v3v4v1v2v3v40123

01

02∧

21∧

23

0∧3∧數(shù)據(jù)結構和原理全文共152頁，當前為第55頁。7.2.5

圖的邊表存儲結構

在某些應用中，有時主要考察圖中各個邊的權值以及所依附的兩個頂點，即圖的結構主要由邊來表示，稱為邊表存儲結構。在邊表結構中，邊采用順序存儲，每個邊元素由三部分組成：邊所依附的兩個頂點和邊的權值；圖的頂點用另一個順序結構的頂點表存儲。如圖7-16所示。邊表存儲結構的形式描述如下：#defineINFINITYMAX_VAL/*最大值∞*/#defineMAX_VEX30/*最大頂點數(shù)*/#defineMAX_EDGE100/*最大邊數(shù)*/數(shù)據(jù)結構和原理全文共152頁，當前為第56頁。typedefstructENode{intivex,jvex;/*邊所依附的兩個頂點*/WeightTypeweight;/*邊的權值*/}ENode;/*邊表元素類型定義*/typedefstruct{intvexnum,edgenum;/*頂點數(shù)和邊數(shù)*/VexTypevexlist[MAX_VEX];/*頂點表*/ENodeedgelist[MAX_EDGE];/*邊表*/

}ELGraph;

數(shù)據(jù)結構和原理全文共152頁，當前為第57頁。圖7-16無向圖的邊表表示v0v2v4v3v16742398頂點表v0v1v2v3v401234邊表132149238243344027016數(shù)據(jù)結構和原理全文共152頁，當前為第58頁。7.3

圖的遍歷圖的遍歷(TraveringGraph)：從圖的某一頂點出發(fā)，訪遍圖中的其余頂點，且每個頂點僅被訪問一次。圖的遍歷算法是各種圖的操作的基礎?！魪碗s性：圖的任意頂點可能和其余的頂點相鄰接，可能在訪問了某個頂點后，沿某條路徑搜索后又回到原頂點?！艚鉀Q辦法：在遍歷過程中記下已被訪問過的頂點。設置一個輔助向量Visited[1…n](n為頂點數(shù))，其初值為0，一旦訪問了頂點vi后，使Visited[i]為1或為訪問的次序號。圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結構是(正)鄰接鏈表。數(shù)據(jù)結構和原理全文共152頁，當前為第59頁。7.3.1深度優(yōu)先搜索算法深度優(yōu)先搜索(DepthFirstSearch--DFS)遍歷類似樹的先序遍歷，是樹的先序遍歷的推廣。1

算法思想設初始狀態(tài)時圖中的所有頂點未被訪問，則：⑴

：從圖中某個頂點vi出發(fā)，訪問vi；然后找到vi的一個鄰接頂點vi1；⑵：從vi1出發(fā)，深度優(yōu)先搜索訪問和vi1相鄰接且未被訪問的所有頂點；⑶：轉⑴

，直到和vi相鄰接的所有頂點都被訪問為止數(shù)據(jù)結構和原理全文共152頁，當前為第60頁。圖7-17無向圖深度優(yōu)先搜索遍歷(a)無向圖Gv1v2v3v4v5(b)G的鄰接鏈表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21?20?01?4?3?⑷：繼續(xù)選取圖中未被訪問頂點vj作為起始頂點，轉(1)，直到圖中所有頂點都被訪問為止。圖7-17是無向圖的深度優(yōu)先搜索遍歷示例(紅色箭頭)。某種DFS次序是：v1→

v3→

v2→

v4→

v5數(shù)據(jù)結構和原理全文共152頁，當前為第61頁。2

算法實現(xiàn)

由算法思想知，這是一個遞歸過程。因此，先設計一個從某個頂點(編號)為v0開始深度優(yōu)先搜索的函數(shù)，便于調用。在遍歷整個圖時，可以對圖中的每一個未訪問的頂點執(zhí)行所定義的函數(shù)。typedefemnu{FALSE,TRUE}BOOLEAN;BOOLEANVisited[MAX_VEX];數(shù)據(jù)結構和原理全文共152頁，當前為第62頁。voidDFS(ALGraph*G,intv){LinkNode*p;Visited[v]=TRUE;Visit[v];/*置訪問標志，訪問頂點v*/

p=G->AdjList[v].firstarc;/*鏈表的第一個結點*/while(p!=NULL){if(!Visited[p->adjvex])DFS(G,p->adjvex);

/*從v的未訪問過的鄰接頂點出發(fā)深度優(yōu)先搜索*/p=p->nextarc;}}數(shù)據(jù)結構和原理全文共152頁，當前為第63頁。voidDFS_traverse_Grapg(ALGraph*G){intv;for(v=0;v<G->vexnum;v++)Visited[v]=FALSE;/*訪問標志初始化*/

p=G->AdjList[v].firstarc;for(v=0;v<G->vexnum;v++)if(!Visited[v])DFS(G,v);}3算法分析

遍歷時，對圖的每個頂點至多調用一次DFS函數(shù)。其實質就是對每個頂點查找鄰接頂點的過程，取決于存儲結構。當圖有e條邊，其時間復雜度為O(e)，總時間復雜度為O(n+e)。數(shù)據(jù)結構和原理全文共152頁，當前為第64頁。7.3.2廣度優(yōu)先搜索算法

廣度優(yōu)先搜索(BreadthFirstSearch--BFS)遍歷類似樹的按層次遍歷的過程。1

算法思想設初始狀態(tài)時圖中的所有頂點未被訪問，則：⑴

：從圖中某個頂點vi出發(fā)，訪問vi；⑵：訪問vi的所有相鄰接且未被訪問的所有頂點vi1，vi2，…，vim；⑶：以vi1，vi2，…，vim的次序，以vij(1≦j≦m)依此作為vi，轉⑴；數(shù)據(jù)結構和原理全文共152頁，當前為第65頁。⑷

：繼續(xù)選取圖中未被訪問頂點vk作為起始頂點，轉⑴，直到圖中所有頂點都被訪問為止。圖7-18是有向圖的廣度優(yōu)先搜索遍歷示例(紅色箭頭)。上述圖的BFS次序是：v1→

v2→

v4→

v3→

v5(b)G’的正鄰接鏈表13?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51圖7-18有向圖廣度優(yōu)先搜索遍歷(a)有向圖G’v1v2v3v4v5數(shù)據(jù)結構和原理全文共152頁，當前為第66頁。2

算法實現(xiàn)

為了標記圖中頂點是否被訪問過，同樣需要一個訪問標記數(shù)組；其次，為了依此訪問與vi相鄰接的各個頂點，需要附加一個隊列來保存訪問vi的相鄰接的頂點。typedefemnu{FALSE,TRUE}BOOLEAN;BOOLEANVisited[MAX_VEX];typedefstructQueue{intelem[MAX_VEX];intfront,rear;}Queue;/*定義一個隊列保存將要訪問頂點*/數(shù)據(jù)結構和原理全文共152頁，當前為第67頁。voidBFS_traverse_Grapg(ALGraph*G){intk,v,w;LinkNode*p;Queue*Q;Q=(Queue*)malloc(sizeof(Queue));Q->front=Q->rear=0;/*建立空隊列并初始化*/for(k=0;k<G->vexnum;k++)Visited[k]=FALSE;/*訪問標志初始化*/for(k=0;k<G->vexnum;k++){v=G->AdjList[k].data;/*單鏈表的頭頂點*/if(!Visited[v])/*v尚未訪問*/

{Q->elem[++Q->rear]=v;/*v入對*/while(Q->front!=Q->rear)數(shù)據(jù)結構和原理全文共152頁，當前為第68頁。

{w=Q->elem[++Q->front];Visited[w]=TRUE;/*置訪問標志*/Visit(w);/*訪問隊首元素*/p=G->AdjList[w].firstarc;while(p!=NULL){if(!Visited[p->adjvex])Q->elem[++Q->rear]=p->adjvex;p=p->nextarc;}}/*endwhile*/}/*endif*/}/*endfor*/}數(shù)據(jù)結構和原理全文共152頁，當前為第69頁。用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的唯一區(qū)別是鄰接點搜索次序不同，因此，廣度優(yōu)先搜索算法遍歷圖的總時間復雜度為O(n+e)。圖的遍歷可以系統(tǒng)地訪問圖中的每個頂點，因此，圖的遍歷算法是圖的最基本、最重要的算法，許多有關圖的操作都是在圖的遍歷基礎之上加以變化來實現(xiàn)的。數(shù)據(jù)結構和原理全文共152頁，當前為第70頁。7.4

圖的連通性問題

本節(jié)所討論的內容是圖的遍歷算法的具體應用。7.4.1無向圖的連通分量與生成樹1無向圖的連通分量和生成樹

對于無向圖，對其進行遍歷時：◆若是連通圖：僅需從圖中任一頂點出發(fā)，就能訪問圖中的所有頂點；◆若是非連通圖：需從圖中多個頂點出發(fā)。每次從一個新頂點出發(fā)所訪問的頂點集序列恰好是各個連通分量的頂點集；數(shù)據(jù)結構和原理全文共152頁，當前為第71頁。(a)無向圖Gv1v2v3v4v5(b)G的鄰接鏈表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21?20?01?4?3?圖7-19無向圖及深度優(yōu)先生成森林(c)深度優(yōu)先生成森林v1v2v3v4v5

如圖7-19所示的無向圖是非連通圖，按圖中給定的鄰接表進行深度優(yōu)先搜索遍歷，2次調用DFS所得到的頂點訪問序列集是：{v1,v3,v2}和{v4,v5}數(shù)據(jù)結構和原理全文共152頁，當前為第72頁。

⑴若G=(V,E)是無向連通圖，頂點集和邊集分別是V(G)，E(G)。若從G中任意點出發(fā)遍歷時，E(G)被分成兩個互不相交的集合：T(G)：遍歷過程中所經(jīng)過的邊的集合；B(G)：遍歷過程中未經(jīng)過的邊的集合；顯然：E(G)=T(G)∪B(G)，T(G)∩B(G)=?

顯然，圖G’=(V,T(G))是G的極小連通子圖，且G’是一棵樹。G’稱為圖G的一棵生成樹。從任意點出發(fā)按DFS算法得到生成樹G’稱為深度優(yōu)先生成樹；按BFS算法得到的G’稱為廣度優(yōu)先生成樹。數(shù)據(jù)結構和原理全文共152頁，當前為第73頁。

⑵

若G=(V,E)是無向非連通圖，對圖進行遍歷時得到若干個連通分量的頂點集：V1(G),V2(G),…,Vn(G)和相應所經(jīng)過的邊集：T1(G),T2(G),…,Tn(G)。則對應的頂點集和邊集的二元組：Gi=(Vi(G),Ti(G))(1≦i≦n)是對應分量的生成樹，所有這些生成樹構成了原來非連通圖的生成森林。說明：當給定無向圖要求畫出其對應的生成樹或生成森林時，必須先給出相應的鄰接表，然后才能根據(jù)鄰接表畫出其對應的生成樹或生成森林。數(shù)據(jù)結構和原理全文共152頁，當前為第74頁。2圖的生成樹和生成森林算法

對圖的深度優(yōu)先搜索遍歷DFS(或BFS)算法稍作修改，就可得到構造圖的DFS生成樹算法。

在算法中，樹的存儲結構采用孩子—兄弟表示法。首先建立從某個頂點V出發(fā)，建立一個樹結點，然后再分別以V的鄰接點為起始點，建立相應的子生成樹，并將其作為V結點的子樹鏈接到V結點上。顯然，算法是一個遞歸算法。算法實現(xiàn)：數(shù)據(jù)結構和原理全文共152頁，當前為第75頁。(1)DFStree算法typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode;CSNode*DFStree(ALGraph*G,intv){CSNode*T,*ptr,*q;LinkNode*p;intw;Visited[v]=TRUE;T=(CSNode*)malloc(sizeof(CSNode));T->data=G->AdjList[v].data;T->firstchild=T->nextsibling=NULL;//建立根結點數(shù)據(jù)結構和原理全文共152頁，當前為第76頁。q=NULL;p=G->AdjList[v].firstarc;while(p!=NULL){w=p->adjvex;if(!Visited[w]){ptr=DFStree(G,w);/*子樹根結點*/if(q==NULL)T->firstchild=ptr;elseq->nextsibling=ptr;q=ptr;}p=p->nextarc;}return(T);}數(shù)據(jù)結構和原理全文共152頁，當前為第77頁。(2)BFStree算法typedefstructQueue{intelem[MAX_VEX];intfront,rear;}Queue;/*定義一個隊列保存將要訪問頂點*/CSNode*BFStree(ALGraph*G,intv){CSNode*T,*ptr,*q;LinkNode*p;Queue*Q;intw,k;Q=(Queue*)malloc(sizeof(Queue));Q->front=Q->rear=0;/*建立空隊列并初始化*/Visited[v]=TRUE;數(shù)據(jù)結構和原理全文共152頁，當前為第78頁。T=(CSNode*)malloc(sizeof(CSNode));T->data=G->AdjList[v].data;T->firstchild=T->nextsibling=NULL;//建立根結點Q->elem[++Q->rear]=v;/*v入隊*/while(Q->front!=Q->rear){w=Q->elem[++Q->front];q=NULL;p=G->AdjList[w].firstarc;while(p!=NULL){k=p->adjvex;if(!Visited[k]){Visited[k]=TRUE;數(shù)據(jù)結構和原理全文共152頁，當前為第79頁。

ptr=(CSNode*)malloc(sizeof(CSNode));ptr->data=G->AdjList[k].data;ptr->firstchild=T->nextsibling=NULL;if(q==NULL)T->firstchild=ptr;elseq->nextsibling=ptr;q=ptr;Q->elem[++Q->rear]=k;/*k入對*/}/*endif*/p=p->nextarc;}/*endwhilep*/}/*endwhilQ*/return(T);}/*求圖G廣度優(yōu)先生成樹算法BFStree*/數(shù)據(jù)結構和原理全文共152頁，當前為第80頁。(3)圖的生成森林算法CSNode*DFSForest(ALGraph*G){CSNode*T,*ptr,*q;intw;for(w=0;w<G->vexnum;w++)Visited[w]=FALSE;T=NULL;for(w=0;w<G->vexnum;w++)if(!Visited[w]){ptr=DFStree(G,w);if(T==NULL)T=ptr;elseq->nextsibling=ptr;q=ptr;}return(T);}數(shù)據(jù)結構和原理全文共152頁，當前為第81頁。7.4.2

有向圖的強連通分量

對于有向圖，在其每一個強連通分量中，任何兩個頂點都是可達的。VG，與V可相互到達的所有頂點就是包含V的強連通分量的所有頂點。設從V可到達(以V為起點的所有有向路徑的終點)的頂點集合為T1(G)，而到達V(以V為終點的所有有向路徑的起點)的頂點集合為T2(G)，則包含V的強連通分量的頂點集合是：

T1(G)∩T2(G)。求有向圖G的強連通分量的基本步驟是：⑴對G進行深度優(yōu)先遍歷，生成G的深度優(yōu)先生成森林T。⑵對森林T的頂點按中序遍歷順序進行編號。數(shù)據(jù)結構和原理全文共152頁，當前為第82頁。⑶改變G中每一條弧的方向，構成一個新的有向圖G’。⑷按⑵中標出的頂點編號，從編號最大的頂點開始對G’進行深度優(yōu)先搜索，得到一棵深度優(yōu)先生成樹。若一次完整的搜索過程沒有遍歷G’的所有頂點，則從未訪問的頂點中選擇一個編號最大的頂點，由它開始再進行深度優(yōu)先搜索，并得到另一棵深度優(yōu)先生成樹。在該步驟中，每一次深度優(yōu)先搜索所得到的生成樹中的頂點就是G的一個強連通分量的所有頂點。⑸重復步驟⑷，直到G’中的所有頂點都被訪問。如圖7-20(a)是求一棵有向樹的強連通分量過程。數(shù)據(jù)結構和原理全文共152頁，當前為第83頁。dacfeb(a)有向圖G654321dacfeb(b)執(zhí)行步驟(1)和(2)acdfeb(c)執(zhí)行步驟(3)adcbef(d)執(zhí)行步驟(4)和(5)圖7-20利用深度優(yōu)先搜索求有向圖的強連通分量

在算法實現(xiàn)時，建立一個數(shù)組in_order[n]存放深度優(yōu)先生成森林的中序遍歷序列。對每個頂點v，在調用DFS函數(shù)結束時，將頂點依次存放在數(shù)組in_order[n]中。圖采用十字鏈表作為存儲結構最合適。算法實現(xiàn)：intin_order[MAX_VEX];數(shù)據(jù)結構和原理全文共152頁，當前為第84頁。voidDFS(OLGraph*G,intv)//按弧的正向搜索{ArcNode*p;Count=0;Visited[v]=TRUE;for(p=G->xlist[v].