圖Graph是一種較線性表和樹更為復雜的非線性結(jié)構(gòu)在線

圖

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

若圖G中的每條邊都是有方向的，則稱G為有向圖（Digraph）。在有向圖中，一條有向邊是由兩個頂點組成的有序?qū)Γ行驅(qū)νǔＳ眉饫ㄌ柋硎?。例如，＜vi，vj＞表示一條有向邊，vi是邊的始點（起點），vj是邊的終點。因此，＜vi，vj＞和＜vj，vi＞是兩條不同的有向邊。有向邊也稱為?。ˋrc），邊的始點稱為弧尾（Tail），終點稱為弧頭（Head）。圖G由兩個集合V和E組成，記為G＝(V，E)，其中v是頂點的有窮非空集合，E是V中頂點偶對（稱為邊）的有窮集。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。E(G)可以是空集，若E(G)為空，則圖G只有頂點而沒有邊，稱為空圖。

若(vi，vj)是一條無向邊，則稱頂點vi和vj互為鄰接點(Adjacent)，或稱vi和vj相鄰接；稱(vi，vj)關(guān)聯(lián)(Incident)于頂點vi和vj，或稱(vi，vj)與頂點vi和vj相關(guān)聯(lián)。如圖7-1中G2，與頂點vl相鄰接的頂點是v2，v3和v4，而關(guān)聯(lián)于頂點v2的邊是(vl，v2)，(v2，v3)和(v2，v4)。若＜vi，vj＞是一條有向邊，則稱頂點vi鄰接到vj,頂點vj鄰接于頂點vi,并稱邊＜vi，vj＞關(guān)聯(lián)于vi和vj或稱＜vi，vj＞與頂點vi和vj相關(guān)聯(lián)。如圖7-1中Gl，關(guān)聯(lián)于頂點v2的邊是＜v1，v2＞，＜v2，vl＞和＜v2,v3＞。無向圖中頂點v的度(Degree)是關(guān)聯(lián)于該頂點的邊的數(shù)目，記為D(v)。若G為有向圖，則把以頂點v為終點的邊的數(shù)目，稱為v的人度(1ndegree)，記為ID(v)；把以頂點v為始點的邊的數(shù)目，稱為v的出度(outdegree)，記為OD(v)；頂點v的度則定義為該頂點的入度和出度之和，即D(v)＝ID(v)十OD(v)。

在一個有向圖中，若存在一個頂點v，從該頂點有路徑可以到達圖中其它所有頂點，則稱此有向圖為有根圖，v稱作圖的根。在無向圖G中，若從頂點vi到頂點vj有路徑(當然從vj到vi也一定有路徑)，則稱vi和vj是連通的。若V(G)中任意兩個不同的頂點vi和vj都連通(即有路徑)，則稱G為連通圖(ConnectedGraph)。例如，圖G2和G3是連通圖。無向圖G的極大連通子圖稱為G的連通分量(connectedComponent)。顯然，任何連通圖的連通分量只有一個，即是其自身，而非連通的無向圖有多個連通分量。例如，圖7-4中的G4是非連通圖，它有兩個連通分量Hl和H2。在有向圖G中，若對于V(G)中任意兩個不同的頂點vi和vj，都存在從vi到vj以及從vj到vi的路徑，則稱G是強連通圖。有向圖G的極大強連通子圖稱為G的強連通分量。顯然，強連通圖只有一個強連通分量，即是其自身。非強連通的有向圖有多個強連通分量。例如圖7-1中的Gl不是強連通圖，因為v3到v2沒有路徑，但它有兩個強連通分量，若將圖的每條邊都賦上一個權(quán)，則稱這種帶權(quán)圖為網(wǎng)絡(Network)。通常權(quán)是具有某種意義的數(shù).它們可以表示兩個頂點之間的距離，耗費等用鄰接矩陣表示法表示圖，除了存儲用于表示頂點間相鄰關(guān)系的鄰接矩陣外，通常還需要用一個順序表來存儲頂點信息。其形式說明如下：#definen6 /*圖的頂點數(shù)*/#definee8 /*圖的邊（?。?shù)*/typedefcharvextype； /*頂點的數(shù)據(jù)類型*/typedeffloatadjtype； /*權(quán)值類型*/typedefstruct{vextypevexs[n]；adjtypearcs[n][n]；}graph；

