圖Graph是一種較線(xiàn)性表和樹(shù)更為復(fù)雜的非線(xiàn)性結(jié)構(gòu)在線(xiàn).ppt

1、圖,圖（Graph）是一種較線(xiàn)性表和樹(shù)更為復(fù)雜的非線(xiàn)性結(jié)構(gòu)。在線(xiàn)性結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是線(xiàn)性關(guān)系，除開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)直接前趨和直接后繼。在樹(shù)形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系實(shí)質(zhì)上是層次關(guān)系，同層上的每個(gè)結(jié)點(diǎn)可以和下一層的零個(gè)或多個(gè)結(jié)點(diǎn)（即孩子）相關(guān)，但只能和上一層的一個(gè)結(jié)點(diǎn)（即雙親）相關(guān)（根結(jié)點(diǎn)除外）。然而在圖結(jié)構(gòu)中，對(duì)結(jié)點(diǎn)（圖中常稱(chēng)為頂點(diǎn)）的前趨和后繼個(gè)數(shù)都是不加限制的，即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。由此，圖的應(yīng)用極為廣泛，特別是近年來(lái)的迅速發(fā)展，已滲透到諸如語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。,基本定義和術(shù)語(yǔ),若

2、圖G中的每條邊都是有方向的，則稱(chēng)G為有向圖（Digraph）。在有向圖中，一條有向邊是由兩個(gè)頂點(diǎn)組成的有序?qū)?，有序?qū)νǔＳ眉饫ㄌ?hào)表示。例如，vi，vj表示一條有向邊，vi是邊的始點(diǎn)（起點(diǎn)），vj是邊的終點(diǎn)。因此，vi，vj和vj，vi是兩條不同的有向邊。有向邊也稱(chēng)為?。ˋrc），邊的始點(diǎn)稱(chēng)為弧尾（Tail），終點(diǎn)稱(chēng)為弧頭（Head）。 圖G由兩個(gè)集合V和E組成，記為G(V，E)，其中v是頂點(diǎn)的有窮非空集合，E是V中頂點(diǎn)偶對(duì)（稱(chēng)為邊）的有窮集。通常，也將圖G的頂點(diǎn)集和邊集分別記為V(G)和E(G)。E(G)可以是空集，若E(G)為空，則圖G只有頂點(diǎn)而沒(méi)有邊，稱(chēng)為空?qǐng)D。,若(vi，vj)是一條無(wú)向

3、邊，則稱(chēng)頂點(diǎn)vi和vj互為鄰接點(diǎn)(Adjacent)，或稱(chēng)vi和vj相鄰接；稱(chēng)(vi，vj)關(guān)聯(lián)(Incident)于頂點(diǎn)vi和vj，或稱(chēng)(vi，vj)與頂點(diǎn)vi和vj相關(guān)聯(lián)。如圖7-1中G2，與頂點(diǎn)vl相鄰接的頂點(diǎn)是v2，v3和v4，而關(guān)聯(lián)于頂點(diǎn)v2的邊是(vl，v2)，(v2，v3)和(v2，v4)。若vi，vj是一條有向邊，則稱(chēng)頂點(diǎn)vi鄰接到vj,頂點(diǎn)vj鄰接于頂點(diǎn)vi,并稱(chēng)邊vi，vj關(guān)聯(lián)于vi和vj或稱(chēng)vi，vj與頂點(diǎn)vi和vj相關(guān)聯(lián)。如圖7-1中Gl，關(guān)聯(lián)于頂點(diǎn)v2的邊是v1，v2，v2，vl和v2,v3。 無(wú)向圖中頂點(diǎn)v的度(Degree)是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目，記為D(v)。

4、若G為有向圖，則把以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目，稱(chēng)為v的人度(1ndegree)，記為ID(v)；把以頂點(diǎn)v為始點(diǎn)的邊的數(shù)目，稱(chēng)為v的出度(outdegree)，記為OD(v)；頂點(diǎn)v的度則定義為該頂點(diǎn)的入度和出度之和，即D(v)ID(v)十OD(v)。,在無(wú)向圖G中，若存在一個(gè)頂點(diǎn)序列vp,vi1,vi2，vin，vq，使得(vp，vil)，(vi1,vi2)，(vin，vq)均屬于E(G)，則稱(chēng)頂點(diǎn)vp到vq存在一條路徑(Path)。若G是有向圖，則路徑也是有向的，它由E(G)中的有向邊vp，vil，vil，vi2，vin，vq組成。路徑長(zhǎng)度定義為該路徑上邊的數(shù)目。若一條路徑上除了vp和vq可

