數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)（第二版）課件 第7章 圖

第七章圖西安科技大學(xué)計(jì)算機(jī)學(xué)院張小艷數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)

七橋問(wèn)題7.1圖--基本概念圖論。歐拉把每一塊陸地看成一個(gè)點(diǎn)，連接兩塊陸地的橋用聯(lián)線表示。把它轉(zhuǎn)化成一個(gè)幾何問(wèn)題。七橋問(wèn)題就轉(zhuǎn)化成了是否能用一筆不重復(fù)地畫(huà)出過(guò)此七條線的圖形？142351234圖--基本概念頂點(diǎn)邊弧

圖是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，是由一個(gè)頂點(diǎn)的有窮非空集V(G)和一個(gè)弧或邊的集合E(G)組成。通常記作二元組G

=

(V，E)其中G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中的弧的集合。線性表可以沒(méi)有元素，稱之為空表；樹(shù)中可以沒(méi)有結(jié)點(diǎn)，稱之為空樹(shù)；圖中不能沒(méi)有頂點(diǎn)。圖--圖的定義圖分為無(wú)向圖和有向圖。(a)無(wú)向圖對(duì)于無(wú)向圖G

=

(V，E)，如果(vi，vj)是一條邊，則稱頂點(diǎn)vi，vj互為鄰接點(diǎn)。邊(vi，vj)依附于頂點(diǎn)(vi，vj)。注意：(vi，vj)和(vj，vi)是一條邊。無(wú)向邊用于表示“對(duì)稱關(guān)系”，城市中的雙行道可以用無(wú)向邊表示。

圖(a)圖可以表示為二元組

(V1，E)

V1={1,2,3,4,5}

E=

{（1,2）,(1,4),(2,3),(2,5),(3,5),(3,4)}圖—圖的分類14235(b)有向圖

對(duì)于有向圖G

=

(V，E)，如果

<vi，vj>

是一條弧，

vi稱為弧尾或起始點(diǎn)，vj稱為弧頭(head)或終端點(diǎn)。

弧<vi，vj>

和

弧<vj，vi>

是兩條不同的弧。有向邊用于表示“非對(duì)稱關(guān)系”。城市中的單行道用有向邊表示。圖(b)可以表示為G2

=(V2，A)

V2={1,2,3,4}

A={<1,2>,<1,3>,<3,4>,<4,1>,<4,2>}表示邊的序偶用圓括號(hào)，表示弧的序偶用尖括號(hào)。圖—圖的分類1234

在一個(gè)無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)都有一條直接邊相鄰接，則稱該圖為無(wú)向完全圖?？梢宰C明，在一個(gè)含有n個(gè)頂點(diǎn)的無(wú)向完全圖中，有n(n-1)/2條邊。

在一個(gè)有向圖中，如果任意兩個(gè)頂點(diǎn)之間都有方向互為相反的兩條弧相鄰接，則稱該圖為有向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，有n(n-1)條邊。

若一個(gè)圖接近完全圖，稱為稠密圖；反之稱為稀疏圖。(a)無(wú)向完全圖(b)有向完全圖圖—完全圖加權(quán)邊或加權(quán)弧。帶權(quán)的圖稱為網(wǎng)或網(wǎng)絡(luò)(network)。(a)無(wú)向網(wǎng)(b)有向網(wǎng)圖—權(quán)值和網(wǎng)圖--頂點(diǎn)的度頂點(diǎn)的度(degree)是指依附于某頂點(diǎn)v的邊數(shù)，通常記為T(mén)D(v)。在有向圖中，要區(qū)別頂點(diǎn)的入度與出度的概念。頂點(diǎn)v的入度是指以頂點(diǎn)v為終點(diǎn)的弧的數(shù)目，記為ID(v)；

頂點(diǎn)v的出度是指以頂點(diǎn)v為始點(diǎn)的弧的數(shù)目，記為OD(v)。TD(v)?=?ID(v)?+?OD(v)。頂點(diǎn)1的度是2，頂點(diǎn)2的度為3，頂點(diǎn)3的度為3，頂點(diǎn)4的度是2，頂點(diǎn)5的度為2，所有頂點(diǎn)的度加起來(lái)等12，圖中有6條邊。15432（a）無(wú)向圖G1對(duì)于具有n個(gè)頂點(diǎn)、e條邊的無(wú)向圖：

頂點(diǎn)1的入度為?1，出度為?2；頂點(diǎn)2的入度為2，出度為0；頂點(diǎn)3的入度為1，出度為1；頂點(diǎn)4的入度為1，出度為2；所有頂點(diǎn)的入度之和與出度之和相等，就是邊數(shù)。1432（b）有向圖G2圖--頂點(diǎn)的度圖--路徑和回路無(wú)向圖G?=?(V，E)中：從頂點(diǎn)v到頂點(diǎn)v'?之間的路徑(path)是一個(gè)頂點(diǎn)序列(v?=?vi1，vi2，…，vim?=?v')，其中，(vij，vij+1)是E中的一條邊，1≤j＜m。路徑上邊或弧的數(shù)目稱為路徑長(zhǎng)度。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。V1V6V5V4V3V2132161189235712（a）無(wú)向網(wǎng)v1→v2→v3→v4v1→v6→v4路徑長(zhǎng)度分別為3和2，這兩條路徑都是簡(jiǎn)單路徑。v1→v2→v6→v5→v4是從頂點(diǎn)v1到頂點(diǎn)v4的一條路徑，路徑長(zhǎng)度為4。v5→v1是從頂點(diǎn)v5到頂點(diǎn)v1的一條路徑，路徑長(zhǎng)度為1。這兩條路徑都是簡(jiǎn)單路徑。V3V1V6V5V4V289613215712（b）有向網(wǎng)圖--路徑和回路無(wú)向網(wǎng)(a)中，v1→v2→v6→v5→v1是一條簡(jiǎn)單回路。有向網(wǎng)(b)中，v1→v2→v6→v5→v1也是一條簡(jiǎn)單回路。無(wú)向網(wǎng)(a)中的v1→v2→v6→v4→v2→v1路徑中v2是重復(fù)的，就不是簡(jiǎn)單環(huán)了。V1V6V5V4V3V2132161189235712V3V1V6V5V4V289613215712（a）無(wú)向網(wǎng)（b）有向網(wǎng)路徑中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同時(shí)稱該路徑為回路或者環(huán)(cycle)。除第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)之外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路，或者簡(jiǎn)單環(huán)。圖--路徑和回路圖--子圖對(duì)于圖G?=?(V，E)，存在G'?=?(V'，E')，若存在V'?是V的子集，E'?是E的子集，則稱圖G'?是G的一個(gè)子圖。153214154321542無(wú)向圖G1G1的子圖圖--無(wú)向圖的連通性在無(wú)向圖中，如果從頂點(diǎn)vi到頂點(diǎn)vj(i?≠?j)有路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱該圖是連通圖。15432無(wú)向圖G1來(lái)看這里的無(wú)向圖連通嗎？MLADKJIHGFECB(a)無(wú)向圖G3顯然是不連通的，但是他包含三個(gè)部分，這三部分各自是聯(lián)通的。這三部分可以稱之為原圖的連通分量。MLAJFCBDEKIHG(b)無(wú)向圖G3的三個(gè)連通分量圖--無(wú)向圖的連通性無(wú)向圖的連通分量要滿足三個(gè)條件：

第一：是子圖；

第二：要聯(lián)通；

