數(shù)據(jù)結(jié)構(gòu)單元5引例已知城市A有一大型發(fā)電廠，它負(fù)責(zé)向城市B-G共六個(gè)城市輸送電力。各城市間架設(shè)專用輸送管道的代價(jià)左圖所示?，F(xiàn)要建立A向其余城市的電力輸送管道，使總體代價(jià)最小。請(qǐng)問(wèn)：如何建造？引例描述：電力輸送最佳方案思政小課堂在機(jī)遇與挑戰(zhàn)并存的今天，沒(méi)有永遠(yuǎn)的機(jī)遇，只有不斷的努力，而機(jī)遇永遠(yuǎn)屬于有準(zhǔn)備的人。歷史的車輪滾滾向前，一個(gè)國(guó)家，一個(gè)民族的發(fā)展也是在曲折中前進(jìn)。努力奮斗不僅是一個(gè)國(guó)家精神的體現(xiàn)，也是每一個(gè)中國(guó)人的事業(yè)追求的歸宿所在。幸福都是奮斗來(lái)的，不奮斗的人生何止平淡如水。奮斗不僅可以去實(shí)現(xiàn)個(gè)人理想，奮斗更加可以讓我們找到生命的價(jià)值所在。人生有終點(diǎn)，奮斗無(wú)止境。奮斗中常常困難重重，滿布荊棘，我們需要用奮斗的信仰去堅(jiān)持自己的選擇。分析引例分析把引例“電力輸送最佳方案”中的城市看作頂點(diǎn)，各城市間的管道看成弧，管道鋪設(shè)的代價(jià)作為權(quán)值，構(gòu)造一個(gè)有向帶權(quán)圖。求“電力輸送最佳方案”，就是求有向帶權(quán)圖源點(diǎn)A到其余各頂點(diǎn)的最短路徑。引例實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.1圖的概述圖是一種復(fù)雜的非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對(duì)結(jié)點(diǎn)的前驅(qū)和后繼的個(gè)數(shù)沒(méi)有任何限制，結(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個(gè)結(jié)點(diǎn)之間都可能有關(guān)系，也就是說(shuō)圖結(jié)點(diǎn)的關(guān)系是多對(duì)多的。引言IntroductionPart01圖的基本概念圖是由結(jié)點(diǎn)集合和結(jié)點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。記作：G=(V，E)其中，V={x│x∈某個(gè)數(shù)據(jù)元素集合}，E={(x,y)|x,y∈V}。V是有限的非空集合，V中的元素稱為頂點(diǎn)（Vertex）或結(jié)點(diǎn)，E是V中頂點(diǎn)偶對(duì)(x,y)的集合，E中的元素稱為邊（Edge）。圖說(shuō)明圖的基本概念圖的基本概念11示例左圖中，頂點(diǎn)集合V＝{v1,v2,v3,v4,v5}；邊的集合E＝{(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}。無(wú)向圖與有向圖12無(wú)向圖

若圖G中的每條邊都是沒(méi)有方向的，則稱G為無(wú)向圖。無(wú)向圖中邊的表示：無(wú)向圖中的邊均是頂點(diǎn)的無(wú)序?qū)?，無(wú)序?qū)νǔＳ脠A括號(hào)表示，無(wú)序?qū)?x,y)和(y,x)表示圖中的同一條邊。無(wú)向圖若圖G中的每條邊都是有方向的，則稱G為有向圖。有向圖中邊的表示：有向圖中的邊是由頂點(diǎn)的有序?qū)M成，有序?qū)νǔＳ眉饫ㄌ?hào)表示，有序?qū)?lt;x,y>和<y,x>表示的是圖中不同的邊。有向邊也稱為弧，邊的始點(diǎn)稱為弧尾，終點(diǎn)稱為弧頭。有向圖有向圖有向圖13示例左圖中，頂點(diǎn)集合V＝{v1,v2,v3,v4}；邊的集合E＝{<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。①若(x，y)或<y，x>是E(G)中的一條邊，則要求x≠y；②不允許一條邊在圖中重復(fù)出現(xiàn)；③不允許在同一個(gè)圖中既有有向邊又有無(wú)向邊。注意完全圖14無(wú)向圖

若G是具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖，則頂點(diǎn)數(shù)與邊數(shù)的關(guān)系為0≤e≤n(n-1)/2。把恰有n(n-1)/2條邊的無(wú)向圖稱為無(wú)向完全圖。也就是說(shuō)，在無(wú)向完全圖中，任意兩個(gè)頂點(diǎn)之間都有一條邊。無(wú)向完全圖有向圖完全圖15無(wú)向圖若G是具有n個(gè)頂點(diǎn)e條邊的有向圖，則頂點(diǎn)數(shù)與邊數(shù)的關(guān)系為0≤e≤n(n-1)。把恰有n(n-1)條邊的有向圖稱為有向完全圖。也就是說(shuō)，在有向完全圖中，任意兩個(gè)頂點(diǎn)之間有方向相反的兩條邊。有向完全圖有向圖01無(wú)向邊和頂點(diǎn)若(x,y)是一條無(wú)向邊，則稱頂點(diǎn)x和y互為鄰接頂點(diǎn)，或稱x和y相鄰接；并稱(x,y)依附或關(guān)聯(lián)于頂點(diǎn)x和y，或稱(x,y)與頂點(diǎn)x和y相關(guān)聯(lián)。02有向邊和頂點(diǎn)若<x,y>是一條有向邊，則稱頂點(diǎn)x鄰接到y(tǒng)，頂點(diǎn)x鄰接于頂點(diǎn)y；并稱邊<x，y>關(guān)聯(lián)于x和y或稱<x,y>與頂點(diǎn)x和y相關(guān)聯(lián)。邊與頂點(diǎn)的關(guān)系度無(wú)向圖中頂點(diǎn)v的度無(wú)向圖中頂點(diǎn)v的度是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目，記為D(v)。有向圖頂點(diǎn)v的入度有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的入度，記為ID(v)。有向圖頂點(diǎn)v的出度有向圖中，以頂點(diǎn)v為始點(diǎn)的邊的數(shù)目，稱為v的出度，記為OD(v)。有向圖頂點(diǎn)v的度有向圖中，頂點(diǎn)v的度定義為該頂點(diǎn)的入度和出度之和，即D(v)=ID(v)+OD(v)。頂點(diǎn)的度無(wú)論有向圖還是無(wú)向圖，頂點(diǎn)數(shù)n、邊數(shù)e和度數(shù)之間有如下關(guān)系：頂點(diǎn)的度18無(wú)向圖有向圖D(v1)=2，D(v2)=3，D(v3)=3，D(v4)=2，D(v5)=2。ID(v1)=1，OD(v1)=2，D(v1)=3；ID(v2)=1，OD(v2)=0，D(v2)=1；ID(v3)=1，OD(v3)=1，D(v3)=2；ID(v4)=1，OD(v4)=1，D(v4)=2。路徑19無(wú)向圖在無(wú)向圖G中，若存在一個(gè)頂點(diǎn)序列vp，vi1，vi2，…，vim，vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)均屬于E(G)，則稱該序列為頂點(diǎn)vp到vq的一條路徑。無(wú)向圖的路徑有向圖V3V1V2V4V5路徑20無(wú)向圖在有向圖G中，若存在一個(gè)頂點(diǎn)序列vp，vi1，vi2，…，vim，vq，使得有向邊<vp,vi1>，<vi1,vi2>，…，<vim,vq>均屬于E(G)，則稱該序列為頂點(diǎn)vp到vq的一條路徑。有向圖的路徑有向圖V1V2V4V3路徑21路徑長(zhǎng)度定義為該路徑上邊的數(shù)目。起點(diǎn)和終點(diǎn)相同的路徑稱為回路。起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。在一個(gè)有向圖中，若存在一個(gè)頂點(diǎn)v，從該頂點(diǎn)有路徑可以到達(dá)圖中其它所有頂點(diǎn)，則稱此有向圖為有根圖，v稱作圖的根。若一條路徑除兩端頂點(diǎn)可以相同外，其余頂點(diǎn)均不相同，則稱此路徑為一條簡(jiǎn)單路徑。02030104子圖