5、以相同外；其余頂點(diǎn)均不相同，則稱(chēng)此路徑為一條簡(jiǎn)單路徑。起點(diǎn)和終點(diǎn)相同(vpvq)的簡(jiǎn)單路徑稱(chēng)為簡(jiǎn)單回路或簡(jiǎn)單環(huán)(Cycle)。例如，在圖G2中頂點(diǎn)序列vl,v2，v3，v4是一條從頂點(diǎn)vl到頂點(diǎn)v4的長(zhǎng)度為3的簡(jiǎn)單路徑；頂點(diǎn)序列vl,v2，v4，vl，v3是一條從頂點(diǎn)vl到頂點(diǎn)v3的長(zhǎng)度為4的路徑，但不是簡(jiǎn)單路徑；頂點(diǎn)序列vl，v2，v4，vl是一個(gè)長(zhǎng)度為3的簡(jiǎn)單環(huán)。在有向圖Gl中，頂點(diǎn)序列vl，v2，vl是一個(gè)長(zhǎng)度為2的有向簡(jiǎn)單環(huán)。,在一個(gè)有向圖中，若存在一個(gè)頂點(diǎn)v，從該頂點(diǎn)有路徑可以到達(dá)圖中其它所有頂點(diǎn)，則稱(chēng)此有向圖為有根圖，v稱(chēng)作圖的根。 在無(wú)向圖G中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑(當(dāng)然

6、從vj到vi也一定有路徑)，則稱(chēng)vi和vj是連通的。若V(G)中任意兩個(gè)不同的頂點(diǎn)vi和vj都連通(即有路徑)，則稱(chēng)G為連通圖(Connected Graph)。例如，圖G2和G3是連通圖。 無(wú)向圖G的極大連通子圖稱(chēng)為G的連通分量(connected Component)。顯然，任何連通圖的連通分量只有一個(gè)，即是其自身，而非連通的無(wú)向圖有多個(gè)連通分量。例如，圖7-4中的G4是非連通圖，它有兩個(gè)連通分量Hl和H2。 在有向圖G中，若對(duì)于V(G)中任意兩個(gè)不同的頂點(diǎn)vi和vj，都存在從vi到vj以及從vj到vi的路徑，則稱(chēng)G是強(qiáng)連通圖。有向圖G的極大強(qiáng)連通子圖稱(chēng)為G的強(qiáng)連通分量。顯然，強(qiáng)連通圖只有

7、一個(gè)強(qiáng)連通分量，即是其自身。非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連通分量。例如圖7-1中的Gl不是強(qiáng)連通圖，因?yàn)関3到v2沒(méi)有路徑，但它有兩個(gè)強(qiáng)連通分量，,若將圖的每條邊都賦上一個(gè)權(quán)，則稱(chēng)這種帶權(quán)圖為網(wǎng)絡(luò)(Network)。通常權(quán)是具有某種意義的數(shù).,它們可以表示兩個(gè)頂點(diǎn)之間的距離，耗費(fèi)等,圖的存儲(chǔ)結(jié)構(gòu),鄰接矩陣(Adjacency Matrix)是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G(V，E)是具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣：,用鄰接矩陣表示法表示圖，除了存儲(chǔ)用于表示頂點(diǎn)間相鄰關(guān)系的鄰接矩陣外，通常還需要用一個(gè)順序表來(lái)存儲(chǔ)頂點(diǎn)信息。其形式說(shuō)明如下： # define n 6 / *

8、 圖的頂點(diǎn)數(shù) * / # define e 8 / * 圖的邊（?。?shù) */ typedef char vextype； / * 頂點(diǎn)的數(shù)據(jù)類(lèi)型 * / typedef float adjtype； / * 權(quán)值類(lèi)型 * / typedef struct vextype vexsn； adjtype arcsnn； graph；,若圖中頂點(diǎn)信息是0至n-1的編號(hào)，則僅需令權(quán)值為1，存儲(chǔ)一個(gè)鄰接矩陣就可以表示圖。若是網(wǎng)絡(luò)，則adjtype為權(quán)的類(lèi)型。由于無(wú)向圖或無(wú)向網(wǎng)絡(luò)的鄰接矩陣是對(duì)稱(chēng)的，故可采用壓縮存儲(chǔ)的方法，僅存儲(chǔ)下三角陣(不包括對(duì)角線(xiàn)上的元素)中的元素即可。顯然，鄰接矩陣表示法的空間復(fù)雜度