第三：含有極大頂點(diǎn)數(shù)及依附于這些頂點(diǎn)的所有的邊。所以無(wú)向圖的連通分量也稱之為無(wú)向圖的極大連通子圖圖--無(wú)向圖的連通性圖--有向圖的連通性在有向圖中，若圖中任意一對(duì)頂點(diǎn)vi,vj，從vi到vj有路徑，從vj到vi也有路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。圖(a)的有向圖有兩個(gè)強(qiáng)連通分量，分別是{v1,v3,v4}和{v2}。14322143(a)有向圖(b)連通分量圖--生成樹(shù)和生成森林一個(gè)連通圖的生成樹(shù)是一個(gè)極小的連通子圖，它包含圖中全部的頂點(diǎn)n，但只有足以讓n個(gè)頂點(diǎn)連通的n-1條邊，就是讓N個(gè)頂點(diǎn)連通而無(wú)回路。MLAJFCBMLAJFCB所以，一個(gè)連通圖的生成樹(shù)不止一棵。圖a不連通，有三個(gè)連通分量，就有三棵生成樹(shù)。MLADKJIHGFECBMLAJFCBDEKIHG(a)無(wú)向圖G3(c)無(wú)向圖G3的三個(gè)生成樹(shù)在非連通圖中，由每個(gè)連通分量都可得到一個(gè)極小連通子圖，即一棵生成樹(shù)。這些連通分量的生成樹(shù)就組成了一個(gè)非連通圖的生成森林。圖--生成樹(shù)和生成森林如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹(shù)。圖中v0的入度為0，v1,v2,v3,v4,v5的入度均為1，所以是一棵有向樹(shù)。V3V0V1V5V4V2入度為0的頂點(diǎn)其實(shí)就相當(dāng)于樹(shù)的根結(jié)點(diǎn)，其余頂點(diǎn)入度為1就是說(shuō)樹(shù)的非根結(jié)點(diǎn)的雙親只有一個(gè)。一個(gè)有向圖的生成森林由若干棵有向樹(shù)組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵互不相交的有向樹(shù)的弧。圖--生成樹(shù)和生成森林圖--基本操作在圖中任何一個(gè)頂點(diǎn)都可以被看成是第一個(gè)頂點(diǎn)；任意一個(gè)頂點(diǎn)的鄰接點(diǎn)之間也不存在次序關(guān)系，所以無(wú)法將圖中的頂點(diǎn)排列成一個(gè)唯一的線性序列。為了操作方便，需要將圖中頂點(diǎn)按任意的順序排列起來(lái)(這個(gè)序列是人為規(guī)定的)。所以需明確一個(gè)“頂點(diǎn)在圖中位置”的概念。15432所謂頂點(diǎn)在圖中位置，指的是該頂點(diǎn)在人為規(guī)定的排列中的位置(或序號(hào))。同理，可對(duì)某個(gè)頂點(diǎn)的所有鄰接點(diǎn)進(jìn)行排序，在這個(gè)序列中，自然形成了第一個(gè)鄰接點(diǎn)和第k個(gè)鄰接點(diǎn)。若某個(gè)頂點(diǎn)的鄰接點(diǎn)的個(gè)數(shù)大于k，則稱第k+1個(gè)鄰接點(diǎn)是第k個(gè)鄰接點(diǎn)的下一個(gè)鄰接點(diǎn)，最后一個(gè)鄰接點(diǎn)的下一個(gè)鄰接點(diǎn)為“空”。圖--基本操作假設(shè)頂點(diǎn)的序號(hào)就是存儲(chǔ)位置，按照序號(hào)從小到大排列某個(gè)頂點(diǎn)的鄰接點(diǎn)。頂點(diǎn)1有兩個(gè)鄰接點(diǎn)，4是頂點(diǎn)1相對(duì)于2的下一個(gè)鄰接點(diǎn)；頂點(diǎn)1相對(duì)于4的下一個(gè)鄰接點(diǎn)為空。15432無(wú)向圖G1可以稱2是1的第一個(gè)鄰接點(diǎn)；圖--基本操作的基本操作：(1)頂點(diǎn)定位操作LocateVex(G，v)：在圖G中找到頂點(diǎn)v，返回該頂點(diǎn)在圖中的位置。(2)取頂點(diǎn)操作GetVextex(G，v)：在圖G中找到頂點(diǎn)v，并返回頂點(diǎn)v的相關(guān)信息。(3)求第一個(gè)鄰接點(diǎn)操作FirstAdjVex(G，v)：在圖G中，返回v的第一個(gè)鄰接點(diǎn)。若頂點(diǎn)v在G中沒(méi)有鄰接頂點(diǎn)，則返回“空”。15432無(wú)向圖G1圖--基本操作的基本操作：(1)頂點(diǎn)定位操作LocateVex(G，v)：在圖G中找到頂點(diǎn)v，返回該頂點(diǎn)在圖中的位置。(2)取頂點(diǎn)操作GetVextex(G，v)：在圖G中找到頂點(diǎn)v，并返回頂點(diǎn)v的相關(guān)信息。(3)求第一個(gè)鄰接點(diǎn)操作FirstAdjVex(G，v)：在圖G中，返回v的第一個(gè)鄰接點(diǎn)。若頂點(diǎn)v在G中沒(méi)有鄰接頂點(diǎn)，則返回“空”。(4)求下一個(gè)鄰接點(diǎn)操作NextAdjVex(G，v，w)：在圖G中，返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。15432無(wú)向圖G1圖--基本操作(5)插入頂點(diǎn)操作InsertVex(G，v)：在圖G中增添新頂點(diǎn)v。(6)刪除頂點(diǎn)操作DeleteVex(G，v)：在圖G中，刪除頂點(diǎn)v以及所有和頂點(diǎn)v相關(guān)聯(lián)的邊或弧。(7)插入弧操作InsertArc(G，v，w)：在圖G中增添一條從頂點(diǎn)v到頂點(diǎn)w的邊或弧。(8)刪除弧操作DeleteArc(G，v，w)：在圖G中刪除一條從頂點(diǎn)v到頂點(diǎn)w的邊或弧。(9)深度優(yōu)先遍歷圖DFSTraverse(G，v)：在圖G中，從頂點(diǎn)v出發(fā)按深度優(yōu)先對(duì)圖中每個(gè)結(jié)點(diǎn)訪問(wèn)一遍且僅一遍。(10)廣度優(yōu)先遍歷圖BFSTraverse(G，v)：在圖G中，從頂點(diǎn)v出發(fā)按廣度優(yōu)先對(duì)圖中每個(gè)結(jié)點(diǎn)訪問(wèn)一遍且僅一遍。圖的這10個(gè)基本操作中，5-8操作涉及圖的修改，一般情況下不常用到。7.2圖的存儲(chǔ)結(jié)構(gòu)圖是一種結(jié)構(gòu)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，任意兩個(gè)頂點(diǎn)之間都有可能存在聯(lián)系。MLADKJIHGFECB同學(xué)們，用順序存儲(chǔ)結(jié)構(gòu)可以圖嗎？

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以嗎？7.2圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣圖是一種結(jié)構(gòu)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，任意兩個(gè)頂點(diǎn)之間都有可能存在聯(lián)系。一個(gè)圖的信息包括兩部分：即圖中頂點(diǎn)的信息描述頂點(diǎn)之間的關(guān)系—邊或者弧的信息。MLADKJIHGFECB圖的信息包括兩部分：頂點(diǎn)的信息、頂點(diǎn)之間的關(guān)系(邊或者弧的信息)。分兩部分存儲(chǔ)：

用一維數(shù)組來(lái)存儲(chǔ)頂點(diǎn)信息;