無(wú)向圖和它的子圖有向圖和它的子圖連通圖和連通分量(a)無(wú)向圖(b)無(wú)向圖的兩個(gè)連通分量①任何連通圖的連通分量只有一個(gè)，即是其自身；②非連通的無(wú)向圖有多個(gè)連通分量。注意在無(wú)向圖G中，若從頂點(diǎn)x到頂點(diǎn)y有路徑，則稱x和y是連通的。若在無(wú)向圖G中，任意兩個(gè)不同的頂點(diǎn)x和y都連通(即有路徑)，則稱G為連通圖。無(wú)向圖G的極大連通子圖稱為G的連通分量。強(qiáng)連通圖和強(qiáng)連通分量有向圖G中，若對(duì)于V中任意兩個(gè)不同的頂點(diǎn)x和y，都存在從x到y(tǒng)以及從y到x的路徑，則稱G是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。(a)有向圖(b)有向圖的兩個(gè)連通分量①?gòu)?qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即是其自身；②非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連分量。注意網(wǎng)絡(luò)有些圖的邊附帶有數(shù)據(jù)信息，這些附帶的數(shù)據(jù)信息稱為權(quán)。第i條邊的權(quán)用符號(hào)wi表示。權(quán)可以表示兩個(gè)頂點(diǎn)之間的距離、花費(fèi)的代價(jià)、所需的時(shí)間等具有某種意義的數(shù)。若將圖的每條邊都賦上一個(gè)權(quán)，則稱這種圖為帶權(quán)圖，也稱為網(wǎng)絡(luò)。Part02圖的抽象數(shù)據(jù)類型描述及定義圖的抽象數(shù)據(jù)類型主要包括兩個(gè)方面：頂點(diǎn)集合和邊集合上的操作。圖上常見(jiàn)的操作有：插入頂點(diǎn)、插入邊、刪除邊、查找、獲取下一個(gè)鄰接點(diǎn)、深度遍歷、廣度遍歷等。圖的抽象數(shù)據(jù)類型描述及定義圖的抽象數(shù)據(jù)類型描述及定義T為泛型，表示圖中數(shù)據(jù)元素的數(shù)據(jù)類型。Java語(yǔ)言約定，T的實(shí)際參數(shù)必須是類，不能是int、double、char等基本數(shù)據(jù)類型，若需表示基本數(shù)據(jù)類型，則須采用基本數(shù)據(jù)類型包裝類，如Integer、Double、Character等。java.util包中的List接口就是線性表，它的實(shí)現(xiàn)子類ArrayList就是順序表，LinkedList就是鏈表。數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.2圖的表示和實(shí)現(xiàn)Part01鄰接矩陣設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，即V={v0,v1,…，vn-1}，那么G的鄰接矩陣是元素具有如下性質(zhì)的n階方陣A，對(duì)于A中的每個(gè)元素aij，滿足：鄰接矩陣圖的鄰接矩陣表示和實(shí)現(xiàn)

