《第7章圖結(jié)構(gòu)》習(xí)題解答要點

1、第7章圖結(jié)構(gòu)第7章圖結(jié)構(gòu)本章學(xué)習(xí)要點 熟悉圖的定義、相關(guān)術(shù)語以及基本概念 熟練掌握圖的4種存儲結(jié)構(gòu)，能根據(jù)實際問題選擇合適的存儲結(jié)構(gòu) 熟練掌握圖的兩種遍歷方法 理解并掌握最小生成樹意義和兩種算法 理解并掌握查找最短路徑的有關(guān)算法 理解并掌握拓撲排序的有關(guān)算法 理解并掌握查找關(guān)鍵路徑的有關(guān)算法在計算機科學(xué)、工程以及其它許多學(xué)科中，常常需要研究數(shù)據(jù)對象之間的各種關(guān)系。比 如，可以用線性表來表示數(shù)據(jù)對象之間的線性關(guān)系，用樹結(jié)構(gòu)來表示數(shù)據(jù)對象之間的某種層 次關(guān)系。但是，還有許多問題(比如信息通信網(wǎng)絡(luò))中的數(shù)據(jù)對象是不能用以上兩種關(guān)系來 明確表示的，這就需要一種更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)一圖結(jié)構(gòu)。圖結(jié)構(gòu)可以用來

2、表示數(shù)據(jù)對象之間的任意關(guān)系，圖中的每個結(jié)點都可以和其它任一結(jié)點相連接，即圖中數(shù)據(jù)對象之間的對應(yīng) 關(guān)系是多個對多個”的關(guān)系。本章將詳細介紹圖的基本概念、各種存儲結(jié)構(gòu)、遍歷方法，求圖的連通分量、生成樹、 最短路徑，最后介紹一些有關(guān)圖的應(yīng)用問題。7.1 圖的定義和基本術(shù)語7.1.1 圖的定義圖g(graph)是由兩個集合v和vr組成，記為g=(v,vr)。v是頂點的有窮非空集合；vr是定義在v上的所有關(guān)系(兩個不同頂點之間的弧或邊)的集合。vr可以是空集合，當(dāng) vr為空集時g表示集合類結(jié)構(gòu)類型。如圖7.1(a)、(b)所示的是一個有向圖和一個無向圖。g)有向圖s)無向圖圖了 1圖的雪例7.1.2 圖

3、結(jié)構(gòu)的基本術(shù)語(1)頂點(vertex)圖中的數(shù)據(jù)元素。比如，圖 7.1中的頂點有：v1,v2,v3,v4,v5,v6。(2)弧(arc)設(shè)vr是圖中所有頂點之間的關(guān)系集，若 6vr,則表示從頂點 v到頂點w的一條弧。例如，在圖 7.1(a)所示的圖 g 中的弧有：, 和 , 共 8 條弧。(3)弧尾(tail)弧的起始點。(4)弧頭(head)弧的終端點。一條弧用有序?qū)Ψ枴梆?，弧頭 ”來表示。(5)有向圖(digraph)由頂點和弧組成的圖稱為有向圖。比如，圖7.1(a)表示一個有向圖。(6)邊(edge)設(shè)vr是圖中所有頂點之間的關(guān)系集，若 6 vr必有 6 vr,則以無 序?qū)Ψ?v

4、,w)或(w,v)來代替和,表示頂點v與頂點w之間的一條邊。例如，在圖 7.1(b)所示的圖 g 中的邊有：(v1,v2),(v1,v4),(v2,v3),(v2,v6),(v3,v5),(v4,v5)和 (v5,v6)共7條邊。(7)無向圖(undigraph)由頂點和邊組成的圖稱為無向圖。比如，圖7.1(b)表示一個無向圖。(8)完全圖(completed graph)用n表示圖中的頂點數(shù)，則具有 n(n-1)/2條邊的無向圖稱為 無向完全圖；具有n(n-1)條弧的有向圖稱為 有向完全圖。當(dāng)圖g中邊(或弧)的總數(shù)e滿足：e n log n時稱其為 稠密圖(densegraph)o顯然，完全

5、圖是稠密圖，反之不然。圖 而圖7.2(b)則是由3個頂點組成的有向完全圖。7.2(a)所示為由4個頂點組成的無向完全圖,口)無向完全圖 也有向完全圖 圖7 2完全圖示例-.169.-(9)權(quán)(weight)與圖的邊或弧相關(guān)的數(shù)(比如長度)稱為權(quán)。(10)網(wǎng)(network)具有權(quán)值的圖稱為網(wǎng)，帶權(quán)的有向圖稱為 有向網(wǎng)，帶權(quán)的無向圖稱為 無向網(wǎng)。比如，圖7.3(a)表示的是一個有向網(wǎng)，而圖7.3(b)表示的是一個無向網(wǎng)。la)有向網(wǎng)cb)無向網(wǎng)圖丁3網(wǎng)示例(11)子圖(subgraph)假設(shè)有兩個圖g=(v,e)和g =(v ,e),若v七v并且e,=e,則稱g 是g的子圖。例如，圖7.4(a)

