《數(shù)據(jù)結(jié)構(gòu)與算法》PPT課堂課件-第13章-圖

1、2022/9/151第十三章 圖13.1 圖的定義和術(shù)語圖(Graph)圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)τ邢驁D有向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是有向邊（也稱弧）的有限集合，弧是頂點的有序?qū)Γ洖?，v,w是頂點，v為弧尾，w為弧頭無向圖無向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)?，記?（v,w）或（w,v)，并且（v,w)=(w,v)2022/9/152例

2、245136G1圖G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , 例157324G26圖G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)2022/9/153有向完備圖n個頂點的有向圖最大邊數(shù)是n(n-1)無向完備圖n個頂點的無向圖最大邊數(shù)是n(n-1)/2權(quán)與圖的邊或弧相關(guān)的數(shù)叫網(wǎng)帶權(quán)的圖叫子圖如果圖G(V,E)和圖G(V,E),滿足：VVEE 則稱G為G的子圖頂點的度無向圖中，頂點的度為與每個頂點相連的邊數(shù)有向圖中，頂點的度分成入度與出度入度：以該頂點為頭的

3、弧的數(shù)目出度：以該頂點為尾的弧的數(shù)目路徑路徑是頂點的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1jn)2022/9/154路徑長度沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和回路第一個頂點和最后一個頂點相同的路徑叫簡單路徑序列中頂點不重復(fù)出現(xiàn)的路徑叫簡單回路除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路叫連通從頂點V到頂點W有一條路徑，則說V和W是連通的連通圖圖中任意兩個頂點都是連通的叫連通分量非連通圖的每一個連通部分叫強連通圖有向圖中，如果對每一對Vi,VjV, ViVj,從Vi到Vj 和從Vj到 Vi都存在路徑，則稱G是2022/9/155例213213有向完

4、備圖無向完備圖356例245136圖與子圖例245136G1頂點2入度：1 出度：3頂點4入度：1 出度：0例157324G26頂點5的度：3頂點2的度：42022/9/156例157324G26例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，12022/9/157連通圖例245136強連通圖356例非連通圖連通分量例2451362022/9/15813.2 圖的存儲結(jié)構(gòu)多

5、重鏈表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V32022/9/159鄰接矩陣表示頂點間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個頂點的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣例G12413例15324G22022/9/1510特點：無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存儲空間為n無向圖中頂點Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點Vi的出度是A中第i行元素之和頂點Vi的入度是A中第i列元素之和網(wǎng)絡(luò)的鄰接矩陣可定義為：2022/9/1511例

6、14523753186422022/9/1512鄰接表實現(xiàn)：為圖中每個頂點建立一個單鏈表，第i個單鏈表存放頂點Vi的所有鄰接頂點。2022/9/1513特點無向圖中頂點Vi的度為第i個單鏈表中的結(jié)點數(shù)有向圖中頂點Vi的出度為第i個單鏈表中的結(jié)點個數(shù)頂點Vi的入度為整個單鏈表中鄰接點域值是i的結(jié)點個數(shù)逆鄰接表：有向圖中對每個結(jié)點建立以Vi為終點的邊的單鏈表求解麻煩！例 1 3 11342 2 42022/9/1514 緊縮鄰接表將圖G的每個頂點的鄰接表緊湊地存儲在2個一維數(shù)組List和h中。其中一維數(shù)組List依次存儲頂點1,2,n的鄰接頂點。數(shù)組單元hi存儲頂點i的鄰接表在數(shù)組List中的起始

7、位置。 緊縮鄰接表如圖G2和G1的緊縮鄰接表表示分別如下圖(a)和(b)：2022/9/151513.3 圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止（問題：什么時候會出現(xiàn)這種情況？）V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7類似于：樹的前序遍歷！2022/9/1516V1V2V4V5V3V7V6V8例例V1V2V4V5V