頂點(diǎn)與頂點(diǎn)之間的關(guān)系用二維數(shù)組存儲(chǔ)--鄰接矩陣。V0V2V3V4V1圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣假設(shè)圖G?=?(V，E)，有n個(gè)頂點(diǎn)，即V?=?{v0，v1，…，vn-1}，則表示G中各頂點(diǎn)相鄰關(guān)系為一個(gè)n?×?n的矩陣，將矩陣arcs稱為鄰接矩陣。圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣V0V2V3V4V1(c)鄰接矩陣存儲(chǔ)結(jié)構(gòu)(b)頂點(diǎn)數(shù)組(a)無(wú)向圖圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣在無(wú)向圖中判斷頂點(diǎn)vi到vj是否有邊，只要判斷arcs[i][j]?是否等于1；頂點(diǎn)vi的度就是第i行的元素之和；如果要找頂點(diǎn)vi的所有鄰接點(diǎn)，查找第i行值為1的矩陣元，其所在列的序號(hào)即為其鄰接點(diǎn)的序號(hào)。圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣判斷頂點(diǎn)vi到vj是否有弧，只要判斷arcs[i][j]?是否等于1。每個(gè)頂點(diǎn)的度分出度和入度，如果要找頂點(diǎn)vi的所有鄰接點(diǎn)，查找第i行值為1的矩陣元，其所在列的序號(hào)即為其鄰接點(diǎn)的序號(hào)。V0V2V3V1(c)鄰接矩陣存儲(chǔ)結(jié)構(gòu)(b)頂點(diǎn)數(shù)組(a)無(wú)向圖圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣若G是網(wǎng)，則鄰接矩陣可定義為：若(vi，vj)或<vi，vj>是G的邊或弧若i?=?j反之圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣圖或網(wǎng)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述形式如下：1#defineINFINITY<整數(shù)中允許的最大值>2#defineMAXNODE<圖中頂點(diǎn)的最大個(gè)數(shù)>3typedefcharVertexType;4typedefstruct5{intadj;

6……7}ArcType;/*定義表示無(wú)窮大整數(shù)*//*定義圖中頂點(diǎn)的最大個(gè)數(shù)*//*假設(shè)頂點(diǎn)數(shù)據(jù)為字符型*//*圖：兩頂點(diǎn)相鄰則adj=1，否則adj=0；網(wǎng)：兩頂點(diǎn)相鄰則adj=wij，i=j則adj=0；否則adj=∞*//*其他信息*/8typedefstruct9{VertexTypevertexes[MAXNODE];10ArcTypearcs[MAXNODE][MAXNODE];11intvexnum,arcnum;12}GraphType;/*頂點(diǎn)數(shù)組*//*鄰接矩陣*//*圖的頂點(diǎn)數(shù)和弧數(shù)*/圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣intadj[MAXNODE][MAXNODE]。在實(shí)際應(yīng)用中，如果人們所關(guān)心的只是兩頂點(diǎn)之間是否有邊(或者弧)相連，而不考慮頂點(diǎn)本身的信息，在這種情況下，可以用編號(hào)作為圖中各個(gè)頂點(diǎn)信息，圖或網(wǎng)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)可以簡(jiǎn)單地表示為：圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣圖的鄰接矩陣存儲(chǔ)具有4個(gè)特點(diǎn)：①用鄰接矩陣存儲(chǔ)圖簡(jiǎn)單明了，極易在圖中查找、插入、刪除一條邊或頂點(diǎn)，但要占用O(n2)個(gè)存儲(chǔ)空間(n是頂點(diǎn)數(shù))，無(wú)論圖中實(shí)際含有多少條邊。因此，對(duì)于稀疏圖而言，不適于用鄰接矩陣來(lái)存儲(chǔ)，因?yàn)檫@樣會(huì)造成存儲(chǔ)空間的浪費(fèi)。②無(wú)向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此，在具體存放鄰接矩陣時(shí)只需存放上(或下)三角矩陣的元素即可。③對(duì)于無(wú)向圖或網(wǎng)，鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度TD(vi)。④對(duì)于有向圖或網(wǎng)，鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度OD(vi)(或入度ID(vi))。圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣1intCreateDN(GraphType*G) /*創(chuàng)建一個(gè)有向網(wǎng)*/2{3inti,j,k,weight;4VertexTypev1,v2;5scanf(″%d,%d″,&G->vexnum,&G->arcnum);/*輸入圖的頂點(diǎn)數(shù)和弧數(shù)*/6for(i=0;i<G->vexnum;i++)7for(j=0;j<G->vexnum;j++)8G->arcs[i][j].adj=INFINITY;/*初始化鄰接矩陣*/9for(i=0;i<G->vexnum;i++)10scanf(″%c″,&G->vertexes[i]); /*輸入圖的頂點(diǎn)*/11for(k=0;k<G->arcnum;k++)12{13scanf(″%c,%c,%d″,&v1,&v2,&weight);/*輸入弧的兩個(gè)頂點(diǎn)及權(quán)值*/14i=LocateVex(G,v1);/*定位函數(shù)，時(shí)間復(fù)雜度為O(n)，*/15j=LocateVex(G,v2);/*定位函數(shù)，時(shí)間復(fù)雜度為O(n)，*/16G->arcs[i][j].adj=weight; /*弧上賦權(quán)值*/17}18return(OK);19}基本操作執(zhí)行n2次循環(huán)次數(shù)為e次時(shí)間復(fù)雜度為：O(e?×?n)所以，此算法的時(shí)間復(fù)雜度為：O(n2?+?e?×?n)。圖的存儲(chǔ)結(jié)構(gòu)

--鄰接矩陣v0v1v2v3v401234頂點(diǎn)數(shù)組：（a）無(wú)向圖邊矩陣：（c）鄰接矩陣存儲(chǔ)結(jié)構(gòu)（b）頂點(diǎn)數(shù)組0123401234V0V1V2V3V4圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表V50501005010000012345678∧∧∧12345689序號(hào)datafirstchild對(duì)圖中的每一個(gè)結(jié)點(diǎn)的鄰接點(diǎn)用一個(gè)單鏈表存儲(chǔ)，所有頂點(diǎn)用一個(gè)數(shù)組存放。把這種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法稱為鄰接表。ABCDEFGHIBCDEFGHIA∧∧∧∧∧∧圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表012345678∧∧∧12345689序號(hào)datafirstchild圖的鄰接表存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)完美結(jié)合。順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，在這里充分發(fā)揮了各自的優(yōu)勢(shì)，所以大家要博學(xué)多識(shí)，積累知識(shí)，掌握各種理論與方法，在具體應(yīng)用中才能夠?qū)⑺鶎W(xué)知識(shí)融會(huì)貫通。要善于運(yùn)用事物或人本身所具有的長(zhǎng)處。ABCDEFGHIBCDEFGHIA∧∧∧∧∧∧圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表adjvexnext①圖中的頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)，每個(gè)數(shù)組元素包含兩部分：

一部分用于存儲(chǔ)頂點(diǎn)信息data，一部分用于存放指向該頂點(diǎn)的第一個(gè)鄰接點(diǎn)的指針firstarc。②圖中每個(gè)頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成一個(gè)單鏈表。

若是無(wú)向圖，該鏈表稱為頂點(diǎn)vi的邊表；

