算數(shù)提高課件ds 7

1第七章圖數(shù)據(jù)結(jié)構(gòu)與算法張路

2圖教學(xué)目的：是介紹圖的基本概念、兩種常用的存儲結(jié)構(gòu)、兩種遍歷算法以及圖的基本應(yīng)用。教學(xué)重點(diǎn)：掌握在圖的兩種存儲結(jié)構(gòu)上實現(xiàn)的遍歷算法。教學(xué)難點(diǎn)：圖的應(yīng)用算法，求最短路徑，求關(guān)鍵路徑以及拓?fù)渑判虻取?內(nèi)容提要圖的基本概念存儲表示圖的基本運(yùn)算與周游最小生成樹最短路徑拓?fù)渑判蜿P(guān)鍵路徑4圖的基本概念圖的定義：由頂點(diǎn)的有窮非空集合V和頂點(diǎn)的偶對(邊)集合E組成，記為G=(V，E)，V是結(jié)點(diǎn)(頂點(diǎn))的有窮集合，E是邊的集合，是結(jié)點(diǎn)的偶對圖應(yīng)用廣泛：網(wǎng)絡(luò)布設(shè)，航線管理，交通管理，語言學(xué)等。5有向圖定義：若圖中每條邊都是有方向的，則稱為有向圖。表示：有向圖中的邊是由兩個頂點(diǎn)組成的有序?qū)?，有序?qū)τ眉饫ㄌ柋硎救?lt;vi,vj>表示一條有向邊，vi是邊的始點(diǎn)，vj是邊的終點(diǎn)。<vi,vj>和<vj,vi>代表兩條不同的有向邊。邊<vi,vj>與頂點(diǎn)vi,vj相關(guān)聯(lián)V1V2V3V4有向圖6無向圖定義:若圖中每條邊都是無方向的，則稱為無向圖。表示:無向圖中的邊是由兩個頂點(diǎn)組成的無序?qū)?，無序?qū)τ脠A括號表示無向圖中(vi,vj)和(vj,vi)代表同一條邊。vi和vj是相鄰結(jié)點(diǎn)，(vj,vi)是與頂點(diǎn)vj和vi相關(guān)聯(lián)的邊V1V2V4V5V3無向圖7例子G1為有向圖，其頂點(diǎn)集合和邊集合為：V(G1)={v0,v1,v2}，E(G1)={<v0,v1>,<v1,v0>,<v1,v2>}G2和G3都是無向圖V(G2)={v0,v1,v2,v3}E(G2)={(v0,v1)，(v0,v2)，(v0,v3)，(v1,v2)，(v1,v3)，(v2,v3)}

v0

v1

v2

(G1) (G2) (G3)8特殊的圖線性結(jié)構(gòu)：唯一前驅(qū)，唯一后繼，線性關(guān)系樹形結(jié)構(gòu)：唯一前驅(qū)，多個后繼，層次關(guān)系圖形結(jié)構(gòu)：多對多、任意，網(wǎng)狀關(guān)系9假設(shè)條件下面的討論中，不考慮頂點(diǎn)到其自身的邊，即若(vi,vj)或<vi,vj>是E(G)中的邊，則vi≠vj圖中不允許一條邊重復(fù)出現(xiàn)10圖頂點(diǎn)與邊的關(guān)系圖G的頂點(diǎn)數(shù)n和邊數(shù)e滿足以下關(guān)系：若G是有向圖，則0≤e≤n(n-1)有向完全圖：有n(n-1)條邊的有向圖若G是無向圖，則0≤e≤n(n-1)/2無向完全圖：有n(n-1)/2條邊的無向圖在頂點(diǎn)個數(shù)相同的圖中，完全圖具有最多的邊數(shù)如圖G2就是一個具有4個頂點(diǎn)的無向完全圖，邊數(shù)為:4*(4-1)/2=6

v0

v1

v2