6、為有向圖及其部分子圖，圖7.4(b)為無向圖及其部分子圖。“1|上)無向圖子圖2子圖1e7.4(12)鄰接點(adjacent)對于無向圖有向圖和無向圖的子圖示例g=(v,vr),若邊(v,w) vr,則稱v和w互為鄰接點,邊(v,w)依附(incident)于頂點v和w,或者說邊(v,w)與頂點v、w相關(guān)聯(lián)。對于有向圖g=(v,v r),若弧 vr,則稱頂點v鄰接到頂點w ,頂點w鄰接自頂點v。(13)度(degree)在無向圖中，頂點 v的度是指和v相關(guān)聯(lián)的邊的數(shù)目，記為(14)出度(out degree)和入度(in degree)在有向圖中，頂點 v的出度是指以的數(shù)目，記為 od(v)

7、;頂點v的入度是指以v為弧頭的弧的數(shù)目，記為id(v);td(v)。v為弧尾的弧頂點v的度是指v的出度、入度的和，記為td(v)。一般地，如果頂點vi的度記為td(v i), 足關(guān)系如下：那么一個有n個頂點e條邊(或弧)的圖，必定滿17 td v)2 i0(15)路彳5 (path)在圖中，從頂點 v到頂點w的頂點序列稱為路徑。顯然，有向圖的路徑是有向的。路徑長度 是指路徑上的邊或弧的數(shù)目。序列中頂點不重復(fù)出現(xiàn)的路徑稱為徑。(16)回路或環(huán)(cycle)在路徑的頂點序列中，第一個頂點和最后一個頂點相同的路徑稱為簡單路回路。除了第一個頂點和最后一個頂點外，其余頂點均不重復(fù)出現(xiàn)的回路稱為 單環(huán)。例

8、如，在圖7.4(a)所示的有向圖中，頂點序列 m,mw)表示一簡單回路或簡條有向路徑，由于其中存在重復(fù)點vi所以不是簡單路徑，該路徑的長度為4；頂點序列(vi,v3,v4)表示一條有向路徑，并且是長度為2的簡單路徑；頂點序列(vi,v3,v4,v1)表示一條有向路徑并且是長度為3的簡單回路(或環(huán))。在圖7.4(b)所示的無向圖中，頂點序列(vi,v3,v5,v4,v3,v5,v2)表示一條路徑，由于其 中存在重復(fù)點v3、v5所以不是簡單路徑；頂點序列(vi,v3,v4,v5,v2,v1)是長度為5的簡單回路。(17)連通圖(connected graph)在無向圖g=(v,vr)中，如果從頂點

9、 v到頂點w有路徑，則 稱v與w是連通的。如果對于任意兩個頂點v,w c v都是連通的則稱 g是連通圖。(18)連通分量(connected component)無向圖g中的極大連通子圖稱為 g的連通分量。圖7.5給出一個無向圖和它的3個連通分量的示例。()的3個連通分量無向非連通圖g無向非連通圖和它的3個連逋分量(19)強連通圖 在有向圖g=(v,vr)中，如果對于任意兩個頂點v,wcv,都存在一條v到w第7章圖結(jié)構(gòu)的路徑，則稱 g是強連通圖；如果對于任意兩個頂點 v,wcv,都存在一個頂點序列：v=v0,vl,v2,，v=w 滿足 或 e vr,則稱 g是弱連通圖。例如，圖7.1(a)為弱

10、連通圖,圖7.2(b)為強連通圖。(20)強連通分量 有向圖g中的極大強連通子圖稱為g的強連通分量。圖7.6給出一個有向圖和它的2個強連通分量的示例。3)有向非連通圖g也)g的2個強連通分星e7.6有向非連逋圖和它的2個覆連逋分量-.173 .-說明：在連通分量和強連通分量定義中的極大”應(yīng)理解為包含依附于該連通子圖或強連通子圖中頂點的所有邊或弧。(21)生成樹一個無向連通圖的生成樹是一個 極小連通子圖，即它包含圖中的所有(假設(shè) n個)頂點，但是只有足以構(gòu)成一棵樹的n-1條邊。說明：1 ) 一個無向連通圖的生成樹不是唯一的，所有生成樹的頂點相同但是所包含的邊可以不 同。2) 一棵有n個頂點的連通