9、S(n)O(n2)。 CREATGRAPH(ga) * 建立無(wú)向網(wǎng)絡(luò) * Graph * ga； int i，j，k； float w； for(i0；in；i+) ga -vexsigetchar()；* 讀入頂點(diǎn)信息，建立頂點(diǎn)表 * for(i0；in；i+) for(j0；jn；j+) ga -arcsij0； * 鄰接矩陣初始化* for(k0；ke；k+) * 讀入e條邊 * (scanf(”ddf”，&I,&j，&w)；*讀入邊(vi，vj)上的權(quán)w * ga -arcsijw； ga - arcsjiw； *CREATGRAPH * 該算法的執(zhí)行時(shí)間是O(n+n2+e)，其中O(

10、n2)的時(shí)問(wèn)耗費(fèi)在鄰接矩陣的初始化操作上。因?yàn)閑n2，所以，算法的時(shí)間復(fù)雜度是O(n2)。,鄰接表,這種表示法類(lèi)似于樹(shù)的孩子鏈表表示法。 對(duì)于圖G中的每個(gè)頂點(diǎn)vi，該方法把所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱(chēng)為頂點(diǎn)vi的鄰接表(Adjacency List)。鄰接表中每個(gè)表結(jié)點(diǎn)均有兩個(gè)域，其一是鄰接點(diǎn)域(Adjvex)，用以存放與vi相鄰接的頂點(diǎn)vj的序號(hào)；其二是鏈域(Next)，用來(lái)將鄰接表的所有表結(jié)點(diǎn)鏈在一起。并且為每個(gè)頂點(diǎn)vi的鄰接表設(shè)置一個(gè)具有兩個(gè)域的表頭結(jié)點(diǎn)：一個(gè)是頂點(diǎn)域(vertex)，用來(lái)存放頂點(diǎn)vi的信息；另一個(gè)是指針域(Link)，用于存入指向vi的鄰接表中

11、第一個(gè)表結(jié)點(diǎn)的頭指針。為了便于隨機(jī)訪(fǎng)問(wèn)任一頂點(diǎn)的鄰接表，將所有鄰接表的表頭結(jié)點(diǎn)順序存儲(chǔ)在一個(gè)向量中，這樣，圖G就可以由這個(gè)表頭向量來(lái)表示。,建立有向圖的鄰接表與此類(lèi)似，只是更加簡(jiǎn)單，每讀入一個(gè)頂點(diǎn)對(duì)序號(hào)i，j時(shí)，僅需生成十個(gè)鄰接點(diǎn)序號(hào)為j的邊表結(jié)點(diǎn)，將其插入到vi的出邊表頭部即可。若建立網(wǎng)絡(luò)的鄰接表，則需在邊表的每個(gè)結(jié)點(diǎn)中增加一個(gè)存儲(chǔ)邊上權(quán)的數(shù)據(jù)域。 值得注意的是，一個(gè)圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一，這是因?yàn)猷徑颖肀硎局?，各邊表結(jié)點(diǎn)的鏈接次序取決于建立鄰接表的算法以及邊的輸入次序。 鄰接矩陣和鄰接表是圖的兩種最常用的存儲(chǔ)結(jié)構(gòu)，它們各有所長(zhǎng)。下面從空間及執(zhí)行某些常用操作的時(shí)間這兩

12、方面來(lái)作一比較。,在鄰接表(或逆鄰接表)表示中，每個(gè)邊表對(duì)應(yīng)于鄰接矩陣的一行(或一列)，邊表中結(jié)點(diǎn)個(gè)數(shù)等于一行(或一列)中非零元素的個(gè)數(shù)。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的圖G，若G是無(wú)向圖，則它的鄰接表表示中有n個(gè)頂點(diǎn)表結(jié)點(diǎn)和2e個(gè)邊表結(jié)點(diǎn)；若G是有向圖，則它的鄰接表表示或逆鄰接表表示中均有n個(gè)頂點(diǎn)表結(jié)點(diǎn)和e個(gè)邊表結(jié)點(diǎn)。因此鄰接表或逆鄰接表表示的空間復(fù)雜度為S(n，e)O(n+e)。若圖中邊的數(shù)目遠(yuǎn)遠(yuǎn)小于n2(即en2)，此類(lèi)圖稱(chēng)作稀疏圖(Sparse Graph)，這時(shí)用鄰接表表示比用鄰接矩陣表示節(jié)省存儲(chǔ)空間；若e接近于n2 (準(zhǔn)確地說(shuō)，無(wú)向圖e接近于n(n-1)2，有向圖e接近于n(n-1)，

13、此類(lèi)圖稱(chēng)作稠密圖(Dense Graph)，考慮到鄰接表中要附加鏈域，則應(yīng)取鄰接矩陣表示法為宜。,在無(wú)向圖中求頂點(diǎn)的度，鄰接矩陣及鄰接表兩種存儲(chǔ)結(jié)構(gòu)都很容易做到：鄰接矩陣中第i行(或第i列)上非零元素的個(gè)數(shù)即為頂點(diǎn)vi的度；在鄰接表表示中，頂點(diǎn)vi的度則是第i個(gè)邊表中的結(jié)點(diǎn)個(gè)數(shù)。在有向圖中求頂點(diǎn)的度。采用鄰接矩陣表示比鄰接表表示更方便：鄰接矩陣中的第i行上非零元素的個(gè)數(shù)是頂點(diǎn)vi的出度OD(vi)，第i列上非零元素的個(gè)數(shù)是頂點(diǎn)vi的入度ID(vi)，頂點(diǎn)vi的度即是二者之和；在鄰接表表示中，第i個(gè)邊表(即出邊表)上的結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)vi的出度，求vi的入度較困難，需遍歷各頂點(diǎn)的邊表。若有向圖采用