(G1) (G2) (G3)11度定義：與頂點(diǎn)v相關(guān)聯(lián)的邊數(shù)稱為頂點(diǎn)的度，記為D(v)在有向圖中，入度：若G是一個有向圖，則以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的入度，記為ID(v)出度：以v為始點(diǎn)的邊的數(shù)目稱為v的出度，記為OD(v)頂點(diǎn)v的度為其入度和出度之和，即D(v)=ID(v)+OD(v)12圖的頂點(diǎn)、邊數(shù)和度數(shù)之間的關(guān)系如G2中頂點(diǎn)v0的度為3如圖G1中頂點(diǎn)v1的入度為1，出度為2，度為3無論是有向圖還是無向圖，頂點(diǎn)數(shù)n，邊數(shù)e和度數(shù)之間滿足以下關(guān)系：有向圖(G1) (G2)

v0

v0

v1

v1

v2

v2

v3如：G2圖中，邊數(shù)為6，度數(shù)之和為(3+3+3+3)?==n1ii)/2D(veID(vi)=OD(vi)Σi=1nΣi=1n13子圖定義：設(shè)有圖G=(V，E)和G’=(V’，E’)，如果V’是V的子集，E’是E的子集，則稱G’是G的子圖。如下圖給出了有向圖G1的若干子圖。（G1）

v0

v1

v214路徑定義：圖G=(V，E)中，若存在頂點(diǎn)序列vi0,vi1,…,vin，使得(vi0,vi1)，(vi1,vi2)，…，(vin-1,vin)都在E中(若G是有向圖，則使得<vi0,vi1>，<vi1,vi2>，…，<vin-1,vin>都在E中)，則稱從頂點(diǎn)vi0到vin存在一條路徑路徑長度：路徑上的邊數(shù)簡單路徑：若路徑上的頂點(diǎn)除vi0和vin可以相同外，其它頂點(diǎn)都不相同回路或環(huán)：起點(diǎn)和終點(diǎn)相同的簡單路徑15例子如圖G1中頂點(diǎn)序列v0,v1,v0是一長度為2的有向環(huán)G2中頂點(diǎn)序列v0,v1,v2,v3是一條從頂點(diǎn)v0到v3的長度為3的路徑頂點(diǎn)序列v0,v1,v3,v0,v2是一條從頂點(diǎn)v0到v2的長度為4的路徑，但不是簡單路徑頂點(diǎn)序列v0,v1,v3,v0是一長度為3的環(huán)16圖的根有向圖中，若存在一頂點(diǎn)v，從該頂點(diǎn)有路徑可以到圖中其它所有頂點(diǎn)，則稱此有向圖為有根圖，v稱為圖的根顯然，有根圖中的根可能不唯一17無向圖的連通無向圖連通：無向圖G=(V，E)中，若從vi到vj有一條路徑(從vj到vi也一定有一條路徑)，則稱vi和vj是連通的連通圖：若V(G)中任意兩個不同的頂點(diǎn)vi和vj都是連通的(即有路徑)，則稱G為連通圖連通分量：無向圖G中的最大連通子圖（即任意增加G中結(jié)點(diǎn)或邊以后所得到的G的子圖都不再連通）稱為G的連通分量18例子如圖G2和G3都是連通圖H1和H2是G4的兩個連通分量G2G3G4V4V5V6V719有向圖的連通有向圖：強(qiáng)連通圖：有向圖G=(V，E)中，若V(G)中任意兩個不同的頂點(diǎn)vi和vj都存在從vi到vj以及從vj和vi的路徑，則稱圖G是強(qiáng)連通圖強(qiáng)連通分量：有向圖的最大強(qiáng)連通子圖稱為圖的強(qiáng)連通分量強(qiáng)連通圖只有一個強(qiáng)連通分量，就是其自身。非強(qiáng)連通的有向圖有多個強(qiáng)連通分量20例子如左圖G1是非強(qiáng)連通圖它的兩個強(qiáng)連通分量如右圖所示

v0

v2

v1

v0

v1

v221帶權(quán)圖、網(wǎng)絡(luò)若圖的每條邊都賦上一個權(quán)，則稱為帶權(quán)圖帶權(quán)的連通圖稱為網(wǎng)絡(luò)。通常權(quán)是具有某種意義的數(shù)。下圖為一個網(wǎng)絡(luò)。22生成樹對于連通的無向圖或強(qiáng)連通的有向圖，從任一頂點(diǎn)出發(fā)，或是對于有根的有向圖，從圖的根頂點(diǎn)出發(fā)周游，可以訪問到所有的頂點(diǎn)。周游時經(jīng)過的邊加上所有頂點(diǎn)構(gòu)成了圖的一個連通子圖，稱為圖的一個生成樹。連通圖的生成樹是連通圖的一個極小連通子圖，它含有圖中的全部n個頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。23生成樹（續(xù)）如在一棵生成樹中增加一條邊，則必定構(gòu)成環(huán)；如在一棵生成樹中去掉一條邊，則連通圖變?yōu)椴贿B通的；頂點(diǎn)數(shù)為n，邊數(shù)小于n-1的無向圖必定是不連通的；頂點(diǎn)數(shù)為n，邊數(shù)大于n-1的無向圖必定存在環(huán)；頂點(diǎn)數(shù)為n，邊數(shù)為n-1的無向圖不一定是生成樹。24內(nèi)容提要圖的基本概念存儲表示圖的基本運(yùn)算與周游最小生成樹最短路徑拓?fù)渑判蜿P(guān)鍵路徑25圖的存儲圖的結(jié)構(gòu)較復(fù)雜，任意兩個頂點(diǎn)間都可能存在聯(lián)系，因而圖的存儲方法也很多，應(yīng)根據(jù)具體的應(yīng)用和施加的操作選擇圖的存儲表示法鄰接矩陣表示法鄰接表表示法26鄰接矩陣表示法1鄰接矩陣是表示頂點(diǎn)間相鄰關(guān)系的矩陣：頂點(diǎn)信息關(guān)系信息：對稱的n階方陣設(shè)G=(V，E)為具有n個頂點(diǎn)的圖，其鄰接矩陣為具有以下性質(zhì)的n階方陣?íì><><=的邊不是圖或若的邊是圖或若GvvvvGvvvvjiAjijijiji,),(,0,),(,1],[27例子無向圖G5和有向圖G6的鄰接矩陣分別為A1和A228鄰接矩陣表示法2如果G是帶權(quán)的圖，wij是邊(vi,vj)或<vi,vj>的權(quán)，則其鄰接矩陣定義為∶?íì><￥><=的邊不是圖或若或的邊是圖或若GvvvvGvvvvwjiAjijijijiij,),(,0,),(,],[úúúúúú?ùêêêêêê?é=010011010024802065114603085303Aúúúúúú?ùêêêêêê?é￥￥￥￥￥￥￥￥￥=101110248265114638534A29圖的鄰接矩陣存儲結(jié)構(gòu)#defineMAXVEX常數(shù)1 #defineMAXEDGE常數(shù)2typedefcharVexType;typedeffloatAdjType;typedefstruct{

VexTypevexs[MAXVEX]; /*頂點(diǎn)信息*/ AdjTypearcs[MAXVEX][MAXVEX];/*鄰接矩陣*/ intn; /*圖的頂點(diǎn)個數(shù)*/}Graph;30鄰接矩陣的特點(diǎn)無向圖無向圖的鄰接矩陣一定是一個對稱方陣。無向圖的鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)個數(shù)為第i個頂點(diǎn)的度D(vi)。有向圖有向圖的鄰接矩陣的第i行非零元素(或非∞元素)個數(shù)為第i個頂點(diǎn)的出度OD(vi)，第i列非零元素(或非∞元素)個數(shù)就是第i個頂點(diǎn)的入度ID(vi)。鄰接矩陣表示圖，很容易確定圖中任意兩個頂點(diǎn)之間是否有邊相連。31鄰接矩陣的特點(diǎn)鄰接矩陣的存儲代價需要存儲一個包括n結(jié)點(diǎn)的順序表來保存結(jié)點(diǎn)的數(shù)據(jù)或指向結(jié)點(diǎn)的數(shù)據(jù)指針需存儲一個n*n的相鄰矩陣來指示結(jié)點(diǎn)間的關(guān)系有向圖：需n*n個單元來存儲相鄰矩陣O(n2)無向圖：由于相鄰矩陣是對稱的只需存儲相鄰矩陣的下三角部分32鄰接矩陣的特點(diǎn)求解度數(shù)有向圖：矩陣第i行元素值的和是第i個結(jié)點(diǎn)的出度，第i列元素值的和是第i個結(jié)點(diǎn)的入度無向圖：鄰接矩陣第i行（或第i列）元素值的和就是第i個結(jié)點(diǎn)的度數(shù)鄰接矩陣表示法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：各種基本操作都易于實現(xiàn)。缺點(diǎn)：空間浪費(fèi)嚴(yán)重。某些算法時間效率低。33圖的存儲圖的結(jié)構(gòu)較復(fù)雜，任意兩個頂點(diǎn)間都可能存在聯(lián)系，因而圖的存儲方法也很多，應(yīng)根據(jù)具體的應(yīng)用和施加的操作選擇圖的存儲表示法鄰接矩陣表示法鄰接表表示法34鄰接表表示法由順序存儲的頂點(diǎn)表+n個鏈?zhǔn)酱鎯Φ倪叡眄樞虼鎯Φ捻旤c(diǎn)表頂點(diǎn)表存放頂點(diǎn)本身的數(shù)據(jù)信息表中每個表目對應(yīng)于圖的一個頂點(diǎn)，包括兩個字段頂點(diǎn)字段(vertex)存放頂點(diǎn)vi的信息指針字段(edgeList)存放與vi相關(guān)聯(lián)的邊表中的第一個邊結(jié)點(diǎn)的地址vertexedgeList35鄰接表表示法（續(xù)）n個鏈?zhǔn)酱鎯Φ倪叡磉叡碇忻總€邊結(jié)點(diǎn)包括三個字段：相鄰頂點(diǎn)字段(endvex)存放通過本邊與頂點(diǎn)vi相鄰接的頂點(diǎn)vj在頂點(diǎn)表中的位置j權(quán)字段(weight)存放邊結(jié)點(diǎn)所代表的邊的權(quán)值鏈字段(nextedge)指向邊表的下一個邊結(jié)點(diǎn)endvexnextedgeweight36無向圖的表示每條邊(vi,vj)在兩個頂點(diǎn)vi，vj的邊表中都占一個結(jié)點(diǎn)，因此，每條邊在邊表中存儲兩次。頂點(diǎn)vi的邊表中結(jié)點(diǎn)個數(shù)為頂點(diǎn)vi的度無向圖G1的鄰接表