若是有向圖，該鏈表稱為頂點(diǎn)vi作為弧尾的出邊表。firstarc如果邊上有其他信息需要保存，可以增加域，比如是網(wǎng)，可以增加權(quán)值weght。adjvexweightnextdata圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表01234^^^1302413datafirstarc02^^413adjvexnextv0v1v2v3v4對(duì)于有n個(gè)頂點(diǎn)、e條邊的無(wú)向圖而言，若采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，則需要n個(gè)表頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。v0v1v2v3v4圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表在無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中，若要獲得某結(jié)點(diǎn)的度，只需要查找這個(gè)頂點(diǎn)的邊表結(jié)點(diǎn)的個(gè)數(shù)即可。若要判斷頂點(diǎn)vi和vj是否存在邊，需要在vi(或vj)的鄰接點(diǎn)單鏈表中查找鄰接點(diǎn)域adjvex是否存在結(jié)點(diǎn)vj(或vi)的下標(biāo)j(或i)。若求頂點(diǎn)的所有鄰接點(diǎn)，就是對(duì)此頂點(diǎn)的鄰接點(diǎn)單鏈表進(jìn)行遍歷，得到的鄰接點(diǎn)域adjvex域?qū)?yīng)的頂點(diǎn)。圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表有向圖0123^123datafirstarc01adjvexnext^^^v0v1v2v3有向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)類似無(wú)向圖，但是要注意有向圖中的弧是有方向的，以頂點(diǎn)為弧尾來(lái)存儲(chǔ)弧。有向圖鄰接表v3v0v1v2圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表有向圖逆鄰接表逆鄰接表中，圖中第i個(gè)頂點(diǎn)的入度等于第i條鏈表中邊結(jié)點(diǎn)的個(gè)數(shù)。0123300datafirstarc2adjvexnext^^v0v1v2v33^^v3v0v1v2圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表對(duì)于網(wǎng)，在邊表結(jié)點(diǎn)上增加一個(gè)權(quán)值weight域，用于存放與邊或弧相關(guān)的信息。當(dāng)然如果邊上有其他的信息需要保存，也可以增加域。adjvexweightnextv0v1v2v3v401234datafirstarcv0v1v2v3v4adjvexweightnext^^^^^1233022645116384032847152137通過(guò)無(wú)向網(wǎng)鄰接表存儲(chǔ)實(shí)例，我們可以看到邊結(jié)點(diǎn)增加的存儲(chǔ)權(quán)值域。圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表#defineMAXNODE＜圖中頂點(diǎn)的最大個(gè)數(shù)＞typedefstructarc {

intadjvex; intweight; structarc*next;}ArcType;typedefstruct{ElemTypedata; ArcType*firstarc; }VertexType; typedefstruct{VertexTypevertexes[MAXNODE];intvexnum,arcnum; }AdjList;/*邊表結(jié)點(diǎn)*//*鄰接點(diǎn)域，存儲(chǔ)鄰接點(diǎn)在表頭結(jié)點(diǎn)表中的位置*//*權(quán)值域，用于存儲(chǔ)邊或弧相關(guān)的信息，非網(wǎng)圖可以不需要*//*鏈域，指向下一鄰接點(diǎn)*//*頂點(diǎn)信息*//*指向第一條依附該頂點(diǎn)的邊或弧的指針*//*頂點(diǎn)表結(jié)點(diǎn)*//*圖中頂點(diǎn)數(shù)和弧數(shù)*/圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表

1#defineMAXNODE302intCreateUDN(AdjList*G)3{4inti,j,k;5intv1,v2;6intn,e;7ArcType*p,*q;8printf(″\n輸入圖中頂點(diǎn)的個(gè)數(shù)n和邊數(shù)e：\n″);9scanf(″%d,%d″,&n,&e,);10G->vexnum=n;11G->arcnum=e;12printf(″\n輸入頂點(diǎn)的信息：\n″);13for(k=0;k<n;k++)14{15scanf(″%d″,&(G->vertexes[k].data));16G->vertexes[k].firstarc=NULL;17}

/*創(chuàng)建一個(gè)無(wú)向圖G*//*輸入圖中的頂點(diǎn)數(shù)和邊數(shù)*/

/*輸入n個(gè)頂點(diǎn)信息*/循環(huán)次數(shù)為n圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表18printf(″\n輸入圖中各邊:\n″)19for(k=0;k<e;k++)20{21scanf(″%d,%d″,&v1,&v2);22i=LocateVex(*G,v1);23j=LocateVex(*G,v2);24q=(ArcType*)malloc(sizeof(ArcType));25q->adjvex=j;26q->next=G->vertexes[i].firstarc;27G->vertexes[i].firstarc=q;28p=(ArcType*)malloc(sizeof(ArcType));29p->adjvex=i;30p->next=G->vertexes[j].firstarc;31G->vertexes[j].firstarc=p;32}33return(1);34}

/*依次讀入e條邊信息，建立邊表*//*讀入邊（v1，v2）*//*查找v1的位置i*//*查找v2的位置i*//*申請(qǐng)結(jié)點(diǎn)q指向*//*鄰接點(diǎn)賦值為j*//*在頂點(diǎn)數(shù)組的第i個(gè)頂點(diǎn)的邊表中插入邊結(jié)點(diǎn)*//*申請(qǐng)結(jié)點(diǎn)p指向*//*鄰接點(diǎn)賦值為i*//*在頂點(diǎn)數(shù)組的第j個(gè)頂點(diǎn)的邊表中插入邊結(jié)點(diǎn)*/該算法時(shí)間復(fù)雜度為O(e?×?n)采用頭插法建立單鏈表鄰接矩陣和鄰接表是兩種最常用的圖的存儲(chǔ)結(jié)構(gòu)，前者適合于圖的靜態(tài)存儲(chǔ)，后者適合于圖的動(dòng)態(tài)存儲(chǔ)。循環(huán)次數(shù)為e時(shí)間復(fù)雜度O(n)時(shí)間復(fù)雜度O(n)圖的存儲(chǔ)結(jié)構(gòu)

--鄰接表7-3圖的深度優(yōu)先遍歷圖的遍歷，是指從圖中的任一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪問(wèn)一次且只訪問(wèn)一次，圖的遍歷有兩種：圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷。圖的遍歷進(jìn)行圖的遍歷時(shí)，需要為圖設(shè)置一個(gè)訪問(wèn)標(biāo)識(shí)數(shù)組:visited[n]，用于表示圖中每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。visited[1~n]=0(“假”)，表示頂點(diǎn)均未被訪問(wèn)；visited[i]=1(“真”)，表示頂點(diǎn)已被訪問(wèn)。V0V2V3V4V12376815設(shè)置訪問(wèn)標(biāo)識(shí)數(shù)組記錄結(jié)點(diǎn)是否被訪問(wèn)過(guò)。這種處理方式是為了讓我們記住來(lái)時(shí)路?！坝浀脕?lái)時(shí)路，繼續(xù)向遠(yuǎn)方”不忘初心砥礪前行。深度優(yōu)先遍歷(depthfirstsearch)類似于樹(shù)的先根遍歷，是樹(shù)先根遍歷的推廣。生成的樹(shù)稱為深度優(yōu)先生成樹(shù)。圖的遍歷

--深度優(yōu)先遍歷ABCGDHEFABDHECFG深度優(yōu)先遍歷的序列為：深度優(yōu)先遍歷圖的算法：(1)訪問(wèn)結(jié)點(diǎn)v；(2)找到v的第一個(gè)鄰接點(diǎn)w；(3)如果鄰接點(diǎn)w存在且未被訪問(wèn)，則從w出發(fā)深度優(yōu)先遍歷圖；否則，結(jié)束；(4)找頂點(diǎn)v關(guān)于w的下一個(gè)鄰接點(diǎn)，轉(zhuǎn)(3)。圖的遍歷

--深度優(yōu)先遍歷9voidDepthFirstSearch(GraphG,intv)10{intw;11visit(v); 12visited[v]=1; 13w=FirstAdjVertex(G,v); 14while(w!=-1) 15{16if(!visited[w])17DepthFirstSearch(G,w); 18w=NextAdjVertex(G,v,w); 19}20}/*深度遍歷v所在的連通子圖*//*訪問(wèn)頂點(diǎn)v*//*置訪問(wèn)標(biāo)識(shí)數(shù)組相應(yīng)分量值*//*找第一個(gè)鄰接點(diǎn)*//*鄰接點(diǎn)存在*//*遞歸調(diào)用DepthFirstSearch*//*找下一個(gè)鄰接點(diǎn)*/圖的遍歷