8、3V7V6V8深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V72022/9/1517V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V3 V6 V7 V52022/9/1518深度優(yōu)先遍歷算法遞歸算法開始訪問v,置標志求v鄰接點有鄰接點u求下一鄰接點uvu訪問過結(jié)束NYNYDFS開始標志數(shù)組初始化Vi=1Vi訪問過DFSVi=Vi+1Vi=Vexnums結(jié)束NNYY2022/9/1519V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc 2 7 8 3adjvexne

9、xt55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V42022/9/1520V1V2V4V5V3V7V6V8例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍歷：V1V3 V7 V6 V2 V4 V8 V52022/9/152113.3 圖的遍歷廣度優(yōu)先搜索(BFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接頂點；然后分別從這些鄰接頂點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未

10、被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8類似于：樹的層次遍歷！2022/9/1522V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V82022/9/1523V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V52022/9/1524廣度優(yōu)先遍歷算法開始標志數(shù)組初始化Vi=1Vi訪問過BFSVi=V

11、i+1Vi=Vexnums結(jié)束NNYY2022/9/1525開始訪問v置標志求w鄰接點uu存在嗎w下一鄰接點uu訪問過結(jié)束NYNYBFS初始化隊列v入隊隊列空嗎隊頭w出隊訪問u,置標志u入隊NaaY2022/9/1526例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列：10 1 2 3 4 54fr遍歷序列：1 40 1 2 3 4 54 3fr遍歷序列：1 4 32022/9/1527例1423512341342vexdatafirstarc 5 5 4 3adjvexnex

12、t55 1 5 1 1 4 3 2 20 1 2 3 4 54 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍歷序列：1 4 3 2 52022/9/15280 1 2 3 4 5 2 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 fr遍歷序列：1 4 3 2 5例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 22022/9/152913.4 最短路徑問題提出用

13、帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中：頂點表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中， 各邊上權(quán)值之和最小的一條路徑最短路徑單源最短路徑51643208562301371732913長度最短路徑8131921202022/9/1530Dijkstra算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點的集合（2）V-S=T：尚未確定最短路徑的頂點集合將T中頂點按最短路徑遞增的次序加入到S中，保證：（1）從源點V0到S中各頂點的最短路徑長度都不大于 從V0到T中任何頂點

14、的最短路徑長度 （2）每個頂點對應(yīng)一個距離值 S中頂點：從V0到此頂點的最短路徑長度 T中頂點：從V0到此頂點的只包括S中頂點作中間 頂點的最短路徑長度依據(jù)：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的 直接路徑的權(quán)值；或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和2022/9/1531求最短路徑步驟初使時令 S=V0,T=其余頂點，T中頂點對應(yīng)的距離值若存在，距離值為弧上的權(quán)值若不存在，距離值為從T中選取一個其距離值為最小的頂點W，加入S對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復(fù)上述步驟，直到S中包含所有頂點，即S=V為止

15、2022/9/1532迭代Sudist2dist3dist4dist5初始1-103010011,2210603010021,2,441050309031,2,4,331050306041,2,4,3,55105030602022/9/1533算法描述算法分析：T(n)=O(n)算法實現(xiàn)圖用帶權(quán)鄰接矩陣存儲a 數(shù)組dist存放當前找到的從源點V0到每個終點的最短路徑長度，其初態(tài)為圖中直接路徑權(quán)值數(shù)組pre表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用0作為其前一頂點的序號2022/9/1534所有頂點對之間的最短路徑方法一：每次以一個頂點為源點，重復(fù)執(zhí)行D

16、ijkstra算法n次 T(n)=O(n)方法二： Floyd算法算法思想：逐個頂點試探法求最短路徑步驟初始時設(shè)置一個n階方陣，令其對角線元素為0，若存在弧，則對應(yīng)元素為權(quán)值；否則為逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值所有頂點試探完畢，算法結(jié)束2022/9/1535例ACB2643110 4 116 0 23 0初始：路徑：AB ACBA BCCA0 4 66 0 23 7 0加入B：路徑：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入A：路徑：AB ACBA BCCA CAB0 4 65 0 23 7 0加入C：路徑：A

17、B ABCBCA BCCA CAB0 0 00 0 00 0 0path=0 0 00 0 00 1 0path=0 0 20 0 00 1 0path=0 0 23 0 00 1 0path=2022/9/1536算法實現(xiàn)圖用鄰接矩陣存儲二維數(shù)組c存放最短路徑長度pathij是從Vi到Vj的最短路徑上Vj前一頂點序號算法描述算法分析：T(n)=O(n)實際上，從實現(xiàn)代碼來看： Floyd算法的代碼比用Dijkstra算法要簡明得多！這樣看來， Floyd算法似乎沒帶來更多的好處？！2022/9/153713.5 生成樹生成樹定義：所有頂點均由邊連接在一起，但不存在回路的圖叫說明：一個圖可以有

18、許多棵不同的生成樹所有生成樹具有以下共同特點：生成樹的頂點個數(shù)與圖的頂點個數(shù)相同生成樹是圖的極小連通子圖一個有n個頂點的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個頂點n-1條邊的圖不一定是生成樹GHKI2022/9/1538最小生成樹問題提出要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點表示城市權(quán)城市間建立通信線路所需花費代價希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費的總代價）最小最小代價生成樹問題分析1654327131791812752410n個城市間，最多可設(shè)置n(n-1)/2條線路n個城市間建立通信網(wǎng)，只需n-1條線

19、路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把 所有城市（頂點）均連起來，且總耗費 （各邊權(quán)值之和）最小2022/9/1539最小生成樹性質(zhì)用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。 2022/9/

20、1540MST性質(zhì)證明 圖示 含邊(u,v)的圈假設(shè)G的任何一棵最小生成樹都不含邊(u,v)。將邊(u,v)添加到G的一棵最小生成樹T上，將產(chǎn)生含有邊(u,v)的圈，并且在這個圈上有一條不同于(u,v)的邊(u,v)，使得uU,vV-U，如下圖所示。 將邊(u,v)刪去，得到G的另一棵生成樹T。由于cuvcuv，所以T的耗費T的耗費。于是T是一棵含有邊(u,v)的最小生成樹，這與假設(shè)矛盾。 2022/9/1541構(gòu)造最小生成樹方法方法一：Prim算法算法思想：設(shè)G=(V,E)是連通網(wǎng)，T是N上最小生成樹中邊的集合初始令U=u0,(u0V), T=在所有uU,vV-U的邊(u,v)E中，找一條代

21、價最小的邊(u0,v0)將(u0,v0)并入集合T，同時v0并入U重復(fù)上述操作直至U=V為止，則T=(V, T)為N的最小生成樹算法實現(xiàn)：圖用鄰接矩陣表示算法描述算法評價：T(n)=O(n)2022/9/1542例16543265135664251311631416431421164321425165432142532022/9/1543方法二：Kruskal算法算法思想：設(shè)G=(V,E)，令最小生成樹初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,)，每個頂點自成一個連通分量在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最