14、逆鄰接表表示，則與鄰接表表示相反，求頂點(diǎn)的入度容易，而求頂點(diǎn)出度較難。 在鄰接矩陣表示中，很容易判定(vi，vj)或vi，vj是否是圖的一條邊，只要判定矩陣中的第i行第j列上的那個(gè)元素是否為零即可；但是在鄰接表表示中，需掃描第i個(gè)邊表，最壞情況下要耗費(fèi)O(n)時(shí)間。 在鄰接矩陣中求邊的數(shù)目e，必須檢測(cè)整個(gè)矩陣，所耗費(fèi)的時(shí)間是0(n2)，與e的大小無(wú)關(guān)；而在鄰接表表示中，只要對(duì)每個(gè)邊表的結(jié)點(diǎn)個(gè)數(shù)計(jì)數(shù)即可求得e，所耗費(fèi)的時(shí)間是0(e+n)。因此，當(dāng)en2時(shí)，采用鄰接表表示更節(jié)省時(shí)間。,圖的遍歷,和樹(shù)的遍歷類(lèi)似，圖的遍歷也是從某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對(duì)圖中所有頂點(diǎn)各作一次訪(fǎng)問(wèn)。若給定的圖是連通

15、圖，則從圖中任一頂點(diǎn)出發(fā)順著邊可以訪(fǎng)問(wèn)到該圖的所有頂點(diǎn)。然而，圖的遍歷比樹(shù)的遍歷復(fù)雜得多，這是因?yàn)閳D中的任一頂點(diǎn)都可能和其余頂點(diǎn)相鄰接，故在訪(fǎng)問(wèn)了某個(gè)頂點(diǎn)之后，可能順著某條回路又回到了該頂點(diǎn)。為了避免重復(fù)訪(fǎng)問(wèn)同一個(gè)頂點(diǎn)，必須記住每個(gè)頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)。為此，可設(shè)置一個(gè)布爾向量visitedn，它的初值為false，一旦訪(fǎng)問(wèn)了頂點(diǎn)vi，便將visitedi-1置為T(mén)RUE。,深度優(yōu)先搜索(Depth-First-Search)遍歷類(lèi)似于樹(shù)的前序遍歷。假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未訪(fǎng)問(wèn)過(guò)，在G中任選一頂點(diǎn)vi為初始出發(fā)點(diǎn)，則深度優(yōu)先搜索可定義如下：首先，訪(fǎng)問(wèn)出發(fā)點(diǎn)vi，并將其標(biāo)記為已訪(fǎng)問(wèn)過(guò)，然后，

16、依次從vi出發(fā)搜索vi的每一個(gè)鄰接點(diǎn)vj,若vj未曾訪(fǎng)問(wèn)過(guò)，則以vj為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索。顯然上述搜索法是遞歸定義的，它的特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索，故稱(chēng)之為深度優(yōu)先搜索。例如，設(shè)x是剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，按深度優(yōu)先搜索方法，下一步將選擇一條從x出發(fā)的未檢測(cè)過(guò)的邊(x，y)。若發(fā)現(xiàn)頂點(diǎn)y已被訪(fǎng)問(wèn)過(guò)，則重新選擇另一條從x出發(fā)的未檢測(cè)過(guò)的邊。若發(fā)現(xiàn)頂點(diǎn)y未曾訪(fǎng)問(wèn)過(guò)，則沿此邊從x到達(dá)y，訪(fǎng)問(wèn)y并將其標(biāo)記為已訪(fǎng)問(wèn)過(guò)，然后從y開(kāi)始搜索，直到搜索完從y出發(fā)的所有路徑，才回溯到頂點(diǎn)x，然后再選擇一條從x出發(fā)的未檢測(cè)過(guò)的邊。上述過(guò)程直至從x出發(fā)的所有邊都已檢測(cè)過(guò)為止。此時(shí)，若x不是初始出發(fā)點(diǎn)，則回