圖的鄰接矩陣表示和實(shí)現(xiàn)33無(wú)向圖帶權(quán)網(wǎng)無(wú)向圖在圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)信息使用一維數(shù)組存儲(chǔ)，邊信息的鄰接矩陣使用二維數(shù)組存儲(chǔ)。無(wú)向圖有向圖頂點(diǎn)表鄰接矩陣有向圖圖的鄰接矩陣表示和實(shí)現(xiàn)34在圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)信息使用一維數(shù)組存儲(chǔ)，邊信息的鄰接矩陣使用二維數(shù)組存儲(chǔ)。無(wú)向圖帶權(quán)圖有向圖頂點(diǎn)表有向圖鄰接矩陣有向圖圖的鄰接矩陣表示和實(shí)現(xiàn)35若G是帶權(quán)圖，則鄰接矩陣可定義為：帶權(quán)圖及其鄰接矩陣無(wú)向圖帶權(quán)圖帶權(quán)圖

Part02鄰接表

對(duì)于圖G中的每個(gè)頂點(diǎn)vi，把所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)帶頭結(jié)點(diǎn)的單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表。鄰接表圖的鄰接表表示和實(shí)現(xiàn)鄰接表鄰接表的結(jié)點(diǎn)結(jié)構(gòu)38表結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接表中每個(gè)表結(jié)點(diǎn)均有兩個(gè)域：①鄰接點(diǎn)域dest，存放與vi相鄰接的頂點(diǎn)vj的序號(hào)j；②鏈域next，將鄰接表的所有表結(jié)點(diǎn)鏈在一起。表結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)vi鄰接表的頭結(jié)點(diǎn)包含兩個(gè)域：①頂點(diǎn)域data，存放頂點(diǎn)vi的信息；②指針域adj，vi的鄰接表的頭指針。頭結(jié)點(diǎn)結(jié)構(gòu)圖的鄰接表表示和實(shí)現(xiàn)39無(wú)向圖無(wú)向圖對(duì)于無(wú)向圖，vi的鄰接表中每個(gè)表結(jié)點(diǎn)都對(duì)應(yīng)于與vi相關(guān)聯(lián)的一條邊。因此，將鄰接表的表頭向量稱為頂點(diǎn)表。將無(wú)向圖的鄰接表稱為邊表。有向圖無(wú)向圖及其鄰接表圖的鄰接表表示和實(shí)現(xiàn)40無(wú)向圖對(duì)于有向圖，vi的鄰接表中每個(gè)表結(jié)點(diǎn)都對(duì)應(yīng)于以vi為始點(diǎn)射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。有向圖有向圖及其鄰接表有向圖Part03逆鄰接表