若圖中頂點信息是0至n-1的編號，則僅需令權(quán)值為1，存儲一個鄰接矩陣就可以表示圖。若是網(wǎng)絡，則adjtype為權(quán)的類型。由于無向圖或無向網(wǎng)絡的鄰接矩陣是對稱的，故可采用壓縮存儲的方法，僅存儲下三角陣(不包括對角線上的元素)中的元素即可。顯然，鄰接矩陣表示法的空間復雜度S(n)＝O(n2)。CREATGRAPH(ga)／*建立無向網(wǎng)絡*／Graph*ga；{inti，j，k；floatw；for(i＝0；i＜n；i++)ga->vexs[i]＝getchar()；／*讀入頂點信息，建立頂點表*／for(i＝0；i＜n；i++)for(j＝0；j＜n；j++)ga->arcs[i][j]＝0；／*鄰接矩陣初始化*／for(k＝0；k＜e；k++)／*讀入e條邊*／(scanf(”％d％d％f”，&I,&j，&w)；／*讀入邊(vi，vj)上的權(quán)w*／ga->arcs[i][j]＝w；ga->arcs[j][i]＝w；}}／*CREATGRAPH*／該算法的執(zhí)行時間是O(n+n2+e)，其中O(n2)的時問耗費在鄰接矩陣的初始化操作上。因為e＜n2，所以，算法的時間復雜度是O(n2)。鄰接表這種表示法類似于樹的孩子鏈表表示法。對于圖G中的每個頂點vi，該方法把所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表(AdjacencyList)。鄰接表中每個表結(jié)點均有兩個域，其一是鄰接點域(Adjvex)，用以存放與vi相鄰接的頂點vj的序號；其二是鏈域(Next)，用來將鄰接表的所有表結(jié)點鏈在一起。并且為每個頂點vi的鄰接表設置一個具有兩個域的表頭結(jié)點：一個是頂點域(vertex)，用來存放頂點vi的信息；另一個是指針域(Link)，用于存入指向vi的鄰接表中第一個表結(jié)點的頭指針。為了便于隨機訪問任一頂點的鄰接表，將所有鄰接表的表頭結(jié)點順序存儲在一個向量中，這樣，圖G就可以由這個表頭向量來表示。在鄰接表(或逆鄰接表)表示中，每個邊表對應于鄰接矩陣的一行(或一列)，邊表中結(jié)點個數(shù)等于一行(或一列)中非零元素的個數(shù)。對于一個具有n個頂點e條邊的圖G，若G是無向圖，則它的鄰接表表示中有n個頂點表結(jié)點和2e個邊表結(jié)點；若G是有向圖，則它的鄰接表表示或逆鄰接表表示中均有n個頂點表結(jié)點和e個邊表結(jié)點。因此鄰接表或逆鄰接表表示的空間復雜度為S(n，e)＝O(n+e)。若圖中邊的數(shù)目遠遠小于n2(即e＜＜n2)，此類圖稱作稀疏圖(SparseGraph)，這時用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間；若e接近于n2(準確地說，無向圖e接近于n(n-1)／2，有向圖e接近于n(n-1))，此類圖稱作稠密圖(DenseGraph)，考慮到鄰接表中要附加鏈域，則應取鄰接矩陣表示法為宜。在無向圖中求頂點的度，鄰接矩陣及鄰接表兩種存儲結(jié)構(gòu)都很容易做到：鄰接矩陣中第i行(或第i列)上非零元素的個數(shù)即為頂點vi的度；在鄰接表表示中，頂點vi的度則是第i個邊表中的結(jié)點個數(shù)。在有向圖中求頂點的度。采用鄰接矩陣表示比鄰接表表示更方便：鄰接矩陣中的第i行上非零元素的個數(shù)是頂點vi的出度OD(vi)，第i列上非零元素的個數(shù)是頂點vi的入度ID(vi)，頂點vi的度即是二者之和；在鄰接表表示中，第i個邊表(即出邊表)上的結(jié)點個數(shù)是頂點vi的出度，求vi的入度較困難，需遍歷各頂點的邊表。若有向圖采用逆鄰接表表示，則與鄰接表表示相反，求頂點的入度容易，而求頂點出度較難。