17、溯到在x之前被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)；若x是初始出發(fā)點(diǎn)，則整個(gè)搜索過(guò)程結(jié)束。顯然這時(shí)圖G中所有和初始出發(fā)點(diǎn)有路徑相通的頂點(diǎn)都已被訪(fǎng)問(wèn)過(guò)。因此，若G是連通圖，則從初始出發(fā)點(diǎn)開(kāi)始的搜索過(guò)程結(jié)束，也就意味著完成了對(duì)圖G的遍歷。,在該存儲(chǔ)結(jié)構(gòu)上執(zhí)行DFS算法的過(guò)程如下：設(shè)初始出發(fā)點(diǎn)是v1，則DFS（0）的執(zhí)行結(jié)果是訪(fǎng)問(wèn)v1，將其置上已訪(fǎng)問(wèn)標(biāo)記，從v1搜索到的第1個(gè)鄰接點(diǎn)是v2，因v2未曾訪(fǎng)問(wèn)過(guò)，故調(diào)用DFS(1)。執(zhí)行DFS(1)，首先訪(fǎng)問(wèn)v2，將其標(biāo)記為已訪(fǎng)問(wèn)過(guò)，然后從v2搜索到的第1個(gè)鄰接點(diǎn)是vl，但vl已訪(fǎng)問(wèn)過(guò)，故繼續(xù)搜索到第2個(gè)鄰接點(diǎn)v4，v4未曾訪(fǎng)過(guò)，因此調(diào)用DFS(3)。類(lèi)似地分析，訪(fǎng)問(wèn)v4后調(diào)用D

18、FS(7)，訪(fǎng)問(wèn)v：后調(diào)用DPS(4)。執(zhí)行DFS(4)時(shí)，在訪(fǎng)問(wèn)v5并作標(biāo)記后，從v5搜索到的兩個(gè)鄰接點(diǎn)依次是v2和v8，因?yàn)樗鼈兙驯辉L(fǎng)問(wèn)過(guò)，所以DFS(4)執(zhí)行結(jié)束返回，回溯到v8。又因?yàn)関8的兩個(gè)鄰接點(diǎn)已搜索過(guò)，故DFS(7)亦結(jié)束返回，回溯到v4。類(lèi)似地由v4回溯到v2。V2的鄰接點(diǎn)vl和v4已搜索過(guò)，但v2的第3個(gè)鄰接點(diǎn)v5還尚未搜索，故接下來(lái)由v2搜索到v5，但因?yàn)関5已訪(fǎng)問(wèn)過(guò)，所以DFS(1)也結(jié)束返回，回溯到vl。vl的第1個(gè)鄰接點(diǎn)已搜索過(guò)，故繼續(xù)從v1搜索到第2個(gè)鄰接點(diǎn)v3，因?yàn)関3未曾訪(fǎng)問(wèn)過(guò)，故調(diào)用DFS(2)。類(lèi)似地依次訪(fǎng)問(wèn)v3，v6，v7后，又由v7依次回溯到v6，v

19、3，vl。此時(shí)，vl的所有鄰接點(diǎn)都已搜索過(guò)，故DFS(0)執(zhí)行完畢。,寬度優(yōu)先搜索法,寬度優(yōu)先搜索(Breadth-First-Search)遍歷類(lèi)似于樹(shù)的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪(fǎng)問(wèn)過(guò)，在G中任選一頂點(diǎn)2為初始出發(fā)點(diǎn)，則寬度優(yōu)先搜索的基本思想是：首先訪(fǎng)問(wèn)出發(fā)點(diǎn)Vi，接著依次訪(fǎng)問(wèn)vi的所有鄰接點(diǎn)wl，w2，wt，然后，再依次訪(fǎng)問(wèn)與wl，w2，wt鄰接的所有未曾訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，依此類(lèi)推，直至圖中所有和初始出發(fā)點(diǎn)v有路徑相通的頂點(diǎn)都已訪(fǎng)問(wèn)到為止。此時(shí)，從vi開(kāi)始的搜索過(guò)程結(jié)束，若G是連通圖則遍歷完成。 顯然，上述搜索法的特點(diǎn)是盡可能先對(duì)橫向進(jìn)行搜索，故稱(chēng)之為寬度優(yōu)先搜索。設(shè)x和y是兩個(gè)