--深度優(yōu)先遍歷深度優(yōu)先遍歷的序列在存儲(chǔ)結(jié)構(gòu)給定的情況下是唯一的，因?yàn)榇鎯?chǔ)結(jié)構(gòu)給定之后，頂點(diǎn)的存儲(chǔ)位置及鄰接點(diǎn)的排列順序也給定了。對(duì)于非連通圖，只要對(duì)圖中所有的連通分量進(jìn)行深度優(yōu)先遍歷。從一個(gè)頂點(diǎn)開(kāi)始深度優(yōu)先遍歷結(jié)束之后，如果圖中還有未被訪問(wèn)的頂點(diǎn)，就另選一個(gè)沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)作為起點(diǎn)，重復(fù)上述過(guò)程，直到圖中所有頂點(diǎn)都被訪問(wèn)過(guò)。所以圖的遍歷算法在從某一個(gè)頂點(diǎn)出發(fā)深度訪問(wèn)之前需要做一些預(yù)處理：1、訪問(wèn)標(biāo)志數(shù)組初始化；2、找沒(méi)有遍歷的頂點(diǎn)。圖的遍歷

--深度優(yōu)先遍歷intvisited[MAXNUM];1voidTraveGraph(CraphG)2{

3intv;4for(v=0;v<G.vexnum;v++) 5visited[v]=0;6for(v=0;v<G.vexnum;v++)7if(!visited[v])DepthFirstSearch(G,v); 8}/*初始化訪問(wèn)標(biāo)識(shí)數(shù)組*//*找沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)，找到后進(jìn)入深度優(yōu)先*//*調(diào)用深度遍歷算法*//*對(duì)圖G進(jìn)行深度優(yōu)先搜索，Craph是圖的一種存儲(chǔ)結(jié)構(gòu)，如鄰接矩陣表示法或鄰接表*//*訪問(wèn)標(biāo)識(shí)數(shù)組*/圖的遍歷

--深度優(yōu)先遍歷一個(gè)連通圖的生成樹(shù)不唯一。（1）（2）（3）連通圖圖的遍歷

--深度優(yōu)先遍歷對(duì)于非連通圖，每個(gè)連通分量中的頂點(diǎn)集和深度優(yōu)先遍歷時(shí)走過(guò)的邊一起構(gòu)成若干棵深度優(yōu)先遍歷生成樹(shù)，這些連通分量的生成樹(shù)組成非連通圖的深度優(yōu)先遍歷生成森林。第一次從頂點(diǎn)1出發(fā)，深度優(yōu)先遍歷的序列為:1-2-4-3-9；第二次從5出發(fā)，深度優(yōu)先遍歷的序列為:5-6-7；第三次從8出發(fā)，深度優(yōu)先遍歷的序列為:8-10。（1）（2）（3）圖的遍歷

--深度優(yōu)先遍歷7-3-2圖的廣度優(yōu)先遍歷圖的遍歷--廣度優(yōu)先遍歷ACBEFGDHI

廣度優(yōu)先遍歷實(shí)質(zhì)上是從指定頂點(diǎn)出發(fā)，按照到該頂點(diǎn)的路徑長(zhǎng)度由短到長(zhǎng)的順序訪問(wèn)圖中的所有頂點(diǎn)。遍歷時(shí)需要設(shè)立訪問(wèn)標(biāo)識(shí)數(shù)組visited[n]：

visited[i]=0，節(jié)點(diǎn)未被訪問(wèn)；

visited[i]=1，節(jié)點(diǎn)已被訪問(wèn)。在廣度優(yōu)先遍歷中需要設(shè)置一個(gè)隊(duì)列Queue來(lái)記錄訪問(wèn)次序。廣度優(yōu)先遍歷是對(duì)圖進(jìn)行遍歷的另一種常用方法，它類似于樹(shù)的層次遍歷，是樹(shù)的按層次遍歷的推廣，在遍歷過(guò)程中需要用隊(duì)列記錄遍歷過(guò)程中的頂點(diǎn)。圖的遍歷--廣度優(yōu)先遍歷ACBEFGDHI出隊(duì)列入隊(duì)列ABCEFGHDIAABCDEFGHBCDEFGHII廣度優(yōu)先遍歷過(guò)程：在對(duì)連通圖進(jìn)行廣度優(yōu)先遍歷過(guò)程中，連通圖的所有的頂點(diǎn)及廣度優(yōu)先遍歷走過(guò)的邊構(gòu)成了一棵生成樹(shù)，稱為廣度優(yōu)先生成樹(shù)。對(duì)于非連通圖，每個(gè)連通分量中的頂點(diǎn)集和廣度優(yōu)先遍歷時(shí)走過(guò)的邊一起構(gòu)成若干棵廣度優(yōu)先遍歷生成樹(shù)，這些連通分量的生成樹(shù)組成非連通圖的廣度優(yōu)先遍歷生成森林。圖的遍歷--廣度優(yōu)先遍歷ABCDEFGHIABCDEFGHI非連通圖（1）（2）廣度優(yōu)先遍歷算法描述如下：(1)設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問(wèn)，設(shè)置輔助隊(duì)列Q，隊(duì)列Q置空；(2)任選圖中一個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)v作為遍歷起點(diǎn)；(3)訪問(wèn)v(將其訪問(wèn)標(biāo)識(shí)置為已被訪問(wèn)，即visited[v]?=?1)，并且將v入隊(duì)列；(4)若隊(duì)列Q不空，從隊(duì)頭取出一個(gè)頂點(diǎn)v；(5)查找v的所有未訪問(wèn)的鄰接點(diǎn)vi并對(duì)其訪問(wèn)(將其訪問(wèn)標(biāo)識(shí)置為已被訪問(wèn)，即visited[i]?=?1)，并入隊(duì)列，轉(zhuǎn)(4)，直到隊(duì)列Q為空；(6)若此時(shí)圖中還有未被訪問(wèn)過(guò)的頂點(diǎn)，則轉(zhuǎn)(2)；否則，遍歷結(jié)束。圖的遍歷--廣度優(yōu)先遍歷1intvisited[MAXNUM];

2voidBFSTraveGraph(GraphTypeG)3{4intv;5QQTypeQ;

6InitQueue(&Q);

7for(v=0;v<G.vexnum;v++)

8visited[v]=0;9for(v=0;v<G.vexnum;v++)10if(!visited[v])BreadthFirstSearch(G,v);

11}圖的遍歷--廣度優(yōu)先遍歷/*訪問(wèn)標(biāo)識(shí)數(shù)組*//*QQType為隊(duì)列類型標(biāo)識(shí)符*//*初始化隊(duì)列*//*初始化訪問(wèn)標(biāo)識(shí)數(shù)組*//*找沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)，進(jìn)行廣度優(yōu)先調(diào)用深度遍歷算法*/12voidBreadthFirstSearch(GraphTypeg,intv0)13{intv,vj,w;14visit(v0);15visited[v0]=1;16EnterQueue(&Q,v0); 17while(!QueueEmpty(Q))

18{v=DeleteQueue(&Q); 19for(vj=0;vj<n;vj++)20if(!visited[vj]&&g.arcs[v][vj].adj==1)

21{visit(vj);22visited[vj]=1;23EnterQueue(&Q,vj)24}25}26}/*訪問(wèn)v0*//*訪問(wèn)標(biāo)志修改為訪問(wèn)過(guò)*//*v0入隊(duì)列*/圖的遍歷--廣度優(yōu)先遍歷/*循環(huán)判斷隊(duì)列是否為空*//*隊(duì)頭元素出隊(duì)*//*找V的所有鄰接點(diǎn)*//*vj入隊(duì)列*//*若鄰接點(diǎn)存在且沒(méi)有被訪問(wèn)過(guò)*/7-4-1普里姆算法一個(gè)帶權(quán)網(wǎng)，這個(gè)網(wǎng)中v1～v6代表6個(gè)村鎮(zhèn)，聯(lián)線上的數(shù)字就是兩個(gè)村鎮(zhèn)架設(shè)通訊設(shè)施的耗費(fèi)。v1v4v2v3v5v65615366425最小生成樹(shù)