11、圖的生成樹有且僅有n-1條邊。但是有 n個頂點和n-1條邊的無向圖不一定是生成樹。例如，圖7.7給出一個連通圖(圖7.7(a)和它的3棵生成樹(圖7.7(b)的示例。(22)生成森林如果一個有向圖 g恰有一個頂點的入度為 0,其余頂點的入度均為 1,則g是一棵有向樹。一個有向圖的生成森林由若干棵有向樹組成，森林中含有圖中全部頂點、但是只有足以包戈芍于愣丕出交也有回村.町弧.。顯然,一個有向圖生成的有向樹或生成森林都 不是唯一的。e如)有向圖gs7.3有向圖生成有向樹和森林的示圖關(guān)于頂點位置”的說明：在圖的基本操作定義中， 其 頂點位置”和 鄰接點位置”僅是一個相對的概念。 從圖的定義可以看出，

12、圖中所有頂點的位置都是平等的，可以將任意一個頂點看成是第一個或最后一個頂點，也無法將其排列成一個線性序列或?qū)哟侮P(guān)系。在實際操作中，為了方便起見，需要將所有頂點按照某個任意選定的順序排列起來(排列與圖中頂點之間的關(guān)系無關(guān))。所以，頂點在圖中的位置”是指該頂點在這個人為的隨意排列中的位置(或序號)。同理，可以對某個頂點的所有鄰接點按照某個任意選定的順序進行排列。2 .1.3圖的基本操作對于圖結(jié)構(gòu)，常用的操作有以下幾種：(1)創(chuàng)建creategraph(&g,v,vr)根據(jù)頂點集v和關(guān)系(邊或弧)集 vr構(gòu)造圖g;(2)查找locatevex(g,u)函數(shù)功能是，如果圖g中存在信息等于u的頂點則返回

13、該頂點在g中的位置，否則返回0;(3)提取getvex(g,v)函數(shù)功能是，返回圖 g中頂點v的信息；(4)修改putvex(&g ,v,value)函數(shù)功能是，修改圖 g中頂點v的信息為value;(5)鄰接點firstadjvex(g ,v)函數(shù)功能是，返回圖 g中頂點v的第一個鄰接點在 g中的位 置，操作不成功時返回0;(6)下一個鄰接點 nextadjvex(g ,v,w)函數(shù)中v,w是圖g的頂點，且w是v的一個鄰接點。 函數(shù)功能是，返回頂點 v相對于w的下一個鄰接點所在的位置，如果 w是v的最后一個鄰接 點則返回0;(7)插入頂點insertvex(&g ,v)函數(shù)功能是，在圖 g中