20、相繼被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，若當(dāng)前是以x為出發(fā)點(diǎn)進(jìn)行搜索，則在訪(fǎng)問(wèn)x的所有未曾訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)之后，緊接著是以y為出發(fā)點(diǎn)進(jìn)行橫向搜索，并對(duì)搜索到的y的鄰接點(diǎn)中尚未被訪(fǎng)問(wèn)的頂點(diǎn)進(jìn)行訪(fǎng)問(wèn)。也就是說(shuō)，先訪(fǎng)問(wèn)的頂點(diǎn)其鄰接點(diǎn)亦先被訪(fǎng)問(wèn)。為此，需引進(jìn)隊(duì)列保存已訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。,最小生成樹(shù),圖的生成樹(shù)不是唯一的，從不同的頂點(diǎn)出發(fā)進(jìn)行遍歷，可以得到不同的生成樹(shù)。對(duì)于連通網(wǎng)絡(luò)G(V，E)，邊是帶權(quán)的，因而G的生成樹(shù)的各邊也是帶權(quán)的。我們把生成樹(shù)各邊的權(quán)值總和稱(chēng)為生成樹(shù)的權(quán)，并把權(quán)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)(Minimun Spanning Tree)。 生成樹(shù)和最小生成樹(shù)有許多重要的應(yīng)用。令圖G的頂點(diǎn)表示城市，邊表示連

21、接兩個(gè)城市之間的通訊線(xiàn)路。n個(gè)城市之間最多可設(shè)立的線(xiàn)路有n(n-1)2條，把n個(gè)城市連接起來(lái)至少要有n-1條線(xiàn)路，則圖G的生成樹(shù)表示了建立通訊網(wǎng)絡(luò)的可行方案。如果給圖中的邊都賦予權(quán)，而這些權(quán)可表示兩個(gè)城市之間通訊線(xiàn)路的長(zhǎng)度或建造代價(jià)，那么，如何選擇n-1條線(xiàn)路，使得建立的通訊網(wǎng)絡(luò)其線(xiàn)路的總長(zhǎng)度最短或總代價(jià)最小呢?這就是要構(gòu)造該圖的一棵最小生成樹(shù)。,以下我們只討論無(wú)向圖的最小生成樹(shù)問(wèn)題。構(gòu)造最小生成樹(shù)可以有多種算法，其中大多數(shù)構(gòu)造算法都是利用了最小生成樹(shù)的下述性質(zhì)：設(shè)G(V，E)是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)真子集。若(u，v)是G中所有的一個(gè)端點(diǎn)在U(即uU)里、另一個(gè)端點(diǎn)不在U(即vV-

22、U)里的邊中，具有最小權(quán)值的一條邊，則一定存在G的一棵最小生成樹(shù)包含此邊(u，v)。這個(gè)性質(zhì)稱(chēng)為MST性質(zhì)。MST性質(zhì)可用反證法證明：假設(shè)G的任何一棵最小生成樹(shù)中都不含邊(u，v)。設(shè)T是G的一棵最小生成樹(shù)，但不包含邊(u，v)。由于T是樹(shù)，且是連通的，因此有一條從u到v的路徑；且該路徑上必有一條連接兩個(gè)頂點(diǎn)集U和V-U的邊(u，v)，其中uU，vV-U，否則u和v不連通。當(dāng)把邊(u，v)加入樹(shù)T時(shí)，得到一個(gè)含有邊(u，v)的回路，見(jiàn)圖7-15。刪去邊(u，v)，上述回路即被消除，由此得到另一棵生成樹(shù)T，T和T的區(qū)別僅在于用邊(u，v)取代了T中的邊(u，v)。因?yàn)?u，v)的權(quán)(u，v)的權(quán)