在有向圖中，為圖中每個(gè)頂點(diǎn)vi建立一個(gè)入邊表的方法稱逆鄰接表表示法。入邊表中的每個(gè)表結(jié)點(diǎn)均對(duì)應(yīng)一條以vi為終點(diǎn)的邊。逆鄰接表有向圖的逆鄰接表表示和實(shí)現(xiàn)有向圖及其逆鄰接表數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.3鄰接矩陣圖類Part01鄰接矩陣類的設(shè)計(jì)鄰接矩陣類的設(shè)計(jì)46成員變量構(gòu)造方法成員方法成員變量成員變量構(gòu)造方法構(gòu)造方法鄰接矩陣類的設(shè)計(jì)47成員變量構(gòu)造方法成員方法成員方法鄰接矩陣類的設(shè)計(jì)48成員變量構(gòu)造方法成員方法成員方法Part02鄰接矩陣類的測(cè)試鄰接矩陣圖類AMGraph的測(cè)試【例5-1】以下圖有向帶權(quán)圖為例，編寫(xiě)程序測(cè)試鄰接矩陣類，輸出鄰接矩陣，刪除弧<E,C>，再次輸出鄰接矩陣。弧的設(shè)計(jì)為了測(cè)試程序方便，定義類Edge用來(lái)保存帶權(quán)的邊。Edge類設(shè)計(jì)如下。測(cè)試類52代碼運(yùn)行結(jié)果代碼測(cè)試類53代碼運(yùn)行結(jié)果運(yùn)行結(jié)果數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.4圖的遍歷從圖的某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對(duì)圖中每個(gè)頂點(diǎn)各做一次且僅做一次訪問(wèn)，這一過(guò)程稱為圖的遍歷。圖的遍歷方法主要有2種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。圖的深度優(yōu)先遍歷類似于樹(shù)的先序遍歷，圖的廣度優(yōu)先遍歷類似于樹(shù)的層次遍歷。引言IntroductionPart01深度優(yōu)先遍歷首先訪問(wèn)出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問(wèn)過(guò)；然后依次從v出發(fā)搜索v的每個(gè)鄰接點(diǎn)w。若w未曾訪問(wèn)過(guò)，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)（亦稱為從源點(diǎn)可達(dá)的頂點(diǎn)）均已被訪問(wèn)為止。若此時(shí)圖中仍有未訪問(wèn)的頂點(diǎn)，則另選一個(gè)尚未訪問(wèn)的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)均已被訪問(wèn)為止。圖的深度優(yōu)先遍歷類似于樹(shù)的前序遍歷。采用的搜索方法的特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索。這種搜索方法稱為深度優(yōu)先搜索（Depth-FirstSearch）。相應(yīng)地，用此方法遍歷圖就很自然地稱之為圖的深度優(yōu)先遍歷。遞歸定義說(shuō)明圖的深度優(yōu)先遍歷設(shè)x是當(dāng)前被訪問(wèn)頂點(diǎn)，在對(duì)x做過(guò)訪問(wèn)標(biāo)記后，選擇一條從x出發(fā)的未檢測(cè)過(guò)的邊(x，y)。若發(fā)現(xiàn)頂點(diǎn)y已訪問(wèn)過(guò)，則重新選擇另一條從x出發(fā)的未檢測(cè)過(guò)的邊，否則沿邊(x，y)到達(dá)未曾訪問(wèn)過(guò)的y，對(duì)y訪問(wèn)并將其標(biāo)記為已訪問(wèn)過(guò)；然后從y開(kāi)始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問(wèn)完所有從y出發(fā)可達(dá)的頂點(diǎn)之后，才回溯到頂點(diǎn)x，并且再選擇一條從x出發(fā)的未檢測(cè)過(guò)的邊。上述過(guò)程直至從x出發(fā)的所有邊都已檢測(cè)過(guò)為止。此時(shí)，若x不是源點(diǎn)，則回溯到在x之前被訪問(wèn)過(guò)的頂點(diǎn)；否則圖中所有和源點(diǎn)有路徑相通的頂點(diǎn)（即從源點(diǎn)可達(dá)的所有頂點(diǎn)）都已被訪問(wèn)過(guò)，若圖G是連通圖，則遍歷過(guò)程結(jié)束，否則繼續(xù)選擇一個(gè)尚未被訪問(wèn)的頂點(diǎn)作為新源點(diǎn)，進(jìn)行新的搜索過(guò)程。搜索過(guò)程圖的深度優(yōu)先遍歷深度優(yōu)先遍歷序列為：V1，V2，V3，V4，V5。圖的深度優(yōu)先遍歷算法60遍歷連通分量遍歷圖深度優(yōu)先遍歷測(cè)試61Part02廣度優(yōu)先遍歷首先訪問(wèn)出發(fā)點(diǎn)v，接著依次訪問(wèn)v的所有鄰接點(diǎn)w1，w2，…，wt，然后再依次訪問(wèn)與wl，w2，…，wt鄰接的所有未曾訪問(wèn)過(guò)的頂點(diǎn)。依此類推，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)都已訪問(wèn)到為止。此時(shí)從v開(kāi)始的搜索過(guò)程結(jié)束。若G是連通圖，則遍歷完成；否則，在圖G中另選一個(gè)尚未訪問(wèn)的頂點(diǎn)作為新源點(diǎn)繼續(xù)上述的搜索過(guò)程，直至G中所有頂點(diǎn)均已被訪問(wèn)為止。廣度優(yōu)先遍歷類似于樹(shù)的按層次遍歷。采用的搜索方法的特點(diǎn)是盡可能先對(duì)橫向進(jìn)行搜索，故稱其為廣度優(yōu)先搜索（Breadth-FirstSearch），相應(yīng)的遍歷也就自然地稱為廣度優(yōu)先遍歷。定義說(shuō)明圖的廣度優(yōu)先遍歷在廣度優(yōu)先搜索過(guò)程中，設(shè)x和y是兩個(gè)相繼要被訪問(wèn)的未訪問(wèn)過(guò)的頂點(diǎn)。它們的鄰接點(diǎn)分別記為x1，x2，…，xs和y1，y2，…，yt。為確保先訪問(wèn)的頂點(diǎn)其鄰接點(diǎn)亦先被訪問(wèn)，在搜索過(guò)程中使用FIFO隊(duì)列來(lái)保存已訪問(wèn)過(guò)的頂點(diǎn)。當(dāng)訪問(wèn)x和y時(shí)，這兩個(gè)頂點(diǎn)相繼入隊(duì)。此后，當(dāng)x和y相繼出隊(duì)時(shí)，我們分別從x和y出發(fā)搜索其鄰接點(diǎn)x1，x2，…，xs和y1，y2，…，yt，對(duì)其中未訪者進(jìn)行訪問(wèn)并將其入隊(duì)。這種方法是將每個(gè)已訪問(wèn)的頂點(diǎn)入隊(duì)，故保證了每個(gè)頂點(diǎn)至多只有一次入隊(duì)。搜索過(guò)程圖的廣度優(yōu)先遍歷廣度優(yōu)先遍歷序列為：V1，V2，V3，V4，V5。圖的廣度優(yōu)先遍歷算法65遍歷連通分量遍歷圖廣度優(yōu)先遍歷測(cè)試66數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.5最小生成樹(shù)Part01最小生成樹(shù)概念如果連通圖G的一個(gè)子圖是一棵包含G的所有頂點(diǎn)的樹(shù)，則該子圖稱為G的生成樹(shù)。生成樹(shù)最小生成樹(shù)圖G及其兩棵生成樹(shù)如果無(wú)向連通圖是一個(gè)帶權(quán)圖，那么它的所有生成樹(shù)中必有一棵邊的權(quán)值總和最小的生成樹(shù)，這棵生成樹(shù)稱為最小代價(jià)生成樹(shù)，簡(jiǎn)稱最小生成樹(shù)。最小生成樹(shù)最小生成樹(shù)從最小生成樹(shù)的定義可知，構(gòu)造有n個(gè)頂點(diǎn)的無(wú)向連通帶權(quán)圖的最小生成樹(shù)，必須滿足以下三個(gè)條件：(1)構(gòu)造的最小生成樹(shù)必須包括n個(gè)頂點(diǎn)；(2)構(gòu)造的最小生成樹(shù)中有且僅有n-1條邊；(3)構(gòu)造的最小生成樹(shù)中不能存在回路。說(shuō)明Part02Prim算法Prim算法思想假設(shè)G=(V,E)是一個(gè)無(wú)向帶權(quán)圖，其中V是帶權(quán)圖中頂點(diǎn)的集合，E是邊的權(quán)值集合。設(shè)置兩個(gè)新的集合U和TE，其中U用來(lái)存放帶權(quán)圖G的最小生成樹(shù)的頂點(diǎn)集合，TE用來(lái)存放帶權(quán)圖G的最小生成樹(shù)邊的集合。132+初始化：U={u0},TE={Φ},u0是圖G中任意一個(gè)頂點(diǎn)；+如果U=V，則算法結(jié)束，否則重復(fù)步驟2+在所有u∈U,v∈V-U中，找一條權(quán)值最小的邊(u,v)，并將v加入集合U中，邊(u,v)加入集合TE中。Prim算法步驟【例】對(duì)下面的圖G，使用普里姆算法求最小生成樹(shù)T的執(zhí)行過(guò)程。圖GPrim算法步驟Prim算法步驟Prim算法實(shí)現(xiàn)77頂點(diǎn)定義算法實(shí)現(xiàn)測(cè)試代碼頂點(diǎn)定義利用Prim算法來(lái)構(gòu)造最小生成樹(shù)，最終的生成樹(shù)由n個(gè)頂點(diǎn)以及n-1條邊組成。除了初始頂點(diǎn)外，由n-1次循環(huán)選取操作得到其余n-1個(gè)頂點(diǎn)和n-1條符合條件的邊，每次循環(huán)得到1個(gè)頂點(diǎn)和1條邊。Prim算法實(shí)現(xiàn)78頂點(diǎn)定義算法實(shí)現(xiàn)測(cè)試代碼算法實(shí)現(xiàn)lowCost數(shù)組，用來(lái)保存符合一個(gè)頂點(diǎn)在U，另外一個(gè)頂點(diǎn)在V-U中的邊的權(quán)值每次從lowCost數(shù)組中選取權(quán)值最小的邊修正lowCost中的值Prim算法實(shí)現(xiàn)79頂點(diǎn)定義算法實(shí)現(xiàn)測(cè)試代碼測(cè)試代碼Part03Kruskal算法Kruskal算法思想假設(shè)G=(V,E)是一個(gè)無(wú)向帶權(quán)圖，其中V是帶權(quán)圖中頂點(diǎn)的集合，E是邊的權(quán)值集合。最小生成樹(shù)為T=(V,TE)。重復(fù)步驟(2)直到所有頂點(diǎn)都在同一連通分量上為止。邊長(zhǎng)遞增的順序選擇E中的邊(u,v)加入到T中，要求u、v分屬于T的兩個(gè)連通分量；若u、v是T的當(dāng)前同一個(gè)連通分量中的頂點(diǎn)，則舍去此邊。初始化：T=(V,?)。也就是說(shuō)，最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖。Kruskal算法步驟【例】對(duì)下面的圖G，使用克魯斯卡爾算法求最小生成樹(shù)T的執(zhí)行過(guò)程。圖GKruscal算法步驟Kruscal算法步驟數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.6最短路徑在一個(gè)圖中，若從一個(gè)頂點(diǎn)到另外一個(gè)頂點(diǎn)存在路徑，路徑長(zhǎng)度就是一條路徑上所經(jīng)過(guò)的邊的數(shù)目。圖中從一個(gè)頂點(diǎn)到另外一個(gè)頂點(diǎn)可能存在多條路徑，路徑長(zhǎng)度最短的那條路徑叫做最短路徑，其路徑長(zhǎng)度稱為最短路徑長(zhǎng)度或最短距離。引言IntroductionPart01帶權(quán)圖的最短路徑在一個(gè)帶權(quán)圖中，若從一個(gè)頂點(diǎn)到另外一個(gè)頂點(diǎn)存在一條路徑，則稱該路徑上所經(jīng)過(guò)邊的權(quán)值之和為該路徑上的帶權(quán)路徑長(zhǎng)度。帶權(quán)圖中從一個(gè)頂點(diǎn)到另外一個(gè)頂點(diǎn)可能存在著許多條路徑，帶權(quán)路徑長(zhǎng)度值最小的那條路徑稱為最短路徑，其帶權(quán)路徑長(zhǎng)度叫做最短路徑長(zhǎng)度或最短距離。帶權(quán)圖可以分為有向圖和無(wú)向圖。如果把無(wú)向帶權(quán)圖的每一條邊(u,v)都定義為弧<u,v>和弧<v,u>，則無(wú)向帶權(quán)圖也就可以轉(zhuǎn)換為有向帶權(quán)圖。不失一般性，這里討論有向帶權(quán)圖的最短路徑問(wèn)題。最短路徑說(shuō)明帶權(quán)圖的最短路徑帶權(quán)圖的最短路徑90示例示例左圖所示的有向帶權(quán)圖從頂點(diǎn)A到頂點(diǎn)D有四條路徑，分別是路徑(A,D)，其帶權(quán)路徑長(zhǎng)度為30；路徑(A,C,F,D)，其帶權(quán)路徑長(zhǎng)度為22；路徑(A,C,F,E,D)，其帶權(quán)路徑長(zhǎng)度為34；路徑(A,C,B,E,D)，其帶權(quán)路徑長(zhǎng)度為32。路徑(A,C,F,D)稱為最短路徑，其帶權(quán)路徑長(zhǎng)度22為最短距離。Part02單源最短路徑設(shè)有一個(gè)有向帶權(quán)圖G=(V,E)，其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)，給定V中的一個(gè)頂點(diǎn)，稱為源點(diǎn)（Source），求從源點(diǎn)到所有其他各頂點(diǎn)的最短路徑長(zhǎng)度（長(zhǎng)度是指路徑上各邊權(quán)之和）的問(wèn)題稱為單源最短路徑問(wèn)題（SingleSourceShortestPaths）。