v2v1v0v3省略權(quán)值37有向圖的表示頂點(diǎn)vi的邊表中每個結(jié)點(diǎn)對應(yīng)的是以vi為始點(diǎn)的一條邊，因此，將有向圖鄰接表的邊表稱為出邊表。頂點(diǎn)vi的邊表中結(jié)點(diǎn)個數(shù)為頂點(diǎn)vi的出度也可將表表示示為入邊表38有向圖G2的鄰接表(出邊表）有向圖G2的逆鄰接表（入邊表）

有向圖G2v0v2v4v1v339鄰接表表示法的存儲結(jié)構(gòu)structEdgeNode;typedefstructEdgeNode*PEdgeNode;typedefstructEdgeNode*EdgeList;structEdgeNode{ intendvex; /*相鄰頂點(diǎn)字段*/ AdjTypeweight; /*邊的權(quán)*/ PEdgeNodenextedge; /*鏈字段*/}; /*邊表中的結(jié)點(diǎn)*/typedefstruct{ VexTypevertex; /*頂點(diǎn)信息*/ EdgeListedgelist; /*邊表頭指針*/}VexNode;/*頂點(diǎn)表中的結(jié)點(diǎn)*/typedefstruct{ VexNodevexs[MAXVEX]; intn; /*圖的頂點(diǎn)個數(shù)*/}GraphList;40鄰接表的存儲代價若圖G是無向圖，則圖的鄰接表表示的空間代價為O(n+2e)

若圖G是有向圖，則圖的鄰接表表示的空間代價為O(n+e)41一些基本操作的實現(xiàn)求無向圖中某個頂點(diǎn)的度： 為該結(jié)點(diǎn)所指向的鏈表中的結(jié)點(diǎn)總數(shù)求有向圖的出度： 該結(jié)點(diǎn)所指向的鏈表的結(jié)點(diǎn)總數(shù)求有向圖的入度：必須搜索整個鄰接表才能得到改進(jìn)：增加逆鄰接表42鄰接表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)容易找任一結(jié)點(diǎn)的第一鄰接點(diǎn)和下一個鄰接點(diǎn)；存儲量小。缺點(diǎn)：判定任意兩個結(jié)點(diǎn)之間是否有邊或弧不方便(需要掃描頂點(diǎn)邊表）。43如何選擇合適的存儲方法?鄰接矩陣表示的空間代價只與圖的頂點(diǎn)數(shù)有關(guān)，若圖中邊的數(shù)目小于頂點(diǎn)的數(shù)目，則用鄰接表表示圖比較節(jié)省空間如果e達(dá)到n2數(shù)量級時，由于鄰接表中增加了輔助的鏈域，采用鄰接矩陣表示圖更節(jié)省空間。特別對于無權(quán)圖而言，鄰接矩陣的每個元素只要一個位就可以表示44內(nèi)容提要圖的基本概念存儲表示圖的基本運(yùn)算與周游最小生成樹最短路徑拓?fù)渑判蜿P(guān)鍵路徑45圖的基本運(yùn)算定義圖的基本類型為Graph，圖的頂點(diǎn)類型為Vertex，頂點(diǎn)信息的類型為VexType，圖中邊的類型為Edge圖中的基本運(yùn)算可以定義如下：創(chuàng)建一個空圖