23、，故T的權(quán)T的權(quán)，因此T也是G的最小生成樹(shù)，它包含邊(u，v)，與假設(shè)矛盾!,假設(shè)G(V，E)是連通網(wǎng)絡(luò)，為簡(jiǎn)單起見(jiàn)，我們用序號(hào)1至n來(lái)表示頂點(diǎn)集合，即v1，2，n。設(shè)所求的最小生成樹(shù)為T(mén)(U，TE)，其中U是T的頂點(diǎn)集，TE是T的邊集。并且將G中邊上的權(quán)看做是長(zhǎng)度。 Prim算法的基本思想是：首先從v中任取一個(gè)頂點(diǎn)u0，將生成樹(shù)T置為僅有一個(gè)結(jié)點(diǎn)u0的樹(shù)，即置Uu0；然后只要U是V的真子集，就在所有那些其一個(gè)端點(diǎn)u己在T(即uU)、另一個(gè)端點(diǎn)v還未在T(即vVU)的邊中，找一條最短(即權(quán)最小)的邊(u，v)，并把該條邊(u，v)和其不在T中的頂點(diǎn)v，分別并入T的邊集TE和頂點(diǎn)集U。如此進(jìn)行下

24、去，每次往生成樹(shù)里并入一個(gè)頂點(diǎn)和一條邊，直到把所有頂點(diǎn)都包括進(jìn)生成樹(shù)T為止。此時(shí)，必有UV，TE中有n-1條邊。MST性質(zhì)保證上述過(guò)程求得的T(U，TE)是G的一棵最小生成樹(shù)。 顯然，Prim算法的關(guān)鍵是如何找到連接U和V-U的最短邊來(lái)擴(kuò)充生成樹(shù)T。為直觀(guān)解釋方便，設(shè)想在構(gòu)造過(guò)程中，T的頂點(diǎn)集U中頂點(diǎn)和邊集TE中的邊均被涂成紅色，U之外的頂點(diǎn)集V-U中的頂點(diǎn)均被涂成藍(lán)色，連接紅點(diǎn)和藍(lán)點(diǎn)的邊均被涂成紫色，那么最短紫邊就是連接U和V-U的最短邊。,最短路徑,交通網(wǎng)絡(luò)中常常提出這樣的問(wèn)題：從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短? 交通網(wǎng)絡(luò)可用帶權(quán)圖來(lái)表示。頂點(diǎn)表示城市名稱(chēng)

25、，邊表示兩個(gè)城市有路連通，邊上權(quán)值可表示兩城市之間的距離、交通費(fèi)或途中所花費(fèi)的時(shí)間等。求兩個(gè)頂點(diǎn)之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。 另外，若兩個(gè)頂點(diǎn)之間沒(méi)有邊，則認(rèn)為兩個(gè)頂點(diǎn)無(wú)通路，但有可能有間接通路（從其他頂點(diǎn)達(dá)到)）。路徑上的開(kāi)始頂點(diǎn)(出發(fā)點(diǎn))稱(chēng)為源點(diǎn)，路徑上的最后一個(gè)頂點(diǎn)稱(chēng)為終點(diǎn)，并假定討論的權(quán)值不能為負(fù)數(shù)。,所有頂點(diǎn)對(duì)之間的最短路徑,所有頂點(diǎn)對(duì)之間的最短路徑是指：對(duì)于給定的有向網(wǎng)G=(V,E)，要對(duì)G中任意一對(duì)頂點(diǎn)有序?qū)、W(VW)，找出V到W的最短距離和W到V的最短距離。解決此問(wèn)題的一個(gè)有效方法是:輪流以每一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行迪杰斯特拉算

26、法n次，即可求得每一對(duì)頂點(diǎn)之間的最短路徑,總的時(shí)間復(fù)雜度為O(n3)。,弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣costn+1n+1來(lái)存儲(chǔ)帶權(quán)有向圖。算法的基本思想是:設(shè)置一個(gè)nxn的矩陣A(k)，其中除對(duì)角線(xiàn)的元素都等于0外，其他元素a(k)ij表示頂點(diǎn)i到頂點(diǎn)j的路徑長(zhǎng)度，K表示運(yùn)算步驟。開(kāi)始時(shí)，以任意兩個(gè)頂點(diǎn)之間的有向邊的權(quán)值作為路徑長(zhǎng)度，沒(méi)有有向邊時(shí)，路徑長(zhǎng)度為，當(dāng)K=0時(shí)，A (0)ij=arcsij, 以后逐步嘗試在原路徑中加入其他頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來(lái)的路徑長(zhǎng)度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：第一步，讓所有邊上加入中間頂