在鄰接矩陣表示中，很容易判定(vi，vj)或＜vi，vj＞是否是圖的一條邊，只要判定矩陣中的第i行第j列上的那個元素是否為零即可；但是在鄰接表表示中，需掃描第i個邊表，最壞情況下要耗費O(n)時間。在鄰接矩陣中求邊的數(shù)目e，必須檢測整個矩陣，所耗費的時間是0(n2)，與e的大小無關(guān)；而在鄰接表表示中，只要對每個邊表的結(jié)點個數(shù)計數(shù)即可求得e，所耗費的時間是0(e+n)。因此，當e＜＜n2時，采用鄰接表表示更節(jié)省時間。圖的遍歷和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā)，沿著某條搜索路徑對圖中所有頂點各作一次訪問。若給定的圖是連通圖，則從圖中任一頂點出發(fā)順著邊可以訪問到該圖的所有頂點。然而，圖的遍歷比樹的遍歷復雜得多，這是因為圖中的任一頂點都可能和其余頂點相鄰接，故在訪問了某個頂點之后，可能順著某條回路又回到了該頂點。為了避免重復訪問同一個頂點，必須記住每個頂點是否被訪問過。為此，可設置一個布爾向量visited[n]，它的初值為false，一旦訪問了頂點vi，便將visited[i-1]置為TRUE。在該存儲結(jié)構(gòu)上執(zhí)行DFS算法的過程如下：設初始出發(fā)點是v1，則DFS（0）的執(zhí)行結(jié)果是訪問v1，將其置上已訪問標記，從v1搜索到的第1個鄰接點是v2，因v2未曾訪問過，故調(diào)用DFS(1)。執(zhí)行DFS(1)，首先訪問v2，將其標記為已訪問過，然后從v2搜索到的第1個鄰接點是vl，但vl已訪問過，故繼續(xù)搜索到第2個鄰接點v4，v4未曾訪過，因此調(diào)用DFS(3)。類似地分析，訪問v4后調(diào)用DFS(7)，訪問v：后調(diào)用DPS(4)。執(zhí)行DFS(4)時，在訪問v5并作標記后，從v5搜索到的兩個鄰接點依次是v2和v8，因為它們均已被訪問過，所以DFS(4)執(zhí)行結(jié)束返回，回溯到v8。又因為v8的兩個鄰接點已搜索過，故DFS(7)亦結(jié)束返回，回溯到v4。類似地由v4回溯到v2。V2的鄰接點vl和v4已搜索過，但v2的第3個鄰接點v5還尚未搜索，故接下來由v2搜索到v5，但因為v5已訪問過，所以DFS(1)也結(jié)束返回，回溯到vl。vl的第1個鄰接點已搜索過，故繼續(xù)從v1搜索到第2個鄰接點v3，因為v3未曾訪問過，故調(diào)用DFS(2)。類似地依次訪問v3，v6，v7后，又由v7依次回溯到v6，v3，vl。此時，vl的所有鄰接點都已搜索過，故DFS(0)執(zhí)行完畢。寬度優(yōu)先搜索法寬度優(yōu)先搜索(Breadth-First-Search)遍歷類似于樹的按層次遍歷。設圖G的初態(tài)是所有頂點均未訪問過，在G中任選一頂點2為初始出發(fā)點，則寬度優(yōu)先搜索的基本思想是：首先訪問出發(fā)點Vi，接著依次訪問vi的所有鄰接點wl，w2，…，wt，然后，再依次訪問與wl，w2，…，wt鄰接的所有未曾訪問過的頂點，依此類推，直至圖中所有和初始出發(fā)點v有路徑相通的頂點都已訪問到為止。此時，從vi開始的搜索過程結(jié)束，若G是連通圖則遍歷完成。顯然，上述搜索法的特點是盡可能先對橫向進行搜索，故稱之為寬度優(yōu)先搜索。設x和y是兩個相繼被訪問過的頂點，若當前是以x為出發(fā)點進行搜索，則在訪問x的所有未曾訪問過的鄰接點之后，緊接著是以y為出發(fā)點進行橫向搜索，并對搜索到的y的鄰接點中尚未被訪問的頂點進行訪問。也就是說，先訪問的頂點其鄰接點亦先被訪問。為此，需引進隊列保存已訪問過的頂點。最小生成樹