22、小的邊依此類推，直至T中所有頂點都在同一連通分量上為止例1654326513566425165432123452022/9/1544算法描述：Prim算法與Kruskal算法的比較 從算法的時間復(fù)雜性看: 當e= (n2)時，Kruskal算法比Prim算法差，但當e= o(n2)時，Kruskal算法卻比Prim算法好得多。算法分析： 設(shè)輸入的連通賦權(quán)圖有e條邊，則將這些邊依其權(quán)值組成優(yōu)先隊列需要O(e)時間；while循環(huán)中，DeleteMin運算需要O(loge)時間，因此關(guān)于優(yōu)先隊列所作運算的時間為O(eloge)。 實現(xiàn)UnionFind所需的時間為O(eloge)。 Kruskal

23、算法所需的計算時間是O(eloge)。2022/9/154513.8 拓撲排序問題提出：學(xué)生選修課程問題頂點表示課程有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)拓撲排序定義AOV網(wǎng)用頂點表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng)若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件2022/9/1546拓撲排序把AOV網(wǎng)絡(luò)中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程叫檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)拓撲排序的方法在有向圖中選一個沒有前驅(qū)的頂點且輸出之從圖中刪除該頂點和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅(qū)的頂點為止2022/9/1547例課程代號 課程名稱 先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10