所謂最小成本，就是在這6個(gè)村鎮(zhèn)之間找到5條邊把6個(gè)村鎮(zhèn)連起來(lái)，同時(shí)達(dá)到5條邊上的權(quán)值之和最小。你找到的會(huì)是下面的一個(gè)無(wú)回路的聯(lián)通網(wǎng)，這就是最小生成樹(shù).v1v4v2v3v5v615342最小生成樹(shù)最小生成樹(shù):

一個(gè)無(wú)向連通網(wǎng)，它所有的生成樹(shù)中必有一棵邊的權(quán)值之和最小的生成樹(shù)，我們稱這棵樹(shù)為最小代價(jià)生成樹(shù)，簡(jiǎn)稱最小生成樹(shù)。求最小生成樹(shù)的經(jīng)典算法有兩種：普里姆算法和克魯斯卡爾算法。普里姆(Prim)算法構(gòu)造最小生成樹(shù)：

假定有連通網(wǎng)N?=?(V,E)，其中V為網(wǎng)中所有頂點(diǎn)的集合，E為網(wǎng)中所有帶權(quán)邊的集合。

①設(shè)TE為最小生成樹(shù)中邊的集合，初始化TE為?Φ，引入U(xiǎn)集合，初始化U?集合只包含V中的一個(gè)頂點(diǎn)u0。

②在U集合到V-U集合的所有的邊中選一條代價(jià)最小的邊(u0,v0)。將邊(u0,v0)并入集合TE，同時(shí)將頂點(diǎn)v0并入U(xiǎn)集合。

③重復(fù)②，直到U?=?V為止。 此時(shí)TE中必含有n-1條邊。 頂點(diǎn)集V、邊集為T(mén)E的生成樹(shù)T?=?(V,TE)，就是N的最小生成樹(shù)。

普里姆(Prim)算法也可稱為“加點(diǎn)法”。最小生成樹(shù)

--普里姆(Prim)算法v1v4v2v3v5v6142533425561665v1v2v3v4v5v6v4U={v1}

，V-U集合=?{v2,v3,v4,v5,v6}。U={v1,v3}

，V-U集合=?{v2,v4,v5,v6}。U={v1,v3,v6}

，V-U集合=?{v2,v4,v5}。U={v1,v3,v6,v4}

，V-U集合=?{v2,v5}。U={v1,v3,v6,v4,v2}

，V-U集合=?{v5}。U={v1,v3,v6,v4,v2,v5}

，V-U集合=?{}。U?=?V，找到最小生成樹(shù)最小生成樹(shù)

--普里姆(Prim)算法普里姆(Prim)算法實(shí)現(xiàn)需要設(shè)置一個(gè)輔助數(shù)組closedge[]，定義為一個(gè)結(jié)構(gòu)體：typedefcharVertexType;struct{VertexTypevex;/*U中的頂點(diǎn)*/intlowcost;/*min({cost(vex,v)|vex∈U})*/}closedge[MAXNUM];/*求最小生成樹(shù)時(shí)的輔助數(shù)組*/closedge[]用來(lái)記錄從U集合到V-U集合具有最小代價(jià)的邊。對(duì)每個(gè)V-U集合中的頂點(diǎn)在輔助數(shù)組中存在一個(gè)分量closedge[v]，它包括兩個(gè)域：U中的頂點(diǎn)域vex和邊(u,v)上的耗費(fèi)lowcost，（v,u）是當(dāng)前權(quán)值最小的邊。

closedge[v].lowcost

=

min({cost(u,v)|u∈U}）最小生成樹(shù)

--普里姆(Prim)算法

以鄰接矩陣作為圖的存儲(chǔ)方式來(lái)展示普里姆(Prim)算法的實(shí)現(xiàn)。從頂點(diǎn)u出發(fā)，按普里姆算法構(gòu)造連通網(wǎng)G的最小生成樹(shù)，并輸出生成樹(shù)的每條邊。1MiniTreePrim(GraphTypeG,VertexTypeu)2{intk,i,j,e,k0,mincost;3charu0,v0;4k=LocateVex(G，u); 5closedge[k].lowcost=0;6for(i=0;i<G.vexnum;i++)7if(i!=k)8{closedge[i].vex=u;9closedge[i].lowcost=G.arcs[k][i].adj;10}11for(e=1;e<=G.vexnum-1;e++)

12{mincost=32767;

13k0=0;/*確定u在圖G中的位置*//*初始化U?=?{u}*//*對(duì)V-U中的頂點(diǎn)i，初始化closedge[i]*//*依次找到n-1條邊*/循環(huán)次數(shù)為n/*mincost為一個(gè)比任何邊的權(quán)都要大的數(shù)*/最小生成樹(shù)

--普里姆(Prim)算法14for(j=0;j<G.vexnum;j++) 15if(closedge[j].lowcost!=0&&closedge[j].lowcost<mincost)16{17k0=j; 18mincost=closedge[j].lowcost;19}20u0=closedge[k0].vex;21v0=G.vertexes[k0];22printf(″(%c,%c)\n″,u0,v0);23closedge[k0].lowcost=0; 24for(i=0;i<G.vexnum;i++)25if(G.arcs[k0][i].adj<closedge[i].lowcost)26{closedge[i].lowcost=G.arcs[k0][i].adj;27closedge[i].vex=v0;28}29}30}算法的時(shí)間復(fù)雜度為O(n2)，與網(wǎng)中的邊數(shù)無(wú)關(guān)，適合于求邊稠密的網(wǎng)的最小生成樹(shù)。/*選擇當(dāng)前代價(jià)最小的邊*/循環(huán)次數(shù)為n/*輸出生成樹(shù)的當(dāng)前最小邊*//*將頂點(diǎn)v0并入U(xiǎn)集合*//*在頂點(diǎn)v0并入U(xiǎn)后，更新closedge[i]*//*closedge[k0]中存有當(dāng)前代價(jià)最小的邊*/最小生成樹(shù)

--普里姆(Prim)算法7-4-2克魯斯卡爾算法克魯斯卡爾算法的基本思想是：(1)初始化最小生成樹(shù)的初始狀態(tài)為：

只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V,Φ)；

圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。(2)在邊集E中選擇代價(jià)最小的邊，如果這個(gè)邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則舍去此邊而選擇下一條代價(jià)最小的邊。(3)重復(fù)(2)，直到T中所有的頂點(diǎn)都在同一連通分量上為止。最小生成樹(shù)

--克魯斯卡爾算法克魯斯卡爾算法逐步增加生成樹(shù)的邊，與普里姆算法相比，可稱為“加邊法”。

對(duì)于圖中的連通網(wǎng)，設(shè)N?=?{V,{E}}，最小生成樹(shù)T的初態(tài)中邊集為空，TE=NULL，每個(gè)頂點(diǎn)自成一個(gè)聯(lián)通網(wǎng)。1236541236543151561816361114362011616最小生成樹(shù)

--克魯斯卡爾算法克魯斯卡爾算法是不斷地掃描邊集合，至多對(duì)e條邊各掃描一次，如果用堆來(lái)存放邊，則每次選擇最小邊僅需O(lb?e)的時(shí)間代價(jià)?？梢宰C明，克魯斯卡爾算法的時(shí)間復(fù)雜度為O(elb?e)，它適合于求邊稀疏的網(wǎng)的最小生成樹(shù)。最小生成樹(shù)

--克魯斯卡爾算法在解決問(wèn)題時(shí)不斷刻苦鉆研，獲取最優(yōu)的解決方案，不能滿足于在找到答案。7-5-1迪杰斯特拉算法最短路徑

在實(shí)際生活中經(jīng)常遇到這樣的問(wèn)題，從A城市到B城市有若干條路,需要選擇一條距離最短的路。假如要用計(jì)算機(jī)解決這一問(wèn)題，可以采用網(wǎng)描述交通網(wǎng)絡(luò)。