圖的生成樹不是唯一的，從不同的頂點出發(fā)進行遍歷，可以得到不同的生成樹。對于連通網(wǎng)絡G＝(V，E)，邊是帶權(quán)的，因而G的生成樹的各邊也是帶權(quán)的。我們把生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并把權(quán)最小的生成樹稱為G的最小生成樹(MinimunSpanningTree)。生成樹和最小生成樹有許多重要的應用。令圖G的頂點表示城市，邊表示連接兩個城市之間的通訊線路。n個城市之間最多可設立的線路有n(n-1)／2條，把n個城市連接起來至少要有n-1條線路，則圖G的生成樹表示了建立通訊網(wǎng)絡的可行方案。如果給圖中的邊都賦予權(quán)，而這些權(quán)可表示兩個城市之間通訊線路的長度或建造代價，那么，如何選擇n-1條線路，使得建立的通訊網(wǎng)絡其線路的總長度最短或總代價最小呢?這就是要構(gòu)造該圖的一棵最小生成樹。

假設G＝(V，E)是連通網(wǎng)絡，為簡單起見，我們用序號1至n來表示頂點集合，即v＝{1，2，…，n}。設所求的最小生成樹為T＝(U，TE)，其中U是T的頂點集，TE是T的邊集。并且將G中邊上的權(quán)看做是長度。Prim算法的基本思想是：首先從v中任取一個頂點u0，將生成樹T置為僅有一個結(jié)點u0的樹，即置U＝{u0}；然后只要U是V的真子集，就在所有那些其一個端點u己在T(即u∈U)、另一個端點v還未在T(即v∈V—U)的邊中，找一條最短(即權(quán)最小)的邊(u，v)，并把該條邊(u，v)和其不在T中的頂點v，分別并入T的邊集TE和頂點集U。如此進行下去，每次往生成樹里并入一個頂點和一條邊，直到把所有頂點都包括進生成樹T為止。此時，必有U＝V，TE中有n-1條邊。MST性質(zhì)保證上述過程求得的T＝(U，TE)是G的一棵最小生成樹。顯然，Prim算法的關(guān)鍵是如何找到連接U和V-U的最短邊來擴充生成樹T。為直觀解釋方便，設想在構(gòu)造過程中，T的頂點集U中頂點和邊集TE中的邊均被涂成紅色，U之外的頂點集V-U中的頂點均被涂成藍色，連接紅點和藍點的邊均被涂成紫色，那么．最短紫邊就是連接U和V-U的最短邊。最短路徑交通網(wǎng)絡中常常提出這樣的問題：從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短?交通網(wǎng)絡可用帶權(quán)圖來表示。頂點表示城市名稱，邊表示兩個城市有路連通，邊上權(quán)值可表示兩城市之間的距離、交通費或途中所花費的時間等。求兩個頂點之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。另外，若兩個頂點之間沒有邊，則認為兩個頂點無通路，但有可能有間接通路（從其他頂點達到)）。路徑上的開始頂點(出發(fā)點)稱為源點，路徑上的最后一個頂點稱為終點，并假定討論的權(quán)值不能為負數(shù)。所有頂點對之間的最短路徑所有頂點對之間的最短路徑是指：對于給定的有向網(wǎng)G=(V,E)，要對G中任意一對頂點有序?qū)、W(V≠W)，找出V到W的最短距離和W到V的最短距離。解決此問題的一個有效方