27、點(diǎn)1，取Aij與Ai1+A1j中較小的值作Aij的值，完成后得到A(1)，第二步，讓所有邊上加入中間頂點(diǎn)2，取Aij與Ai2+A2j中較小的值，完成后得到A(2)，如此進(jìn)行下去，當(dāng)?shù)趎步完成后，得到A(n)，A(n)即為我們所求結(jié)果，A(n)ij表示頂點(diǎn)i到頂點(diǎn)j的最短距離。,拓?fù)渑判?通常我們把計(jì)劃、施工過(guò)程、生產(chǎn)流程、程序流程等都當(dāng)成一個(gè)工程，一個(gè)大的工程常常被劃分成許多較小的子工程，這些子工程稱(chēng)為活動(dòng)，這些活動(dòng)完成時(shí)，整個(gè)工程也就完成了。例如，計(jì)算機(jī)專(zhuān)業(yè)學(xué)生的課程開(kāi)設(shè)可看成是一個(gè)工程，每一門(mén)課程就是工程中的活動(dòng)，圖7-24給出了若干門(mén)所開(kāi)設(shè)的課程，其中有些課程的開(kāi)設(shè)有先后關(guān)系，有些則沒(méi)有

28、先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開(kāi)設(shè)，如開(kāi)設(shè)數(shù)據(jù)結(jié)構(gòu)課程之前必須先學(xué)完程序設(shè)計(jì)基礎(chǔ)及離散數(shù)學(xué)，而開(kāi)設(shè)離散數(shù)學(xué)則必須學(xué)完高等數(shù)學(xué)。在圖7-24（b）中，我們用一種有向圖來(lái)表示課程開(kāi)設(shè)，在這種有向圖中，頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)的優(yōu)先關(guān)系，這有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(Active On Vertices)簡(jiǎn)稱(chēng)為AOV網(wǎng)。,在AOV網(wǎng)中，有向邊表示i活動(dòng)應(yīng)先于j活動(dòng)開(kāi)始，即i活動(dòng)必須完成后，j活動(dòng)才可以開(kāi)始，并稱(chēng)i為j的直接前驅(qū)，j為i的直接后繼。這種前驅(qū)與后繼的關(guān)系有傳遞性，此外，任何活動(dòng)i不能以它自己作為自己的前驅(qū)或后繼，這叫做反自反性。從前驅(qū)和后繼的傳遞性和反自反性來(lái)看，AOV網(wǎng)

29、中不能出現(xiàn)有向回路（或稱(chēng)有向環(huán)）。在AOV網(wǎng)中如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件，這是不對(duì)的，工程將無(wú)法進(jìn)行。對(duì)程序流程而言，將出現(xiàn)死循環(huán)。因此，對(duì)給定的AOV網(wǎng)，應(yīng)先判斷它是否存在有向環(huán)。判斷AOV網(wǎng)是否有有向環(huán)的方法是對(duì)該AOV網(wǎng)進(jìn)行拓?fù)渑判?，將AOV網(wǎng)中頂點(diǎn)排列成一個(gè)線(xiàn)性有序序列，若該線(xiàn)性序列中包含AOV網(wǎng)全部頂點(diǎn)，則AOV網(wǎng)無(wú)環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該AOV網(wǎng)所代表的工程是不可行的。,本章小結(jié),圖是一種復(fù)雜的非線(xiàn)性結(jié)構(gòu)，具有廣泛的應(yīng)用背景。本章涉及到的基本概念有： 圖：由兩個(gè)集合V和E組成，記為G(V，E)，其中v是頂點(diǎn)的有窮非空集合，E是V中頂點(diǎn)偶對(duì)（稱(chēng)為

30、邊）的有窮集。通常，也將圖G的頂點(diǎn)集和邊集分別記為V(G)和E(G)。E(G)可以是空集，若E(G)為空，則圖G只有頂點(diǎn)而沒(méi)有邊，稱(chēng)為空?qǐng)D。 有向圖（Digraph）：若圖G中的每條邊都是有方向的，則稱(chēng)G為有向圖。 無(wú)向圖（Undigraph）：若圖G中的每條邊都是沒(méi)有方向的，則稱(chēng)G為無(wú)向圖。 無(wú)向完全圖(Undirected Complete Graph)：恰好有n(n-1)2條邊的無(wú)向圖稱(chēng)為無(wú)向完全圖。 有向完全圖(Directed Complete Graph)：恰有n(n-1)條邊的有向圖稱(chēng)為有向完全圖。 鄰接點(diǎn)(Adjacent)：若(vi，vj)是一條無(wú)向邊，則稱(chēng)頂點(diǎn)vi和vj互為鄰接點(diǎn)。 度(Degree)：無(wú)向圖中頂點(diǎn)v的度是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目。 人度(1ndegree)若G為有向圖，則把以頂點(diǎn)v為