14、插入頂點v;(8)刪除頂點deletevex(&g,v)函數(shù)功能是，在圖g中刪除頂點v以及相關(guān)的邊或弧；(9)插入弧insertarc(&g ,v,w)函數(shù)功能是，在圖 g中增加邊(v,w)或弧;(10)刪除弧deletearc(&g ,v,w)函數(shù)功能是，在圖 g中刪除邊(v,w)或弧 ;(11)深度優(yōu)先遍歷dsftraverse(g,v,visit()函數(shù)功能是，從頂點v開始按深度優(yōu)先遍歷圖g,其中visit()是關(guān)于頂點的操作函數(shù)；(12)廣度優(yōu)先遍歷 bsftraverse(g,v,visit()函數(shù)功能是，從頂點v開始按廣度優(yōu)先遍歷圖 g,其中visit()是關(guān)于頂點的操作函數(shù)。7.

15、2圖的存儲表示與實現(xiàn)圖是一種復(fù)雜結(jié)構(gòu)其存儲方法也比較多，在實際應(yīng)用中，一般需要根據(jù)具體的圖形和要 進行的操作來選取適當(dāng)?shù)拇鎯Y(jié)構(gòu)。圖的常用存儲結(jié)構(gòu)有：鄰接矩陣表示法、鄰接表表示法、 十字鏈表表示法和多重鏈接表表示法。7.2.1 鄰接矩陣表示法鄰接矩陣表示法是圖的一種順序存儲表示法。用兩個數(shù)組分別存儲數(shù)據(jù)元素(頂點)的 信息和元素之間所存在的關(guān)系(邊或弧)的信息。該表示法既可用于表示無向圖也可用于表示有 向圖。1 .鄰接矩陣的定義設(shè)g=(v,vr)是一個圖，含有n個頂點，那么g的鄰接矩陣是表示 g中頂點之間相鄰關(guān)系 的n階方陣anw,下面分別根據(jù)有權(quán)圖和無權(quán)圖給出矩陣a的定義。如果g是無權(quán)圖，則

16、a的定義為：1(vi，vj) wvr或 wvrai j0其它情況如果g是有權(quán)圖，則a的定義為：fwij(vi ,vj) wvr 或 wyr(權(quán)彳wj #0)ai j、0 其它情況(為操作統(tǒng)一此處用0而非)【例7.1】分別給出圖7.1、圖7.3中各圖的鄰接矩陣。7.9(a)、圖7.9(b)所示；在圖 排列時的鄰接矩陣分別如圖在圖7.1(a)、圖7.1(b)中，圖的頂點順序按vi,v2,v3,v4,v5,v6排列時的鄰接矩陣分別如圖a,b,c, d 和 a,b,c, d,e7.3(a)、圖7.3(b)中，圖的頂點順序分別按7.9(c)、圖 7.9(d)所示。01010000000010000100

17、10000001001000100101001010010i00i010001000110iaiooio0 70 00 09 0100000500p08dgoo3o00001283001001210無向圖r有向網(wǎng)和無向網(wǎng)的鄒媵炬陣表示顯然，圖的鄰接矩陣有以下特點：(1)當(dāng)圖中頂點的排列順序確定后，該圖的鄰接矩陣是唯一確定的；(2)無向圖的鄰接矩陣是對稱的，可以采用壓縮存儲的方法僅存入其下三角(或上三角)部分的元素即可；n _1(3)在無向圖中，頂點vi的度是其鄰接矩陣a的第i行元素的和，即：td (v ) =z ai j；j =0(4)在有向圖中，頂點vi的出度是其鄰接矩陣 a的第i行元素的和

18、，而入度是a的第i列元n _1n -1素的和，所以vi的度可以表示為：td(vi)= ai j +z a ji (n為圖中頂點的個數(shù))j 0：j zq2.鄰接矩陣的存儲表示與實現(xiàn)(1)鄰接矩陣的類型定義圖的類型gkind有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef enumdg,dn,udg,udngkind;第7章圖結(jié)構(gòu)typedef int vtype;struct vnodeint flag;vtype vex;struct mgraphvnode* vexs;vtype* arcs;int vexnum,arcnum;gkind kind;為便于操作，定義頂點類型 vtype為int型

19、/頂點與訪問情況類型 vnode訪問次數(shù)，頂點信息/定義圖的鄰接矩陣類型mgraph描述頂點的數(shù)組指針鄰接矩陣的數(shù)組指針vexsarcs/頂點數(shù)vexnum和邊或弧數(shù) arcnum圖的種類標志kind(2)查找圖中頂點位置的操作函數(shù)的功能是，返回頂點u在圖g中的位置，查找失敗返回 0值。int locatevex_mg(mgraph g,vtype u) int i;for(i=0;ig .vexnum;i+)if(g.vexsi.vex=u) break;if(ig.vexnum)return(i+1);else return(0);(3)鄰接矩陣的建立操作函數(shù)的功能是，根據(jù)圖 g的種類標志

20、kind建立圖#includeiostream.hvoid creategraph_mg(mgraph& g ,gkind kind)int i,j,k;vtype u,v;coutg.vexnumg .arcnum;g.kind=kind;g.vexs=new vnodeg .vexnum;g.arcs=new vtypeg.vexnum*g .vexnum;g的所有信息。為gvexs分配存儲空間為g.arcs分配存儲空間cout按某種順序輸入g .vexnum個頂點的值：n;for(i=0;ig.vexsi.vex;for(i=0;ig .vexnum;i+)for(j=0;jg .vex

21、num;j+)g.arcsi*g.vexnum+j=0;if(g.kind=dg|g .kind=udg)/flag=0表示該頂點未被訪問/輸入所有頂點的信息到g.vexs中/將圖g的關(guān)系集garcs初始化為空集cout輸入圖中g(shù).arcnum條邊(弧)的信息u v:n;-.181.-elsecout輸入圖中g(shù).arcnum條邊(弧)和權(quán)的信息 u v w:n;for(k=0;kuv; 根據(jù)頂點信息找到所在位置while(!(i=locatevex_mg(g )&(j=locatevex_mg(g,v); i-,j-;/i,j從位置值轉(zhuǎn)換為下標值g.arcsi*g.vexnum+j=1; if

22、(g.kind=dn|g .kind=udn) cing.arcsi*g .vexnum+j;/b入相應(yīng)邊或弧的權(quán)重 wif(g.kind=udg|g .kind=udn)無向圖的鄰接矩陣是對稱的g.arcsj*g.vexnum+i=g .arcsi*g.vexnum+j; (4)顯示輸出鄰接矩陣的操作函數(shù)功能是，顯示輸出圖g的鄰接矩陣 garcs。void displymg(mgraph g) int i,j;for(i=0;ig.vexnum;i+) for(j=0;jg .vexnum;j+)coutg.arcsi*g .vexnum+j ;coutendl;(5)演示程序主函數(shù)程序中分

23、別建立有向圖g1、無向圖g2、有向網(wǎng)g3和無向網(wǎng)g4的鄰接矩陣，并顯示輸出每個鄰接矩陣的數(shù)據(jù)信息。void main() mgraph g1,g2,g3,g4;gkind gk1=dg ,gk2=udg ,gk3=dn,gk4=udn;cout建立一個有向圖的鄰接矩陣g1:n;creategraph_mg(g1,gk1);cout建立一個無向圖的鄰接矩陣g2:n;creategraph_mg(g2,gk2);cout有向圖g1的鄰接矩陣為：n;displymg(g1);cout無向圖g2的鄰接矩陣為：n;displymg(g2);cout*n;cout建立一個有向網(wǎng)的鄰接矩陣g3:n;crea

24、tegraph_mg(g3,gk3);cout建立一個無向網(wǎng)的鄰接矩陣g4:n;creategraph_mg(g4,gk4);cout有向網(wǎng)g3的鄰接矩陣為：n;displymg(g3);cout無向網(wǎng)g4的鄰接矩陣為：n;displymg(g4);程序運行演示結(jié)果為：建立一個有向圖的鄰接矩陣g1:輸入頂點數(shù)vexnum和弧數(shù)arcnum:6 8/按某種順序輸入6個頂點的值： 一1 2 3 4 5 6/輸入圖中8條邊(弧)的信息u v:1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5/建立一個無向圖的鄰接矩陣g2:輸入頂點數(shù)vexnum和弧數(shù)arcnum:6 7/按某種順序輸入6

25、個頂點的值：一1 2 3 4 5 6/輸入圖中7條邊(弧)的信息u v:1 2 1 4 2 3 2 6 5 3 5 6 5 4/有向圖g1的鄰接矩陣為：0 1 0 1 0 00 0 0 0 0 01 0 0 0 0 10 0 1 0 0 00 0 0 1 0 00 1 0 0 1 0*建立一個有向網(wǎng)的鄰接矩陣g3:輸入頂點數(shù)vexnum和弧數(shù)arcnum:4 4/按某種順序輸入4個頂點的值：一1 2 3 4/輸入圖中4條邊(弧)和權(quán)的信息u v w:1 2 7 1 3 1 3 4 5 4 1 9/建立一個無向網(wǎng)的鄰接矩陣 g4:輸入頂點數(shù)vexnum和弧數(shù)arcnum:5 5/按某種順序輸入5

26、個頂點的值：一1 2 3 4 5/輸入圖中5條邊(弧)和權(quán)的信息u v w:1 2 9 4 1 8 4 2 3 4 5 1 3 5 12/有向網(wǎng)g3的鄰接矩陣為：0 7 1 00 0 0 00 0 0 59 0 0 01 0 0 0 1 0無向圖g2的鄰接矩陣為：無向網(wǎng)g4的鄰接矩陣為0 1 0 1 0 00 90 8 01 0 1 0 0 19 00 3 00 1 0 0 1 00 00 0 121 0 0 0 1 08 30 0 10 0 1 1 0 10 012 1 0說明：(1)程序演示中建立的是圖7.1、圖7.3中4個圖的鄰接矩陣:gl.arcs、g2.arcs、g3.arcs、g4

27、.arcs。從運行結(jié)果可以看出與圖7.9的形式一致。(2)在圖的鄰接矩陣存儲結(jié)構(gòu)上也容易實現(xiàn)其它基本操作，比如，對于無向圖g中返回頂點v的第一個鄰接點位置的基本操作函數(shù)：int firstadjvex_mg(mgraph g,vtype v)。算法的實現(xiàn)過程是：1)根據(jù)頂點信息 v,通過調(diào)用函數(shù)int locatevex_mg(mgraph g,vtype v)找到v在g中的 位置i;2)在g的鄰接矩陣中尋找第i行中第一個非零元素所在的列號j;3)如果j存在函數(shù)返回j+1,否則返回0值。類似地可以給出函數(shù)：int nextadjvex_mg(mgraph g ,vtype v,vtype w)

28、的算法實現(xiàn)代碼。(3)用鄰接矩陣表示有 n個頂點的圖g時，查找邊(或弧)的時間復(fù)雜度為o(n2)。由于鄰接矩陣的存儲空間僅與頂點數(shù)n有關(guān)，而與邊無關(guān)，因此，當(dāng)圖 g的頂點較多而邊數(shù)又很少時，其邊的查找效率會很低。為此，下面給出圖的另一種存儲結(jié)構(gòu)，即圖的鄰接表表示法。7.2.2鄰接表表示法圖的鄰接表表示是把圖的每個頂點的鄰接頂點用一個鏈表來表示。一般地，用順序存儲的方式來表示圖中n個頂點的信息，另外，對圖中每個頂點v建立一個單鏈表，用于表示與 v相鄰接的所有頂點的位置（下標）。鏈表中每個結(jié)點有兩個域值：一個是頂點位置（下標）域， 用于表示該鄰接點的序號；另一個是指針域，用于指向下一個鄰接點。1

29、.鄰接表的定義（1）表結(jié)點 在鄰接表中，對圖中的每個頂點建立一個單鏈表，頂點v所對應(yīng)的單鏈表中的結(jié)點（表示依附于該頂點的邊或以v為尾的?。┓Q為 表結(jié)點。圖的表結(jié)點中包含有頂點位置域（adjvex）、指向下一條邊（?。┑闹羔樣颍╪extarc）；而網(wǎng)的表結(jié)點中還要有表示相應(yīng)權(quán)值 的域（weight）。（2）頭結(jié)點 在鄰接表中每個單鏈表上附設(shè)一個結(jié)點，稱為頭結(jié)點。每個頭結(jié)點由 3個域 組成：結(jié)點信息域（data）、結(jié)點訪問次數(shù)域（flag）和指向鏈表中第一個結(jié)點的指針域 （nextarc）。 圖中的所有頭結(jié)點以順序結(jié)構(gòu)存儲。在圖7.10中分別給出鄰接表表結(jié)點的結(jié)構(gòu)示圖（a）和頭結(jié)點的結(jié)構(gòu)示圖（b）

30、oadjvexwe ii ghtnextarcdataflagnext-arc鄰接栽培點結(jié)構(gòu)3）頭結(jié)點結(jié)構(gòu)圖7.1口鄰接表的結(jié)點結(jié)構(gòu)示圖例如，圖7.11分別給出有向圖 g1和無向圖g2的一種鄰接表表示結(jié)構(gòu)?？谟邢驁Dg1吼及g1的一種翎接表表示匡11圖的鄂接表表亭本例由于圖中頂點的排列次序可以不同，每個頂點的鄰接點的排列順序也可以不同，所以， 一個圖的鄰接表表示不唯一。用鄰接表表示具有 n個頂點和e條邊的無向圖時，需要一個由n個元素組成的順序表（表 頭結(jié)點表）和由2e個結(jié)點組成的n個單鏈表。而表示 n個頂點和e條弧的有向圖時，需要一 個由n個元素組成的順序表和由 e個結(jié)點組成的n個單鏈表。當(dāng)圖中

31、邊（或?。┑臄?shù)目遠遠少 于圖的頂點數(shù)目時，鄰接表所需的存儲空間要比鄰接矩陣所需的少。2 .逆鄰接表在圖g的鄰接表中，頂點 v的相鄰元素可以通過遍歷該頂點對應(yīng)的單鏈表求得，設(shè)該鏈表中結(jié)點的個數(shù)為 k那么，g為無向圖時k表示v的度，g為有向圖時k表示v的出度。如果 求頂點v的入度，則需要遍歷鄰接表中的所有單鏈表，統(tǒng)計與v的序號相同的結(jié)點個數(shù)。這樣處理很不方便，為此，仿照鄰接表，建立一個逆鄰接表，即對每個頂點 v建立一個單鏈表，把所有鄰接于v的頂點鏈接在一起，此時該單鏈表的長度即為v的入度。例如，圖7.11(a)所示的有向圖可用逆鄰接表表示為圖7.12。117.12有向圖的法郭授表表示3.鄰接表的存

32、儲表示與實現(xiàn)(1)鄰接表存儲結(jié)構(gòu)的類型定義定義單鏈表結(jié)點類型arcnode :struct arcnode int adjvex,weight;arcnode* nextarc;定義鏈表頭結(jié)點結(jié)構(gòu)類型vexnode:struct vexnodevtype data;int flag;arcnode* nextarc;定義鄰接表存儲結(jié)構(gòu)的類型algraph :struct algraphvexnode* vertices;/定義頭結(jié)點數(shù)組指針 verticesint vexnum,arcnum;頂點數(shù) vexnum 和邊或弧數(shù) arcnumgkind kind;圖的種類標志kind;(2)查找圖

33、中頂點位置的操作函數(shù)的功能是，返回頂點 u在圖g中的位置，查找失敗返回0值。int locatevex_al(algraph g ,vtype u) int i;for(i=0;ig .vexnum;i+)if(g.verticesi.data=u) break;if(ig.vexnum)return(i+1);else return(0); (3)鄰接表的建立操作函數(shù)的功能是，根據(jù)圖 g的種類標志kind建立g的鄰接表表示的存儲結(jié)構(gòu)。#includeiostream.hvoid creategraph_al(algraph& g ,gkind kind) int i,j,k;vtype u,

34、v;arcnode* pr,*pr1;g.kind=kind;coutg.vexnumg .arcnum; g.vertices=new vexnodeg .vexnum;為頂點數(shù)組分配內(nèi)存空間cout按某種順序輸入g .vexnum個頂點的值：n; for(i=0;ig.verticesi.data;/輸入所有頂點的信息到 vex中g(shù).verticesi.nextarc=null;設(shè)定初始的單鏈表為空 if(g.kind=dg|g .kind=udg) cout輸入圖中g(shù).arcnum條邊(弧)的信息u v:n; else cout輸入圖中g(shù).arcnum條邊(弧)和權(quán)的信息 u v w:n

35、; for(k=0;kuv; while(!(i=locatevex_al(g )&(j=locatevex_al(g ,v); i-,j-;/i,j從位置值轉(zhuǎn)換為下標值pr=new arcnode;動態(tài)分配單鏈表結(jié)點 prpr-adjvex=j; pr-weight=0; if(g.kind=dn|g .kind=udn)cinpr-weight;/輸入對應(yīng)邊(弧)的權(quán)值pr-nextarc=g.verticesi.nextarc;將結(jié)點pr插入到第i個鏈表的首部g.verticesi.nextarc=pr; if(g.kind=udg|g .kind=udn) /對于無向圖(或網(wǎng))將結(jié)點p

36、r1插入到第j個鏈表的首部 pr1=new arcnode;/動態(tài)分配單鏈表結(jié)點 pr1pr1-adjvex=i; pr1-weight=pr-weight; pr1-nextarc=g .verticesj.nextarc; g.verticesj.nextarc=pr1;將結(jié)點pr1插入到第j個鏈表的首部/end switch /end for (4)顯示輸出鄰接矩陣的操作 函數(shù)功能是，顯示輸出圖g的鄰接鏈表中的所有信息。void displyal(algraph g)/ 顯示鄰接矩陣 g int i;arcnode* p;for(i=0;ig .vexnum;i+) p=g.vertic

37、esi.nextarc;couti (g .verticesi.data):; while(p) if(g .kind=dg|g .kind=udg) coutadjvex;else/對于圖僅輸出頂點的下標值/對于網(wǎng)要輸出下標與對應(yīng)的權(quán)的值couttadjvex,weightnextarc;coutendl;/end for(5)演示程序主函數(shù)程序中分別建立有向圖 g1、無向圖g2、有向網(wǎng)g3和無向網(wǎng)g4的鄰接表，并顯示輸出 所建立的每個鄰接表的數(shù)據(jù)信息。void main() algraph g1,g2,g3,g4;gkind gk1=dg ,gk2=udg ,gk3=dn,gk4=udn;

38、cout建立一個有向圖的鄰接表creategraph_al(g1,gk1);cout建立一個無向圖的鄰接表creategraph_al(g2,gk2);cout有向圖g1的鄰接表為:n;displyal(gi);cout”無向圖g2的鄰接表為：n;displyal(g2);g1:n;g2:n;cout*n;cout建立一個有向網(wǎng)的鄰接表creategraph_al(g3,gk3);cout建立一個無向網(wǎng)的鄰接表creategraph_al(g4,gk4);cout有向網(wǎng)g3的鄰接表為：n;displyal(g3);cout無向網(wǎng)g4的鄰接表為：n;displyal(g4);程序運行演示結(jié)果為：

39、建立一個有向圖的鄰接表 g1:g3:n;g4:n;輸入頂點數(shù)和邊(弧)數(shù)vexnum arcnum:6 8 /第7章圖結(jié)構(gòu)按某種順序輸入6個頂點的值：1 2 3 4 5 6/輸入圖中8條邊(弧)的信息u v:1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5/建立一個無向圖的鄰接表g2輸入頂點數(shù)和邊(弧)數(shù)vexnum arcnum:6 7 /按某種順序輸入6個頂點的值：1 2 3 4 5 6/輸入圖中7條邊(弧)的信息u v:1 2 1 4 2 3 2 6 5 3 5 6 5 4/有向圖g1的鄰接表為：0 (1)： 3 11 (2)：2 (3): 5 03 (4): 24 (5)

40、: 35 (6): 4 0無向圖g2的鄰接表為：0 (1): 3 11 (2): 5 2 02 (3): 4 13 (4): 4 04 (5): 3 5 25 (6): 4 1說明：*建立一個有向網(wǎng)的鄰接表g3:輸入頂點數(shù)和邊(弧)數(shù)vexnum arcnum:4 4 /按某種順序輸入4個頂點的值：1 2 3 4/輸入圖中4條邊(弧)和權(quán)的信息u v w:1 2 7 1 3 1 3 4 5 4 1 9/建立一個無向網(wǎng)的鄰接表g4:輸入頂點數(shù)和邊(弧)數(shù)vexnum arcnum:5 5 /按某種順序輸入5個頂點的值：1 2 3 4 5/輸入圖中5條邊(弧)和權(quán)的信息u v w:1 2 9 4

41、1 8 4 2 3 4 5 1 3 5 12/有向網(wǎng)g3的鄰接表為：0 (1)： 2,1 1,71 (2)：2 (3): 3,53 (4): 0,9無向網(wǎng)g4的鄰接表為：0 (1)： 3,8 1,91 (2)： 3,3 0,92 (3): 4,123 (4): 4,1 1,3 0,84 (5): 2,12 3,1-.183.-(1)程序演示中建立的是圖7.1、圖7.3中4個圖的一種鄰接表表示：g1.vertices、g2.verticesg3.vertices 和 g4.vertices。(2)在程序顯示的結(jié)果中，第一列為頂點的下標，第二列為圖中所有頂點的值。對于圖， 單鏈表中的每一項表示該頂

42、點的鄰接點的下標；對于網(wǎng)，單鏈表中的每一項表示該頂點的鄰 接點的下標值和相應(yīng)邊(弧)的權(quán)值。(3)在建立鄰接表時，由于輸入的是頂點信息，所以要先通過查找求得該頂點在圖中的位置，再將相應(yīng)結(jié)點插入到對應(yīng)單鏈表的首部，所以，該操作的時間復(fù)雜度為o(n*e)。7.2.3有向圖的十字鏈表表示法十字鏈表是有向圖的另一種鏈式存儲結(jié)構(gòu)，該方法是將有向圖的鄰接表和逆鄰接表結(jié)合 起來得到的一種鏈表。1.十字鏈表的定義7.13給出十類似鄰接表，在十字鏈表中包含鏈表的頭結(jié)點和弧結(jié)點兩種類型的結(jié)點，圖 字鏈結(jié)點結(jié)構(gòu)的示圖。tai i vex head vex hi i nk 11i nk i n千口品 懺 i rsti

43、n + i rstout|g)頭皓點結(jié)構(gòu))迎堵點結(jié)構(gòu)圖丁 13 十字選會的結(jié)點結(jié)構(gòu)其中，頭結(jié)點包含頂點信息域(data)、指向以該頂點為弧頭的第一個弧結(jié)點的指針域(firstin)、指向以該頂點為弧尾的第一個弧結(jié)點的指針域(firstout),表的所有頭結(jié)點以順序存儲?；〗Y(jié)點包含表示弧尾頂點下標的尾域(tailvex) 表示弧頭頂點下標的頭域 (headvex)、指向弧頭相同的下一條弧的指針域 (hlink)、指向弧尾相同的下一條弧的指針域(tlink)、弧的信息(如權(quán)第7章圖結(jié)構(gòu)值)域(info)。例如，圖7.14給出有向圖的一種十字鏈表表示。0圖7 14有向圖的十字能益表示示例-.185.

44、-2.十字鏈表的存儲表示與實現(xiàn)(1)十字鏈表存儲結(jié)構(gòu)的類型定義下面分別給出十字鏈弧結(jié)點 定義。struct arcboxinttailvex,headvex;arcbox *hlink,*tlink;intweight;struct olvexnodevtypedata;arcbox*firstin,*firstout;struct olgrapholvexnode *xlist;int vexnum,arcnum;gkind kind;(2)十字鏈表的查找操作函數(shù)int敗則返回int如果將有向圖的鄰接矩陣看成是稀疏矩陣的話，則十字鏈表也可以看成是鄰接矩陣的十 字鏈表存儲結(jié)構(gòu)。在有向圖的十字鏈

45、表表示中，鏈表的頭結(jié)點之間是順序存儲結(jié)構(gòu)，弧結(jié)點 所在的鏈表是非循環(huán)鏈表，結(jié)點之間的相對位置自然形成，不一定按頂點序列號有序。由此 可見，有向圖的十字鏈表表示方式是不唯一的。(arcbox)、頂點結(jié)點(olvexnode)、十字鏈表(olgraph)的類型/弧結(jié)點的結(jié)構(gòu)定義/定義弧尾和弧頭頂點的位置/弧頭相同、弧尾相同的弧的鏈域/定義有向網(wǎng)中弧的權(quán)值頂點結(jié)點結(jié)構(gòu)定義頂點信息/分別指向頂點的第一條入弧和出弧定義十字鏈表類型鏈表頭結(jié)點數(shù)組指針有向圖的頂點數(shù)和弧數(shù)locatevex_olg(olgraph g ,vtype u)返回頂點u在圖g中的位置，如果查找失 0值。locatevex_olg(

46、olgraph g ,vtype u) int i;for(i=0;ig .vexnum;i+) if(g .xlisti.data=u)break;if(ig.vexnum)return(i+1);else return(0); (3)建立十字鏈表的算法實現(xiàn)函數(shù) void creategraph_olg(olgraph& g ,gkind kind)根據(jù)圖的類型 kind 建立一個有向圖 或有向網(wǎng)的十字鏈表 govoid creategraph_olg(olgraph& g,gkind kind) int i,j,k；vtype u,v;arcbox* pr;g.kind=kind;cout

47、g.vexnumg .arcnum;g.xlist=new olvexnodeg .vexnum;為頂點數(shù)組分配內(nèi)存空間cout按某種順序輸入g .vexnum個頂點的值：n;for(i=0;ig.xlisti.data;g.xlisti.firstin=g .xlisti.firstout=null;if(g.kind=dg)cout輸入圖中g(shù).arcnum條弧的信息 u v:n;else cout輸入圖中g(shù).arcnum條弧和權(quán)的信息 u v w:n; for(k=0;kuv; while(!(i=locatevex_olg(g ,u)&(j=locatevex_olg(g ,v);動態(tài)分

48、配弧存儲空間/i從位置值轉(zhuǎn)換為下標值/j從位置值轉(zhuǎn)換為下標值/將輸入的弧插入到相應(yīng)鏈表的首部pr=new arcbox;pr-tailvex=-i;pr-headvex=-j;if(g.kind=dn)cinpr-weight;pr-hlink=g .xlistj.firstin;g.xlistj.firstin=pr;pr-tlink=g .xlisti.firstout;g.xlisti.firstout=pr;/end for(4)顯示十字鏈表信息的操作g的信函數(shù)void displyolg(olgraph g)分別按鄰接表和逆鄰接表方式顯示當(dāng)前十字鏈表 息。void displyolg

49、(olgraph g) int i;arcbox* p;cout按鄰接表顯示結(jié)果為：n;for(i=0;ig .vexnum;i+) p=g.xlisti.firstout;couti (g .xlisti.data):;while(p) couttailvex headvex;if(g .kind=dn)cout weight;couttlink;coutendl;/end forcout按逆鄰接表顯示結(jié)果為：n;for(i=0;ig .vexnum;i+) p=g.xlisti.firstin;couti (g .xlisti.data):;while(p) couttailvex headvex;if(g .kind=dn)cout weight;couthlink;coutendl;/end for(5)程序演示主程序代碼程序中分別建立一個有向圖g1和一個有向網(wǎng)g2的十字鏈表，并按鄰接表和逆鄰接表兩種形式顯示所建立的的十字鏈表的內(nèi)容。void main() olgraph g1,g2;gkind gk1=dg ,gk2=dn;cout