在圖中頂點(diǎn)表示城市，邊代表城市之間的通路，邊上的權(quán)代表通路的距離。這樣，上述問(wèn)題就變成了在圖中尋找一條從頂點(diǎn)A到頂點(diǎn)B所經(jīng)過(guò)的路徑上權(quán)值累加和最小的路徑。我們把這樣一類問(wèn)題稱為最短路徑問(wèn)題。v0v1v2v3v4v5v620301051291081518最短路徑有兩種最短路徑問(wèn)題：①求某一源點(diǎn)到其余各頂點(diǎn)的最短路徑；②求任意兩頂點(diǎn)間的最短路徑。從源點(diǎn)到終點(diǎn)的路徑可能存在三種情況：①?zèng)]有路徑；②只有一條路徑，則該路徑即為最短路徑；③存在多條路徑，則其中必存在一條最短路徑。v0v1v2v3v4v5v6

有向網(wǎng)G?=?(V，E),求源點(diǎn)v0到其他各頂點(diǎn)的最短路徑。從源點(diǎn)v0到v5沒(méi)有路徑從源點(diǎn)v0到v1只有一條路徑(v0，v1)從源點(diǎn)v0到v4有兩條路徑，其中以長(zhǎng)度為15的路徑(v0，v2，v4)為最短路徑20301051291081518最短路徑--迪杰斯特拉最短路徑--迪杰斯特拉

迪杰斯特拉(Dijkstra)提出了一種按路徑長(zhǎng)度遞增的次序求從源點(diǎn)到各終點(diǎn)的最短路徑的算法。這個(gè)算法就稱為迪杰斯特拉算法

有向網(wǎng)G?=?(V，E)，用鄰接矩陣存儲(chǔ)02030

1009

05

0

01215

010018

v0v1v2v3v4v5v620301051291081518

終點(diǎn)v1v2v3v4v6v5從v0到各終點(diǎn)的最短路徑及最短路徑長(zhǎng)度求解過(guò)程i-1i-2i-3i-4i-5i-6(v0，v1)20(v0，v2)10(v0，v3)30

(v0，v1)20(v0，v3)30(v0,v2

,

v4)15

(v0，v1)20(v0,v2,v4,v3)27(v0,v2,v4,v6)30

(v0,v2,v4,v3)27(v0,v1,v6)29

(v0,v1,v6)29

v0v1v2v3v4v5v602030

1009

05

0

01215

010018

20301051291081518最短路徑--迪杰斯特拉算法實(shí)現(xiàn)過(guò)程中需要記錄依次找到的最短路徑建立一個(gè)集合S，初始時(shí)該集合只有源點(diǎn)v0，然后逐步將已求得最短路徑的頂點(diǎn)加入到集合中。

為了實(shí)現(xiàn)算法，需要引進(jìn)輔助向量dist[]，它的每個(gè)分量dist[i]表示已經(jīng)找到的從開(kāi)始點(diǎn)v0到終點(diǎn)vi的當(dāng)前最短路徑的長(zhǎng)度。它的初態(tài)為：如果從v0到vi有弧，則dist[i]為弧的權(quán)值；否則dist[i]

為∞。最短路徑--迪杰斯特拉v0v1v2v3v4v5v62030105129108151802030

1009

05

0

01215

010018

從dist[]向量中選擇一個(gè)長(zhǎng)度最小的路徑dist[j]此路徑為(v0，vj)。設(shè)下一條最短路徑的終點(diǎn)是vk，這條路徑可能是弧(v0，vk)；可能是：v0到vj，vj到vk，路徑長(zhǎng)度是從v0到vk的弧上的權(quán)值之和。最短路徑--迪杰斯特拉v0v1v2v3v4v5v62030105129108151802030

1009

05

0

01215

010018

dist[i](v0，v2)就是從v0到v2的最短路徑，dist[2]記錄最短路徑長(zhǎng)度10這里我們選擇了(v0，v2)比如：從v0到v4初始值為無(wú)窮大，但是v0經(jīng)過(guò)v2再到v4有路徑，而且路徑長(zhǎng)度是最短的，從v0到v4的路徑為：v0到v2，v2到v4，路徑長(zhǎng)度為15。設(shè)置集合S：用于存放已經(jīng)找到的從v0出發(fā)的最短路徑的終點(diǎn)集合。用鄰接矩陣g表示網(wǎng)(1)S集合初態(tài)只包含一個(gè)頂點(diǎn){v0}；輔助向量dist[i]

=

g.arcs[0][i]。(2)在向量dist中選擇路徑長(zhǎng)度最短的一條路徑，v0到vk的路徑，將vk并入S集合。(3)更新向量dist，使得向量dist中始終記錄從v0出發(fā)到集合V-S上任意一個(gè)頂點(diǎn)vi的最短路徑。判斷V0是否可借助S中的頂點(diǎn)到達(dá)集合V-S上任一頂點(diǎn)vi？如果可達(dá)，且路徑長(zhǎng)度比原來(lái)的短，就修改v0到vi的路徑，修改dist[i]，否則保持原來(lái)的路徑及原來(lái)的dist[i].(4)重復(fù)(2)、(3)步n-1次，逐個(gè)求出v0到圖其他每個(gè)頂點(diǎn)的最短路徑最短路徑--迪杰斯特拉n個(gè)頂點(diǎn)，自然要有循環(huán)做n次循環(huán)n次總的時(shí)間復(fù)雜度是O(n2)。循環(huán)n-1次循環(huán)n次

引入向量P、D、final;

P[v]記錄有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑;若P[v][w]?為1，則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)；D[v]?記錄有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑長(zhǎng)度；final[v]?為1，當(dāng)且僅當(dāng)v∈S，即已經(jīng)求得從v0到v的最短路徑。1voidDijkstra(GraphTypeG,intv0,PathMatrix*P,ShortPathTable*D)2{/*常量INFINITY為邊上權(quán)值可能的最大值*/3for(v=0;v<G.vexnum;++v) /*初始化*/4{5fianl[v]=0; /*v頂點(diǎn)屬于V-S集*/6D[v]=G.arcs[v0][v];/*初始化源點(diǎn)到其他頂點(diǎn)的最短路徑*/7P[v]=0; /*設(shè)空路徑*/8if(D[v]<INFINITY) /*初始化最短路徑上的點(diǎn)*/9P[v]=1;10}11D[v0]=0;final[v0]=1;/*初始化，v0頂點(diǎn)屬于S集*/引入向量P、D、final;

P[v]記錄有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑若P[v][w]?為1，則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)；D[v]?記錄有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑長(zhǎng)度；final[v]?為1，當(dāng)且僅當(dāng)v∈S，即已經(jīng)求得從v0到v的最短路徑。12for(i=1;i<G.vexnum;++i)/*其余G.vexnum-1個(gè)頂點(diǎn)*/13{/*開(kāi)始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集*/14min=INFINITY;/*min為當(dāng)前所知離v0頂點(diǎn)的最近距離*/15for(w=0;w<G.vexnum;++w)/*在v0到其他頂點(diǎn)vi中查找最短路徑*/16if(!final[w]) /*w頂點(diǎn)在V-S中*/17if(D[w]<min)18{v=w;19min=D[w];20}21final[v]=1 /*離v0頂點(diǎn)最近的v加入S集合*/22for(w=0;w>G.vexnum;++w)/*更新當(dāng)前最短路徑*/if(!final[w]&&(min+G.arcs[v][w]<D[w]))/*修改D[w]和P[w]*24{D[w]=min+G.arcs[v][w];25P[w]=P[v];P[w][v]=1;/*P[w]=P[v]+P[w]*/26}}}/*Dijkstra*/算法的運(yùn)行時(shí)間分析：設(shè)圖中有n個(gè)頂點(diǎn)，e條邊。語(yǔ)句3～語(yǔ)句10：for循環(huán)的次數(shù)為n，時(shí)間復(fù)雜度是O(n)。語(yǔ)句12～語(yǔ)句27：for循環(huán)共進(jìn)行n-1次，其中包含兩個(gè)并列的循環(huán)，