GraphcreatGraph()判斷圖g是否是空圖intisNullGraph(Graphg)把圖g置為空圖voidmakeNullGraph(Graphg)銷毀一個圖g，即釋放圖g占用的空間voiddestroyGraph(Graphg)查找圖中值為value的頂點(diǎn)

VertexsearchVertex(Graphg,VexTypevalue)46圖的基本運(yùn)算在圖g中增加一個值為value的頂點(diǎn)GraphaddVertex(Graphg,VexTypevalue)在圖g中刪除一個頂點(diǎn)和與該頂點(diǎn)相關(guān)聯(lián)的所有邊GraphdeleteVertex(Graphg,Vertexvi)在圖g中刪除/增加一條邊<vi,vj>

GraphdeleteEdge/addEdge(Graphg,Vertexvi,Vertexvj)判斷圖g中是否存在一條指定邊<vi,vj>

intfindEdge(Graphg,Vertexvi,Vertexvj)……

由于不同的應(yīng)用要求，實現(xiàn)的操作有很大差別47圖的周游圖的周游從圖中某一頂點(diǎn)出發(fā)，按照某種方式系統(tǒng)地訪問圖中所有頂點(diǎn)，且使每一個結(jié)點(diǎn)被訪問且僅被訪問一次。也稱為圖的遍歷。連通圖或強(qiáng)連通圖:從圖中任意一頂點(diǎn)出發(fā)都可以訪問圖中所有頂點(diǎn)由于圖中每個頂點(diǎn)都可能與圖中其它多個頂點(diǎn)鄰接并存在回路，為了避免重復(fù)訪問已訪問過的頂點(diǎn)，在圖的周游中，通常對已訪問過的頂點(diǎn)作標(biāo)記。48圖的周游方法深度優(yōu)先周游（Depth_FirstSearch/Traversal，DFS）廣度優(yōu)先周游（Breadth_FirstSearch/Traversal，BFS）49深度優(yōu)先周游具體的思想：從圖的指定頂點(diǎn)v出發(fā)，先訪問頂點(diǎn)v，并將其標(biāo)記為已訪問過然后依次從v未被訪問過的鄰接頂點(diǎn)w出發(fā)進(jìn)行深度優(yōu)先搜索，直到圖中與v相連的所有頂點(diǎn)都被訪問過如果圖中還有未被訪問的頂點(diǎn)，則從另一未被訪問過的頂點(diǎn)出發(fā)重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問過為止50深度優(yōu)先搜索序列對圖進(jìn)行深度優(yōu)先周游時，按訪問頂點(diǎn)的先后次序所得到的頂點(diǎn)序列，稱為該圖的深度優(yōu)先搜索序列，簡稱DFS序列V1出發(fā)深度優(yōu)先搜索序列：V1->V2->V4->V8->V5->V3->V6->V7訪問過的結(jié)點(diǎn)需要特殊標(biāo)志，避免回路。V1V2V3V4V5V8V6V751V7V6V3V2V5V1V8V4V7V6V3V2V5V1V8V4841532721例子_1：V1