對(duì)于有向帶權(quán)圖從一個(gè)確定頂點(diǎn)（稱為源點(diǎn)）到其余各頂點(diǎn)的最短路徑問(wèn)題，迪杰斯特拉（Dijkstra）提出了一個(gè)按路徑長(zhǎng)度遞增的順序逐步產(chǎn)生最短路徑的構(gòu)造方法。單源最短路徑單源最短路徑基本思想迪杰斯特拉（Dijkstra）算法將頂點(diǎn)集V分成S（開(kāi)始只包含源點(diǎn)s，S包含的點(diǎn)都是已經(jīng)計(jì)算出最短路徑的點(diǎn)）和V-S集合（V-S包含那些未確定最短路徑的點(diǎn)）；如此反復(fù)，直到V-S變空集為止。從V-S中選取這樣一個(gè)頂點(diǎn)w：滿足經(jīng)過(guò)S集合中任意頂點(diǎn)v到w的路徑最短，即滿足{v到w的路徑}最小的那個(gè)w。其中v屬于S，w屬于V-S。將w加入S，并從V-S中移除w；Dijkstra算法步驟【例】用迪杰斯特拉（Dijkstra）算法求下圖G中頂點(diǎn)A到其余各頂點(diǎn)的最短距離。圖GDijkstra算法步驟Dijkstra算