語(yǔ)句15～語(yǔ)句20是查找最短路徑，循環(huán)n次；

語(yǔ)句22～語(yǔ)句26是更新當(dāng)前最短路徑，循環(huán)n次。所以總的時(shí)間復(fù)雜度是O(n2)。7-5-2弗洛伊德算法

對(duì)于一個(gè)有向網(wǎng)，求每對(duì)頂點(diǎn)之間的最短路徑，顯然可調(diào)用Dijkstra算法。

具體方法是：每次以不同的頂點(diǎn)為源點(diǎn)，用Dijkstra算法求出從該頂點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行n次這樣的操作，就可得到從每個(gè)頂點(diǎn)到其余頂點(diǎn)的最短路徑。

最短路徑--弗洛伊德算法02030

1009

05

0

01215

010018

v0v1v2v3v4v5v620301051291081518這種方法的時(shí)間復(fù)雜度為O(n3)。574設(shè)用鄰接矩陣表示圖g最短路徑--弗洛伊德算法(1)求圖g中任意一對(duì)頂點(diǎn)vi、vj間的最短路徑。將vi到vj的最短路徑長(zhǎng)度初始化為g.arcs[i][j]，這個(gè)不一定是vi到vj的最短的路徑，需要做n次試探。02030

1009

05

0

01215

010018

v0v1v2v3v4v5v6203010512910815185274(2)在vi、vj間加入頂點(diǎn)v0，判別(vi,v0,vj)是否存在(即判別弧(vi,v0)和(v0,vj)是否存在)。如果存在，比較(vi,v0,vj)和(vi,vj)的路徑長(zhǎng)度，取其中較短的路徑作為vi到vj的且中間頂點(diǎn)號(hào)不大于0的最短路徑。設(shè)用鄰接矩陣表示圖g最短路徑--弗洛伊德算法02030

1009

05

0

01215

010018

v0v1v2v3v4v5v6203010512910815185274(3)再將頂點(diǎn)v1加入vi、vj間，若(vi,…,v1)和(v1,…,vj)分別是中間頂點(diǎn)序號(hào)不大于0的最短路徑，這兩條路徑在上一步中已求出。將(vi,…,v1,…,vj)與上一步已求出的且vi到vj中間頂點(diǎn)號(hào)不大于0的最短路徑比較，取其中較短的路徑作為vi到vj的且中間頂點(diǎn)號(hào)不大于1的最短路徑。(4)繼續(xù)在vi、vj間加入頂點(diǎn)v2、v3v4…..，依次類推，……經(jīng)過(guò)n次比較和修正，在第n步，將求得vi到vj的且中間頂點(diǎn)號(hào)不大于n的最短路徑，這必是從vi到vj的最短路徑。弗羅伊德算法

路徑可直接從鄰接矩陣獲得

vivjcost[i，j]v1中間頂點(diǎn)序號(hào)不大于1的最短路徑

v2中間頂點(diǎn)序號(hào)不大于2的最短路徑

…Vn中間頂點(diǎn)序號(hào)不大于n的最短路徑

圖g中所有頂點(diǎn)偶對(duì)<vi，vj>間的最短路徑長(zhǎng)度對(duì)應(yīng)一個(gè)n階方陣D。依次在<vi，vj>間增加v1,v2,v3……過(guò)程中，方陣D中的值不斷變化，對(duì)應(yīng)一個(gè)n階方陣序列。定義一個(gè)n階方陣序列：

D(-1)，D(0)，D(1)，…，D(k)，…，D(n-1);其中：D(-1)用鄰接矩陣初始化，D(-1)[i][j]?=?G.arcs[i][j]D(k)[i][j]?=?Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}，0≤k≤n-1D(1)[i][j]?是從vi到vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑的長(zhǎng)度；D(k)[i][j]?是從vi到vj的中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長(zhǎng)度；D(n-1)[i][j]?就是從vi到vj的最短路徑的長(zhǎng)度。

最短路徑--弗洛伊德算法

為了能記錄路徑，我們定義一個(gè)方陣P，記錄所有頂點(diǎn)偶對(duì)<vi，vj>間的最短路徑，用它代表對(duì)應(yīng)頂點(diǎn)的最短路徑的前驅(qū)矩陣。方陣P隨著D的變化而變化，所以，P也對(duì)應(yīng)一個(gè)方陣序列：P(-1)，P(0)，P(1)，…，P(k)，…，P(n-1)。P(-1)是初始設(shè)置,P(-1)[i][j]?=?jP(1)[i][j]是從vi到vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑；P(k)[i][j]?是從vi到vj的中間頂點(diǎn)的個(gè)數(shù)不大于k的最短路徑；P(n-1)[i][j]?就是從vi到vj的最短路徑。

最短路徑--弗洛伊德算法

typedefintPathMatrix[MAXVEX][MAXVEX]typedefintDistancMatrix[MAXVEX][MAXVEX]1voidFloyd(GgraphG,PathMatrix*P[],DistancMatrix*D)2{3for(v=0;v<G.vexnum;++v)4for(w=0;w<G.vexnum;++w)5{6D[v][w]=G.arcs[v][w]; 7P[v][w]=w;8}9for(u=0;u<G.vexnum;++u)10for(v=0;v<G.vexnum;++v)11for(w=0;w<G.vexnum;++w)12if(D[v][u]+D[u][w]<D[v][w]) 13{14D[v][w]=D[v][u]+D[u][w];15P[v][w]=P[v][u];16}17}/*初始化DP;*//*先定義兩個(gè)矩陣DP*//*G：帶權(quán)有向圖，P[v][w]為v到w的當(dāng)前最短路徑，D[v][w]記錄路徑長(zhǎng)度*/最短路徑--弗洛伊德算法算法的時(shí)間復(fù)雜度為O(n3)Dijkstra、RobertFloyd這兩位科學(xué)家在計(jì)算機(jī)領(lǐng)域成果斐然，是我們學(xué)習(xí)的榜樣。

通過(guò)樹(shù)立榜樣，學(xué)習(xí)先進(jìn)典型人物，鼓勵(lì)學(xué)生不懈努力、改革創(chuàng)新，思考計(jì)算機(jī)專業(yè)的新的方法和理論，助力科技強(qiáng)國(guó)，并注重新技術(shù)的應(yīng)用轉(zhuǎn)化，提高生產(chǎn)生活效率。7.6有向無(wú)環(huán)圖及其應(yīng)用一個(gè)無(wú)環(huán)的有向圖稱做有向無(wú)環(huán)圖(directedacyclinegraph)，簡(jiǎn)稱DAG圖。DAG圖是一類較有向樹(shù)更一般的特殊有向圖。有向樹(shù)DAG有向示意圖對(duì)于無(wú)向圖來(lái)說(shuō)，若深度優(yōu)先遍歷過(guò)程中遇到回邊(即指向已訪問(wèn)過(guò)的頂點(diǎn)的邊)，則必定存在環(huán)；檢查一個(gè)有向圖是否存在環(huán)要比無(wú)向圖復(fù)雜，因?yàn)檫@條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹(shù)上頂點(diǎn)的弧。但是，如果從有向圖上某個(gè)頂點(diǎn)v出發(fā)的遍歷，在深度優(yōu)先遍歷結(jié)束之前出現(xiàn)一條從頂點(diǎn)u到頂點(diǎn)v的回邊，由于u在生成樹(shù)上是v的子孫，則有向圖必定存在包含頂點(diǎn)v和u的環(huán)有向無(wú)環(huán)圖是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過(guò)程的有效工具。除最簡(jiǎn)單的情況之外，幾乎所有的工程(project)