v2

v4

v8

v5

v3

v6

v7周游時的訪問路徑周游時的回溯路徑周游時已訪問過的鄰接點(diǎn)52例子_3：已知無向圖及其鄰接表，求DFS序列53voiddFSInList(GraphList*pgraphlist,intvisited[],inti){intj;PEdgeNodep;printf(“node:%c\n”,pgraphlist->vexs[i].vertex);visited[i]=TRUE;p=pgraphlist->vexs[i].edgelist;/*取邊表中的第一個邊結(jié)點(diǎn)*/while(p!=NULL){if(visited[p->endvex]==FALSE)/*未被訪問*/dFSInList(pgraphlist,visited,p->endvex);p=p->nextedge; /*取邊表中的下一個邊結(jié)點(diǎn)*/}}/*從vi出發(fā)進(jìn)行深度優(yōu)先搜索，圖采用鄰接表存儲*/54traverDFS(GraphList*pgraphlist);{intvisited[MAXVEX]; intn; n=pgraphlist->n; for(i=0;i<n;i++) visited[i]=FALSE;/*初始化數(shù)組visited*/ for(i=0;i<n;i++) if(visited[i]==FALSE) dFSInList(pgraphlist,visited,i);

}說明：設(shè)圖有n個頂點(diǎn)，e條邊，若圖是連通圖，則只需調(diào)用dFSInList一次，就可完成圖的深度優(yōu)先周游；否則調(diào)用幾次則表明圖中有幾個連通分量圖的深度優(yōu)先周游55例子_4：已知無向圖的鄰接矩陣，求DFS序列初始化，首先設(shè)置一個數(shù)組visited(大小n=8，為圖中頂點(diǎn)個數(shù))，各元素的初值為FALSE，表示所有頂點(diǎn)均未訪問過。56/*從vi出發(fā)進(jìn)行深度優(yōu)先搜索，圖采用鄰接矩陣表示法*/voiddFSInMatrix(Graph*pGraph,intvisited[],inti){int

j;printf(“node:%c\n”,pGraph->vexs[i]);/*訪問出發(fā)點(diǎn)vi*/visited[i]=TRUE;for(j=0;j<pGraph->n;j++)if((pGraph->arcs[i][j]==1)&&(visited[j]==FALSE))dFSInMatrix(pGraph,visited,j);}57voidtraverDFS(Graph*pGraph){intvisited[MAXVEX];/*初始化數(shù)組visited*/

for(i=0;i<pGraph->n;i++)visited[i]=FALSE;for(i=0;i<n;i++)if(visited[i]==FALSE)dFSInMatrix(pGraph,visited,i);/*if(visited[i]==FALSE)dFSInList(pGraph,visited,i);調(diào)用多少次，表示圖中有多少個連通分量*/}圖的深度優(yōu)先周游58DFS算法分析時間復(fù)雜度：采用鄰接矩陣表示－O(n2)，得到一個頂點(diǎn)的所有鄰接點(diǎn)需要檢查矩陣相應(yīng)行中的n個元素采用鄰接表表示－O(n+e)，檢查一