數(shù)據(jù)結構-C語言描述（第三版）課件：圖

圖7.1圖的定義與基本術語7.2圖的存儲結構7.3圖的遍歷7.4

圖的應用7.5總結與提高

圖結構與表結構和樹結構的不同表現(xiàn)在結點之間的關系上，線性表中結點之間的關系是一對一的；樹是按分層關系組織的結構，樹結構之間是一對多；對于圖結構，圖中頂點之間的關系可以是多對多，即一頂點和其它頂點間的關系是任意的，可以有關也可以無關。因此，圖G

樹T

L，圖是一種比較復雜的非線性數(shù)據(jù)結構。

圖作為一種非線性結構，被廣泛應用于多個技術領域。在本章中，主要是應用圖論的理論知識來討論如何在計算機上表示和處理圖，以及如何利用圖來解決一些實際問題。7.1圖的定義與基本術語7.1.1圖的定義圖（Graph）是一種網狀數(shù)據(jù)結構，其形式化定義如下：Graph=（V，R）V={x∣x∈DataObject}R={VR}VR={<x，y>∣P（x，y）∧（x，y∈V）}DataObject為一個集合，該集合中的所有元素具有相同的特性。V中的數(shù)據(jù)元素通常稱為頂點（vertex），VR是兩個頂點之間的關系的集合。P（x，y）表示x和y之間有特定的關聯(lián)屬性P。

?。喝?lt;x，y>∈VR，則<x，y>表示從頂點x到頂點y的一條?。╝rc），并稱x為弧尾（tail）或起始點，稱y為弧頭（head）或終端點。有向圖：若圖中的邊是有方向的，稱這樣的圖為有向圖。無向圖：若<x，y>∈VR，必有<y，x>∈VR，即VR是對稱關系，這時以無序對（x，y）來代替兩個有序對，表示x和y之間的一條邊（edge），此時的圖稱為無向圖。

例如：下圖G1是有向圖，G2是無向圖2134G12145G23

在圖中，我們可以將任一頂點看成是圖的第一個頂點，同理，對于任一頂點而言，它的鄰接點之間也不存在順序關系。為了操作的方便，我們需要將圖中的頂點按任意序列排列起來。頂點在這個人為的隨意排列中的位置序號稱為頂點在圖中的位置。

圖的基本操作和其它數(shù)據(jù)結構一樣，也有創(chuàng)建、插入、刪除、查找等。圖的抽象類型定義：ADTGraph數(shù)據(jù)對象V：一個集合，該集合中的所有元素具有相同的特性。數(shù)據(jù)關系R：R={VR}VR={<x，y>∣P（x，y）∧（x，y∈V）}基本操作：（1）CreateGraph（G）操作前提：已知圖G不存在操作結果：創(chuàng)建圖G。（2）DestoryGraph（G）操作前提：已知圖G存在；操作結果：銷毀圖G。（3）LocateVertex（G，v）操作前提：已知圖G存在，頂點v值合法；操作結果：若頂點v在圖G中存在，則返回頂點v在圖G中的位置。若圖G中沒有頂點v，則函數(shù)返回值為“空”。（4）GetVertex（G，i）操作前提：已知圖G存在；操作結果：返回圖G中的第i個頂點的值。若i大于圖G中頂點數(shù)，則函數(shù)返回值為“空”。（5）FirstAdjVertex（G，v）操作前提：已知圖G存在，頂點v值合法；操作結果：返回圖G中頂點v的第一個鄰接點。若v無鄰接點或圖G中無頂點v，則函數(shù)值為“空”。（6）NextAdjVertex（G，v，w）操作前提：已知圖G存在，w是圖G中頂點v的某個鄰接點，操作結果：返回頂點v的下一個鄰接點（緊跟在w后面）。若w是v的最后一個鄰接點，則函數(shù)值為“空”。（7）InsertVertex（G，u）操作前提：已知圖G存在，u值合法；操作結果：在圖G中增加一個頂點u。（8）DeleteVertex（G，v）操作前提：已知圖G存在，v值合法；操作結果：刪除圖G的頂點v及與頂點v相關聯(lián)的弧。（9）InsertArc（G，v，w）操作前提：已知圖G存在，v值，w值合法；操作結果：在圖G中增加一條從頂點v到頂點w的弧。（10）DeleteArc（G，v，w）操作前提：已知圖G存在，v值，w值合法，存在弧(v,w)；操作結果：刪除圖G中從頂點v到頂點w的弧。（11）TraverseGraph（G）操作前提：已知圖G存在；操作結果：按照某種次序，對圖G的每個頂點訪問一次且僅訪問一次。7.1.2基本術語

設用n表示圖中頂點的個數(shù)，用e表示圖中邊或弧的數(shù)目，并且不考慮圖中每個頂點到其自身的邊或弧。無向完全圖：有n（n-1）/2條邊（圖中每個頂點和其余n-1個頂點都有邊相連）的無向圖為無向完全圖。有向完全圖：有n（n-1）條邊（圖中每個頂點和其余n-1個頂點都有弧相連）的有向圖為有向完全圖。稀疏圖：對于有很少條邊的圖（e<nlogn）稱為稀疏圖，反之稱為稠密圖。

子圖：設有兩個圖G=（V，{E}）和圖G/=（V/，{E/}）,若V/

V且E/

E，則稱圖G/為G的子圖。

圖G1和圖G2的子圖如圖7.2所示。AACACDCDAB（a）G1的子圖ABCEDEABCEDBA（b）G2的子圖

對于無向圖

G=（V，{E}），如果邊（v，v/）∈E，則稱頂點v，v/互為鄰接點，即v，v/相鄰接。邊（v，v/）依附于頂點v和v/，或者說邊（v，v/）與頂點v和v/相關聯(lián)。對于有向圖G=（V，{A}）而言，若弧<v，v/>∈A，則稱頂點v鄰接到頂點v/，頂點v/鄰接自頂點v，或者說弧<v，v/>與頂點v，v/相關聯(lián)。

鄰接點：度、入度和出度

對于無向圖而言，頂點v的度是指和v相關聯(lián)的邊的數(shù)目，記作TD（v）。

對于有向圖而言，頂點v的度有出度和入度兩部分：以頂點v為弧頭的弧的數(shù)目稱為該頂點的入度，記作ID（v），以頂點v為弧尾的弧的數(shù)目稱為該頂點的出度，記作OD（v）則頂點v的度為：

TD（v）=ID（v）+OD（v）。

一般地，若圖G中有n個頂點，e條邊或弧，則圖中頂點的度與邊的關系如下：e=TD(Vi)2ni=1權與網

:

在實際應用中，有時圖的邊或弧上往往與具有一定意義的數(shù)有關，即每一條邊都有與它相關的數(shù)，稱為權，這些權可以表示從一個頂點到另一個頂點的距離或耗費等信息。我們將這種帶權的圖叫做賦權圖或網。16圖7.3賦權圖示例5661665123419211133141865路徑與回路無向圖G=（V，{E}）中從頂點v到v/的路徑是一個頂點序列vi0，vi1，vi2，…，vin，其中（vij-1，vij）∈E，1≤j≤n。如果圖G是有向圖，則路徑也是有向的，頂點序列應滿足<vij-1，vij>∈A，1≤j≤n。

路徑長度：指路徑上經過的弧或邊的數(shù)目。

回路或環(huán)：在一個路徑中，若其第一個頂點和最后一個頂點是相同的，即v=v/，則稱該路徑為一個回路或環(huán)。簡單路徑：若表示路徑的頂點序列中的頂點各不相同，則稱這樣的路徑為簡單路徑。簡單回路：除了第一個和最后一個頂點外，其余各頂點均不重復出現(xiàn)的回路為簡單回路。

連通圖

連通圖：在無向圖G=（V，{E}）中，若從vi到vj有路徑相通，則稱頂點vi與vj是連通的。如果對于圖中的任意兩個頂點vi、vj∈V，vi，vj都是連通的，則稱該無向圖G為連通圖。

連通分量：無向圖中的極大連通子圖稱為該無向圖的連通分量。

強連通圖：在有向圖G=（V，{A}）中，若對于每對頂點vi、vj∈V且vi≠vj，從vi到vj和vj到vi都有路徑，則稱該有向圖為強連通圖。強連通分量：有向圖的極大強連通子圖稱作有向圖的強連通分量。圖G1和圖G3的連通分量見p157的圖7.4所示(a)無向圖G3ABLCJFMDEIGHK(b)無向圖G3的三個連通分量BLCJFMIGHKDEABAC1D圖7.4圖G1和G3的連通分量示例(c)有向圖G1的兩個連通分量7.2圖的存儲結構圖的存儲結構方法有：①鄰接矩陣表示法；②鄰接表；③鄰接多重表；④十字鏈表

鄰接矩陣表示法

圖的鄰接矩陣表示法（AdjacencyMatrix）也稱作數(shù)組表示法。它采用兩個數(shù)組來表示圖：一個是用于存儲頂點信息的一維數(shù)組，另一個是用于存儲圖中頂點之間關聯(lián)關系的二維數(shù)組，這個關聯(lián)關系數(shù)組被稱為鄰接矩陣。

若G是一具有n個頂點的無權圖，G的鄰接矩陣是具有如下性質的n×n矩陣A：

A[i,j]=若<vi,vj>或（vi,vj)VR0反之G1和G2的鄰接矩陣A1=0 1 1 00 0 0 00 0 0 11 0 0 0A2=0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0若圖G是一個有n個頂點的網，則它的鄰接矩陣是具有如下性質的n×n矩陣A：A[i,j]=Wij若<vi,vj>或（vi,vj)VR∞反之有向網及其鄰接矩陣6978254551V1V6V5V4V2V3v1 v2 v3 v4 v5 v6∞ 5 ∞ 7 ∞ ∞∞ ∞ 4 ∞ ∞ ∞8 ∞ ∞ ∞ ∞ 9∞ ∞ 5 ∞ ∞ 6∞ ∞ ∞ 5 ∞ ∞2 ∞ ∞ ∞ 1 ∞v1v2v3v4v5v6(a)有向網N(b)有向網N的鄰接矩陣鄰接矩陣表示法的C語言類型描述為：#defineMAX_VERTEX_NUM10/*最多頂點個數(shù)*/#defineINFINITY32768/*最多頂點個數(shù)*/typedefenum{DG,DN,UDG,UDN}GraphKind;/*圖的種類：DG表示有向圖,DN表示有向網,UDG表示無向圖,UDN表示無向網*/typedefcharVertexData;/*假設頂點數(shù)據(jù)為字符型*/typedefstructArcNode{AdjTypeadj;/*對于無權圖，用1或0表示是否相鄰；對帶權圖，則為權值類型*/OtherInfoinfo;}ArcNode;typedefstruct{VertexDatavexs[MAX_VERTEX_NUM];/*頂點向量*/ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*鄰接矩陣*/intvexnum,arcnum;/*圖的頂點數(shù)和弧數(shù)*/GraphKindkind;/*圖的種類標志*/}AdjMatrix;/*（AdjacencyMatrixGraph）*/

鄰接矩陣法的特點：1.存儲空間：對于無向圖而言，它的鄰接矩陣是對稱矩陣，所以可采用壓縮存儲法（下三角），其存儲空間只需n(n-1)/2。但對于有向圖而言，因為它的弧是有方向的，它的鄰接矩陣不一定是對稱矩陣，所以需要n2個存儲空間。2.便于運算：采用鄰接矩陣表示法，便于判定圖中任意兩個頂點之間是否有邊相連，即根據(jù)A[i，j]=0或1來判斷。另外還便于求得各個頂點的度。

對于無向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個頂點的度：TD(vi)=A[i,j]j=1n

對于有向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個頂點的出度，第i列元素之和就是圖中第i個頂點的入度。

OD(vi)=A[i,j]j=1nID(vi)=A[j,i]j=1n頂點i的出度：頂點i的入度：采用鄰接矩陣存儲法表示圖，很便于實現(xiàn)圖的一些基本操作，如FirstAdjVertex（G，v）：（1）首先，由LocateVertex（G，v）找到v在圖中的位置，即v在一維數(shù)組vexs中的序號i。

（2）二維數(shù)組arcs中第i行上第一個adj域非零的分量所在的列號j，便是v的第一個鄰接點在圖G中的位置。

（3）取出一維數(shù)組vexs[j]中的數(shù)據(jù)信息，即與頂點v鄰接的第一個鄰接點的信息。

注意：稀疏圖不適于用鄰接矩陣來存儲，因為這樣會造成存儲空間的浪費。用鄰接矩陣法創(chuàng)建有向網的算法如下：intLocateVertex(AdjMatrix*G,VertexDatav)/*求頂點位置函數(shù)*/{intj=Error,k;for(k=0;k<G->vexnum;k++) if(G->vexs[k]==v) {j=k;break;}return(j);}intCreateDN(AdjMatrix*G)/*創(chuàng)建一個有向網*/{inti,j,k,weight;VertexDatav1,v2;scanf("%d,%d",&G->arcnum,&G->vexnum);/*輸入圖的頂點數(shù)和弧數(shù)*/for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++) G->arcs[i][j].adj=INFINITY;for(i=0;i<G->vexnum;i++)scanf("%c",&G->vexs[i]);/*輸入圖的頂點*/for(k=0;k<G->arcnum;k++) {scanf("%c,%c,%d",&v1,&v2,&weight);/*輸入一條弧的兩個頂點及權值*/ i=LocateVex_M(G,v1); j=LocateVex_M(G,v2); G->arcs[i][j].adj=weight;/*建立弧*/ }return(Ok);}分析：該算法的時間復雜度為O（n2+e×n），其中O（n2）時間耗費在對二維數(shù)組arcs的每個分量的arj域初始化賦值上。O（e×n）的時間耗費在有向網中邊權的賦值上。

鄰接表表示法鄰接表（AdjacencyList）表示法實際上是圖的一種鏈式存儲結構。

它的基本思想是只存有關聯(lián)的信息，對于圖中存在的邊信息則存儲，而對于不相鄰接的頂點則不保留信息。在鄰接表中，對圖中的每個頂點建立一個帶頭結點的邊鏈表，每個邊鏈表的頭結點又構成一個表頭結點表。這樣，一個n個頂點的圖的鄰接表表示由表頭結點表與邊表兩部分構成。（1）表頭結點表：由所有表頭結點以順序結構（向量）的形式存儲，以便可以隨機訪問任一頂點的單鏈表。表頭結點有兩部分構成，其中數(shù)據(jù)域（vexdata）用于存儲頂點的名或其它有關信息；鏈域（firstarc）用于指向鏈表中第一個頂點（即與頂點vi鄰接的第一個鄰接點）。表頭結點結構為：vexdatafirstarc（2）邊表：由表示圖中頂點間鄰接關系的n個邊鏈表組成。它由三部分組成，其中鄰接點域（adjvex）用于存放與頂點vi相鄰接的頂點在圖中的位置；鏈域（nextarc）用于指向與頂點vi相關聯(lián)的下一條邊或弧的結點；數(shù)據(jù)域（info）用于存放與邊或弧相關的信息（如賦權圖中每條邊或弧的權值等）。

adjvexinfonextarc弧結點結構為：圖例圖G1、G2的鄰接表表示法1234AB∧CD3∧24∧1∧（a）G1的鄰接表表示法1∧

2∧

2∧

341∧

2∧

45533ABECD12345（b）G2的鄰接表表示法鄰接表存儲結構的形式化說明如下：#defineMAX_VERTEX_NUM10/*最多頂點個數(shù)*/typedefenum{DG,DN,UDG,UDN}GraphKind;/*圖的種類*/typedefstructArcNode{intadjvex;/*該弧指向頂點的位置*/structArcNode*nextarc;/*指向下一條弧的指針*/OtherInfoinfo;/*與該弧相關的信息*/}ArcNode;

typedefstructVertexNode{VertexDatadata;/*頂點數(shù)據(jù)*/ArcNode*firstarc;/*指向該頂點第一條弧的指針*/}VertexNode;

typedefstruct{VertexNodevertex[MAX_VERTEX_NUM];intvexnum,arcnum;/*圖的頂點數(shù)和弧數(shù)*/GraphKindkind;/*圖的種類標志*/}AdjList;/*基于鄰接表的圖(AdjacencyListGraph)*/

●存儲空間：對于有n個頂點，e條邊的無向圖而言，若采取鄰接表作為存儲結構，則需要n個表頭結點和2e個表結點。

●無向圖的度：在無向圖的鄰接表中，頂點vi的度恰好就是第i個邊鏈表上結點的個數(shù)。

●有向圖的度：在有向圖中，第i個邊鏈表上頂點的個數(shù)是頂點vi的出度。要想求得該頂點的入度，則必須遍歷整個鄰接表。在所有單鏈表中查找鄰接點域的值為i的結點并計數(shù)求和。由此可見，對于用鄰接表方式存儲的有向圖，求頂點的入度并不方便，因此需要有一種解決的方法－逆鄰接表法。對圖中的每一頂點vi建立一個遞鄰接表，即對每個頂點vi建立一個所有以頂點vi為弧頭的弧的表，這樣求頂點vi的入度即是計算逆鄰接表中第i個頂點的邊鏈表中結點個數(shù)。

圖G1的逆鄰接表表示法見p162的圖7.10十字鏈表

十字鏈表(OrthogonalList)是有向圖的另一種鏈式存儲結構。我們也可以把它看成是將有向圖的鄰接表和逆鄰接表結合起來形成的一種鏈表。

有向圖中的每一條弧對應十字鏈表中的一個弧結點，同時有向圖中的每個頂點在十字鏈表中對應有一個結點，叫做頂點結點。

這兩類結點的結構見圖所示。tailvexheadvexhlinktlinktailvex表示弧尾頂點在圖中的位置headvex表示弧頭頂點在圖中的位置hlink指向與此弧的弧頭相同的下一條弧tlink指向與此弧的弧尾相同的下一條?。╝）十字鏈表弧結點結構示意datafirstinfirstoutdata域用于存儲與頂點有關的信息如頂點的名字等firstin域（鏈域）用于指向以該頂點作為弧頭的第一個弧頂點firstout域（鏈域）用于指向以該頂點作為弧尾的第一個弧頂點（b）十字鏈表頂點結點結構示意圖7.10圖的十字鏈表弧結點、頂點結點結構圖圖G1的十字鏈表表示12

∧

13∧

∧4

1

∧

∧

A

C

BD

34∧∧1234建立一個有向圖的十字鏈表的算法如下：

voidCrtOrthList（OrthListg）/*從終端輸入n個頂點的信息和e條弧的信息，以建立一個有向圖的十字鏈表*/{scanf(“%d,%d”,&n,&e);/*鍵盤輸入圖的頂點個數(shù)和弧的個數(shù)*/for(i=0;i<n;i++){scanf(“%c”,g.vertex[i].data）；

g.vertex[i].firstin=NULL；g.vertex[i].firsout=NULL；

}for(k=0;k<e;k++){scanf(“%c,%c”,&vt,&vh);i=LocateVertex（g，vt）；j=LocateVertex（g，vh）；

p=alloc(sizeof(ArcNode));p->tailvex=i；p->headvex=j；

p->tlink=g.vertex[i].firstout；g.vertex[i].firstout=p；

p->hlink=g.vertex[j].firstin；g.vertex[j].firstin=p；

}}/*CrtOrthList*/

十字鏈表的優(yōu)點：

在十字鏈表中既能夠很容易地找到以vi為尾的弧，也能夠容易地找到以vi為頭的弧，因此對于有向圖，若采用十字鏈表作為存儲結構，則很容易求出頂點vi的度。

鄰接多重表

鄰接多重表(AdjacencyMulti_list)是無向圖的另外一種存儲結構。使用鄰接多重表這種存儲結構是因為它能夠提供更為方便的邊處理信息。

鄰接多重表是指將圖中關于一條邊的信息用一個結點來表示。鄰接多重表中的邊結點結構和頂點結點結構markivexilinkjvexjlink標志域：可用以標記該條邊是否被搜索過ivex和jvex：為該邊依附的兩個頂點在圖中的位置ilink（鏈域）：用于指向下一條依附于頂點ivex的邊jlink（鏈域）：用于指向下一條依附于頂點jvex的邊（a）鄰接多重表中邊結點的結構datafirstedgedata域用于存儲與頂點有關的信息，如頂點的名字firstdege域（鏈域）用于指向第一條依附于該頂點的邊（b）鄰接多重表中頂點結點的結構圖7.12鄰接多重表的結點結構鄰接多重表的結構類型說明如下：typedefstructEdgeNode{intmark,ivex,jvex;structEdgeNode*ilink,*jlink;}EdgeNode;typedefstruct{VertexDatadata;EdgeNode*firstedge;}VertexNode;typedefstruct{VertexNodevertex[MAX_VERTEX_NUM];intvexnum,arcnum;/*圖的頂點數(shù)和弧數(shù)*/GraphKindkind;/*圖的種類*/}AdjMultiList;/*基于圖的鄰接多重表表示法(AdjacencyMulti_list)*/圖G2的鄰接多重表見圖所示。ABDC121∧4∧323∧5∧3452∧E圖7.13無向圖的鄰接多重表表示7.4圖的遍歷圖的遍歷：從圖中的某個頂點出發(fā)，按某種方法對圖中的所有頂點訪問且僅訪問一次。

為了保證圖中的各頂點在遍歷過程中訪問且僅訪問一次，需要為每個頂點設一個訪問標志，用以標示圖中每個頂點是否被訪問過，訪問標志用數(shù)組visited[n]來表示。

圖的遍歷方法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索深度優(yōu)先搜索：深度優(yōu)先搜索（Depth_FirstSearch）是指按照深度方向搜索，它類似于樹的先根遍歷。深度優(yōu)先算法的基本思想是：（1）從圖中某個頂點v0出發(fā)，首先訪問v0。

（2）找出剛訪問過的頂點vi的第一個未被訪問的鄰接點，然后訪問該頂點。重復此步驟，直到當前的頂點沒有未被訪問的鄰接點為止。（3）返回前一個訪問過的頂點，找出該頂點的下一個未被訪問的鄰接點，訪問該頂點。轉2。

采用遞歸的形式說明，則深度優(yōu)先搜索連通子圖的的基本思想可表示為：

（1）訪問出發(fā)點v0。

（2）依次以v0的未被訪問的鄰接點為出發(fā)點，深度優(yōu)先搜索圖，直至圖中所有與v0有路徑相通的頂點都被訪問。若此時圖中還有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，重復上述深度優(yōu)先搜索過程，直至圖中所有頂點均被訪問過為止。

深度優(yōu)先搜索的過程示例見p167的7.15圖所示。其中實箭頭代表訪問方向，虛箭頭代表回溯方向，箭頭旁邊的數(shù)字代表搜索順序，A為起始頂點。8ADGBEHCFI1236710114155149131216訪問序列為：A、B、C、F、E、G、D、H、I。圖的深度優(yōu)先搜索的算法描述如下：#defineTrue1#defineFalse0#defineError–1/*出錯*/#defineOk1intvisited[MAX_VERTEX_NUM];/*訪問標志數(shù)組*/

voidTraverseGraph(Graphg)/*對圖g進行深度優(yōu)先搜索，Graph表示圖的一種存儲結構，如數(shù)組表示法或鄰接表等*/{for(vi=0;vi<g.vexnum;vi++)visited[vi]=False;/*訪問標志數(shù)組初始*/for(vi=0;vi<g.vexnum;vi++) /*調用深度遍歷連通子圖的操作*//*若圖g是連通圖，則此循環(huán)只執(zhí)行一次*/ if(！visited[vi])DepthFirstSearch(g，vi)；}/*TraverseGraph*/

深度遍歷v0所在地連通子圖算法如下：voidDepthFirstSearch（Graphg,intv0）/*深度遍歷v0所在的連通子圖*/{visit（v0）；visited[v0]=True；/*訪問頂點v0，并置訪問標志數(shù)組相應分量值*/w=FirstAdjVertex(g,v0);while(w!=-1)/*鄰接點存在*/{if(!visited[w])DepthFirstSearch(g,w);/*遞歸調用DepthFirstSearch*/w=NextAdjVertex(g,v0,w);/*找下一個鄰接點*/}}/*DepthFirstSearch*/

上述算法中對于FirstAdjVertex（g，v0）以及NextAdjVertex（g，v0，w）并沒有具體實現(xiàn)。因為對于圖的不同存儲方法，兩個操作的實現(xiàn)方法不同，時間耗費也不同。

下面的算法是在鄰接矩陣與鄰接表方式下實現(xiàn)上面算法的功能。1）用鄰接矩陣方式實現(xiàn)深度優(yōu)先搜索voidDepthFirstSearch(AdjMatrixg,intv0)/*圖g為鄰接矩陣類型AdjMatrix*/

{visit(v0);visited[v0]=True;for(vj=0;vj<n;vj++)if(!visited[vj]&&g.arcs[v0][vj].adj==1)DepthFirstSearch(g,vj);}/*DepthFirstSearch*/

2）用鄰接表方式實現(xiàn)深度優(yōu)先搜索voidDepthFirstSearch(AdjListg,intv0)/*圖g為鄰接表類型AdjList*/{visit(v0)；visited[v0]=True；p=g.vertex[v0].firstarc；while(p!=NULL){if(!visited[p->adjvex])DepthFirstSearch（g，p->adjvex）；

p=p->nextarc；

}}/*DepthFirstSearch*/

分析算法：以鄰接表作為存儲結構，查找每個頂點的鄰接點的時間復雜度為O(e)，

其中e是無向圖中的邊數(shù)或有向圖中弧數(shù),則深度優(yōu)先搜索圖的時間復雜度為O(n+e)。

3）用非遞歸過程實現(xiàn)深度優(yōu)先搜索voidDepthFirstSearch(Graphg,intv0)/*從v0出發(fā)深度優(yōu)先搜索圖g*/{

InitStack(S);/*初始化空棧*/Push(S,v0)；while(!Empty(S)){v=Pop(S);if(!visited(v))/*棧中可能有重復結點*/{visit(v);visited[v]=True;}w=FirstAdj(g,v);/*求v的第一個鄰接點*/while(w!=-1){ if(!visited(w))Push(S,w);w=NextAdj(g,v,w);/*求v相對于w的下一個鄰接點*/}}}

7.3.2廣度優(yōu)先搜索廣度優(yōu)先搜索（Breadth_FirstSearch）是指按照廣度方向搜索，它類似于樹的按層次遍歷。廣度優(yōu)先搜索的基本思想是：（1）從圖中某個頂點v0出發(fā)，首先訪問v0。

（2）依次訪問v0的各個未被訪問的鄰接點。

（3）分別從這些鄰接點（端結點）出發(fā)，依次訪問它們的各個未被訪問的鄰接點（新的端結點）。

訪問時應保證：如果Vi和Vk為當前端結點，且Vi在Vk之前被訪問，則Vi的所有未被訪問的鄰接點應在Vk的所有未被訪問的鄰接點之前訪問。重復（3），直到所有端結點均沒有未被訪問的鄰接點為止。

若此時還有頂點未被訪問，則選一個未被訪問的頂點作為起始點，重復上述過程，直至所有頂點均被訪問過為止。

廣度優(yōu)先搜索過程示例見p169的圖7.16所示。其中箭頭代表搜索方向，箭頭旁邊的數(shù)字代表搜索順序，A為起始頂點。ADGBEHCFI14657823訪問序列為：A、B、E、D、C、G、F、H、I。廣度優(yōu)先搜索連通子圖的算法如下：voidBreadthFirstSearch(Graphg,intv0)/*廣度優(yōu)先搜索圖g中v0所在的連通子圖*/{visit(v0);visited[v0]=True;InitQueue(&Q);/*初始化空隊*/

EnterQueue(&Q,v0)；/*v0進隊*/while(!Empty(Q)){DeleteQueue(&Q,&v);/*隊頭元素出隊*/w=FirstAdj(g,v);/*求v的第一個鄰接點*/while(w!=-1){ if(!visited(w)){visit(w);visited[w]=True;EnterQueue(&Q,w);}

w=NextAdj(g,v,w);/*求v相對于w的下一個鄰接點*/}}}

7.4圖的應用7.4.1圖的連通性問題無向圖的連通分量

在對圖遍歷時，對于連通圖，無論是廣度優(yōu)先搜索還是深度優(yōu)先搜索，僅需要調用一次搜索過程，即從任一個頂點出發(fā)，便可以遍歷圖中的各個頂點。對于非連通圖，則需要多次調用搜索過程，而每次調用得到的頂點訪問序列恰為各連通分量中的頂點集。調用搜索過程的次數(shù)就是該圖連通分量的個數(shù)。

例如：一個非連通圖，按照它的鄰接表進行深度優(yōu)先搜索遍歷，三次調用深度優(yōu)先搜索（DepthFirstSearch）過程得到的訪問頂點序列為：1，2，4，3，95，6，78，10因此有三個連通分量。如圖所示5ABECFDHGIJ236932419417510248FEGADBCIJH(a)無向圖G5(b)G5的鄰接表ADBCIFEGJH(c)無向圖G5的三個連通分量圖7.16圖及其連通分量最小生成樹在一個連通網的所有生成樹中，各邊的代價之和最小的那棵生成樹稱為該連通網的最小代價生成樹（MinimumCostSpanningTree），簡稱為最小生成樹。

最小生成樹的重要性質如下：設N=(V,{E})是一連通網，U是頂點集V的一個非空子集。若（u,v）是一條具有最小權值的邊，其中u∈U，v∈V-U，則存在一棵包含邊（u,v）的最小生成樹。

用反證法來證明這個最小生成樹（MST）的性質：

假設不存在這樣一棵包含邊（u,v）的最小生成樹。任取一棵最小生成樹T，將（u,v）加入T中。根據(jù)樹的性質，此時T中必形成一個包含（u,v）的回路，且回路中必有一條邊（u’,v’）的權值大于或等于（u,v）的權值。刪除（u,v），則得到一棵代價小于等于T的生成樹T’，且T’為一棵包含邊（u,v）的最小生成樹。這與假設矛盾。

一個連通網的最小生成樹算法：普里姆算法假設N=(V,{E})是連通網，TE為最小生成樹中邊的集合。（1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U,v∈V-U的邊中選一條代價最小的邊（u0，v0）并入集合TE，同時將v0并入U；

（3）重復（2），直到U=V為止。

此時，TE中必含有n-1條邊，則T=（V，{TE}）為N的最小生成樹。

普里姆算法是逐步增加U中的頂點，可稱為“加點法”注意：選擇最小邊時，可能有多條同樣權值的邊可供選擇，此時任選其一。為了實現(xiàn)這個算法需設一個輔助數(shù)組closedge[]，以記錄從U道V-U具有最小代價的邊。對每個頂點v∈V-U，在輔助數(shù)組中存在一個分量closedge[v]，它包括兩個域vex和lowcost，其中l(wèi)owcost存儲該邊上的權，顯然有

closedge[v].lowcoast=Min({cost(u,v)|u∈U})普里姆算法可描述為：struct{VertexDataadjvex;intlowcost;}closedge[MAX_VERTEX_NUM];/*求最小生成樹時的輔助數(shù)組*/MiniSpanTree_Prim(AdjMatrixgn,VertexData

u)/*從頂點u出發(fā)，按普里姆算法構造連通網gn的最小生成樹，并輸出生成樹的每條邊*/{k=LocateVertex(gn,u);closedge[k].lowcost=0;/*初始化，U={u}*/for(i=0;i<gn.vexnum;i++)if(i!=k)/*對V-U中的頂點i，初始化closedge[i]*/{closedge[i].adjvex=u;closedge[i].lowcost=gn.arcs[k][i].adj;}for(e=1;e<=gn.vexnum-1;e++)/*找n-1條邊(n=gn.vexnum)*/{k0=Minium(closedge);/*closedge[k0]中存有當前最小邊（u0,v0）的信息*/u0=closedge[k0].adjvex;/*u0∈U*/v0=gn.vexs[k0]/*v0∈V-U*/printf(u0,v0);/*輸出生成樹的當前最小邊（u0,v0）*/closedge[k0].lowcost=0;/*將頂點v0納入U集合*/for(i=0;i<vexnum;i++)/*在頂點v0并入U之后，更新closedge[i]*/if(gn.arcs[k0][i].adj<closedge[i].lowcost){closedge[i].lowcost=gn.arcs[k0][i].adj;closedge[i].adjvex=v0;}}}

P173的圖7.18(a)是一個連通網，由普里姆算法構造最小生成樹的過程見圖7.18(b)~(f)所示。算法中各參量的變化見p173的表7－1。圖7.18普里姆算法構造最小生成樹的過程iClosedge[i]012345UV-Uek0(u0,v0)adjvexlowcost0V16V11V15V1∞V1∞{V1}{V2,V3,V4,V5,V6}12(V1,V3)adjvexlowcost0V350V15V36V34{V1,V3}{V2,V4,V5,V6}25(V3,V6)adjvexlowcost0V350V62V360{V1,V3,V6}{V2,V4,V5}33(V6,V4)adjvexlowcost0V3500V360{V1,V3,V6,V4}{V2,V5}41(V3,V2)adjvexlowcost0000V230{V1,V3,V6,V4,V2}{V5}54(V2,V5)adjvexlowcost000000{V1,V3,V6,V4,V2,V5}{}表7-1普里姆算法各參量的變化2.克魯斯卡爾算法假設N=(V,{E})是連通網，將N中的邊按權值從小到大的順序排列；（1）將n個頂點看成n個集合；

（2）按權值由小到大的順序選擇邊，所選邊應滿足兩個頂點不在同一個頂點集合內，將該邊放到生成樹邊的集合中。同時將該邊的兩個頂點所在的頂點集合合并；（3）重復（2），直到所有的頂點都在同一個頂點集合內。

克魯斯卡爾算法是逐步增加生成樹的邊，故稱為“加邊法”克魯斯卡爾算法的執(zhí)行過程。7.4.2有向無環(huán)圖的應用拓撲排序（TopologicalSort）

AOV-網：用頂點表示活動，用弧表示活動間的優(yōu)先關系的有向無環(huán)圖，稱為頂點表示活動的網（ActivityOnVertexNetwork），簡稱為AOV-網。

如表7-2課程關系，用頂點表示課程，弧表示先決條件，則表7－2可用一個有向無環(huán)圖表示。見圖課程編號課程名稱先修課程C1高等數(shù)學無C2程序設計基礎無C3離散數(shù)學C1,C2C4數(shù)據(jù)結構C2,C3C5算法語言C2C6編譯技術C4,C5C7操作系統(tǒng)C4,C9C8普通物理C1C9計算機原理C8C1C2C3C4C5C6C7C8C9圖7.21表示課程之間優(yōu)先關系的有向無環(huán)圖拓撲序列：在有向圖G=（V，{E}）中，

V中頂點的線性序列（vi1,,vi1,,vi3,…，vin）稱為拓撲序列。此序列必須滿足：對序列中任意兩個頂點vi、vj，在G中有一條從vi到vj的路徑，則在序列中vi必排在vj之前。

如前圖的一個拓撲序列為：C1,C2,C3,C4,C5,C8,C9,C7,C6。

AOV-網的特性如下：

若vi為vj的先行活動，vj為vk的先行活動，則vi必為vk的先行活動，即先行關系具有可傳遞性。

AOV-網的拓撲序列不是唯一的。

它的另一個拓撲序列為：C1,C2,C3,C8,C4,C5,C9,C7,C6。

求拓撲排序的基本思想：（1）從有向圖中選一個無前驅的頂點輸出；（2）將此頂點和以它為起點的弧刪除；（3）重復（1）、（2），直到不存在無前驅的頂點；（4）若此時輸出的頂點數(shù)小于有向圖中的頂點數(shù)，則說明有向圖中存在回路，否則輸出的頂點的順序即為一個拓撲序列。

例如圖7.22所示的AOV－網，其拓撲序列為：v1,v6,v4,v3,v2,v5或v1,v3,v2,v6,v4,v5V1V6V2V4V3V5圖7.22AOV-網對于有向圖的不同存儲形式，有不同實現(xiàn)的拓撲排序算法。1）基于鄰接矩陣表示的存儲結構A為有向圖G的鄰接矩陣，則有（1）找G中無前驅的頂點—在A中找到值全為0的列；（2）刪除以i為起點的所有弧—將矩陣中i對應的行全部置為0。

算法步驟為：（1）取1作為第一新序號；（2）找一個未新編號的、值全為0的列j，若找到則轉（3）；否則，若所有的列全部都編過號，拓撲排序結束；若有列未曾被編號，則該圖中有回路；（3）輸出列號對應的頂點j，把新序號賦給所找到的列；（4）將矩陣中j對應的行全部置為0;（5）新序號加1，轉（2）；

2）基于鄰接表的存儲結構

入度為零的頂點即沒有前趨的頂點，因此我們可以附設一個存放各頂點入度的數(shù)組indegree[]，于是有

（1）找G中無前驅的頂點——查找indegree[i]為零的頂點vi；（2）刪除以i為起點的所有弧——對鏈在頂點i后面的所有鄰接頂點k，將對應的indegree[k]減1。

為了避免重復檢測入度為零的頂點，可以再設置一個輔助棧，若某一頂點的入度減為0，則將它入棧。每當輸出某一頂點時，便將它從棧中刪除。

拓撲排序的實現(xiàn)算法intTopoSort(AdjListG){StackS;intindegree[MAX_VERTEX_NUM];inti,count,k;ArcNode*p;FindID(G,indegree);/*求各頂點入度*/InitStack(&S);/*初始化輔助棧*/for(i=0;i<G.vexnum;i++) if(indegree[i]==0)Push(&S,i);/*將入度為0的頂點入棧*/count=0;

while(!StackEmpty(S)){Pop(&S,&i); printf("%c",G.vertex[i].data); count++;/*輸出i號頂點并計數(shù)*/p=G.vertexes[i].firstarc; while(p!=NULL) {k=p->adjvex;indegree[k]--;/*i號頂點的每個鄰接點的入度減1*/ if(indegree[k]==0)Push(&S,k);/*若入度減為0，則入棧*/ p=p->nextarc; } }/*while*/if(count<G.vexnum)return(Error);/*該有向圖含有回路*/elsereturn(Ok);}求各頂點入度的函數(shù)voidFindID(AdjListG,intindegree[MAX_VERTEX_NUM])/*求各頂點的入度*/{inti;ArcNode*p;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertexes[i].firstarc; while(p!=NULL) {indegree[p->adjvex]++; p=p->nextarc; }}/*for*/}圖7.22所示的AOV-網用拓撲排序算法求出的拓撲序列為：v6，v1，v3，v2，v4，v5。

算法的時間復雜度分析：

若有向無環(huán)圖有n個頂點和e條弧，則在拓撲排序的算法中，for循環(huán)需要執(zhí)行n次，時間復雜度為O(n)；對于while循環(huán)，由于每一頂點必定進一次棧，出一次棧，其時間復雜度為O(e)；故該算法的時間復雜度為O(n+e)。

關鍵路徑AOE-網：在有向圖中，用頂點表示事件，用弧表示活動，弧的權值表示活動所需要的時間。我們把用這種方法構造的有向無環(huán)圖叫做邊表示活動的網（ActivityOnEdgeNetwork）,簡稱AOE-網。

AOE-網用在工程計劃和管理中，人們最關心的是：

哪些活動是影響工程進度的關鍵活動？

至少需要多長時間能完成整個工程？源點：存在唯一的、入度為零的頂點，叫源點。匯點：存在唯一的、出度為零的頂點，叫匯點。關鍵路徑：從源點到匯點的最長路徑的長度即為完成整個工程任務所需的時間，該路徑叫做關鍵路徑。關鍵活動：關鍵路徑上的活動叫做關鍵活動。

在AOE-網中的基本概念：如圖7.24所示的AOE-網。V0為源點，表示整個工程可以開始，v8為匯點，表示整個工程結束。410235678a1=6a2=4a3=5a5=1a6=2a9=4a4=1a10=2a11=4a8=7a7=9圖7.24AOE-網幾個重要的定義：

事件vi的最早發(fā)生時間ve(i)：從源點到頂點vi的最長路徑的長度，叫做事件vi的最早發(fā)生時間。求ve(i)時可從源點開始，按拓撲順序向匯點遞推：ve(0)=0；

ve(i)=Max{ve(k)＋dut(<k,i>)}<k,i>∈T,1≤i≤n-1;其中，T為所有以i為頭的弧<k,i>的集合，dut（<k,i>）表示與弧<k,i>對應的活動的持續(xù)時間。

事件vi的最晚發(fā)生時間vl(i)：在保證匯點按其最早發(fā)生時間發(fā)生這一前提下，事件vi的最晚發(fā)生時間。在求出ve(i)的基礎上，可從匯點開始，按逆拓撲順序向源點遞推，求出vl(i)：vl(n-1)=ve(n-1)；

vl(i)=Min{vl(k)＋dut(<i,k>)}<i,k>∈S,0≤i≤n-2;其中，S為所有以i為尾的弧<i,k>的集合，dut（<i,k>）表示與弧<i,k>對應的活動的持續(xù)時間。

活動ai的最早開始時間e(i)：如果活動ai對應的弧為<j,k>，則e(i)等于從源點到頂點j的最長路徑的長度，即：e(i)=ve(j)

活動ai的最晚開始時間l(i)：如果活動ai對應的弧為<j,k>，其持續(xù)時間為dut（<j,k>）則有：l(i)=vl(k)-dut（<j,k>）

活動ai的松弛時間（時間余量）：ai的最晚開始時間與ai的最早開始時間之差：l(i)-e(i)。顯然，松弛時間（時間余量）為0的活動為關鍵活動。

求關鍵路徑的基本步驟：（1）對圖中頂點進行拓撲排序，在排序過程中按拓撲序列求出每個事件的最早發(fā)生時間ve(i)；（2）按逆拓撲序列求每個事件的最晚發(fā)生時間vl(i)；（3）求出每個活動ai的最早開始時間e(i)和最晚發(fā)生時間l(i)；4)找出e(i)=l(i)的活動ai，即為關鍵活動。

修改后的拓撲排序算法intve[MAX_VERTEX_NUM];/*每個頂點的最早發(fā)生時間*/intTopoOrder(AdjListG,Stack*T)/*G為有向網，T為返回拓撲序列的棧，S為存放入度為0的頂點的棧*/{intcount,i,j,k;ArcNode*p;intindegree[MAX_VERTEX_NUM];/*各頂點入度數(shù)組*/StackS;InitStack(T);InitStack(&S);/*初始化棧T,S*/FindID(G,indegree);/*求各個頂點的入度*/for(i=0;i<G.vexnum;i++)if(indegree[i]==0) Push(&S,i);count=0;for(i=0;i<G.vexnum;i++)ve[i]=0;/*初始化最早發(fā)生時間*/while(!StackEmpty(S)){Pop(&S,&j);Push(T,j);count++;p=G.vertex[j].firstarc;while(p!=NULL) { k=p->adjvex;if(--indegree[k]==0)Push(&S,k);/*若頂點的入度減為0，則入棧*/

if(ve[j]+p->weight>ve[k])ve[k]=ve[j]+p->weight; p=p->nextarc; }/*while*/}/*while*/if(count<G.vexnum)return(Error);elsereturn(Ok);}求關鍵路徑的實現(xiàn)算法intCriticalPath(AdjListG){ArcNode*p;inti,j,k,dut,ei,li;chartag;intvl[MAX_VERTEX_NUM];/*每個頂點的最遲發(fā)生時間*/StackT;if(!TopoOrder(G,&T))return(Error);for(i=0;i<G.vexnum;i++) vl[i]=ve[i];/*初始化頂點事件的最遲發(fā)生時間*/while(!StackEmpty(T))/*按逆拓撲順序求各頂點的vl值*/ {Pop(&T,&j); p=G.vertex[j].firstarc; while(p!=NULL) {k=p->adjvex;dut=p->weight; if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;p=p->nextarc; }/*while*/ }/*while*/for(j=0;j<G.vexnum;j++)/*求ei,li和關鍵活動*/ {p=G.vertex[j].firstarc; while(p!=NULL) {k=p->Adjvex;dut=p->weight; ei=ve[j];li=vl[k]-dut;tag=(ei==li)?'*':'';printf("%c,%c,%d,%d,%d,%c\n",G.vertex[j].data,G.vertex[k].data,dut,ei,li,tag);/*輸出關鍵活動*/ p=p->nextarc; }/*while*/ }/*for*/return(Ok);}/*CriticalPath*/該算法的時間復雜度為O(n+e)。用該算法求圖7.24中AOE-網的關鍵路徑，結果如圖7.25。014867a1a7a8a11a10a4圖7.25關鍵路徑7.4.3最短路徑問題求某一頂點到其它各頂點的最短路徑設有帶權的有向圖D=(V,{E})，D中的邊權為

W(e)。已知源點為v0，求v0到其它各頂點的最短路徑。

如圖7.26所示的帶權有向圖，其源點v0到其它各頂點的最短路徑如表7－3所示。0V4V2V3V545153531520源點終點最短路徑路徑長度V0V2V0，V210V3V0，V2，V325V1V0，V2，V3，V145V4V0，V445V5無最短路徑圖7.26一個帶權有向圖表7.3v0到其他頂點的最短路徑用迪杰斯特拉（Dijkstra）求最短路徑算法對于圖G=(V,E)，將圖中的頂點分成兩組：第一組S：已求出的最短路徑的終點集合（開始為{v0}）。第二組V－S：尚未求出最短路徑的頂點集合（開始為V－{v0}的全部結點）。算法將按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中，直到所有頂點都被加入到第一組頂點集S為止。[定理]：下一條最短路徑或者是?。╲0，vx），或者是中間經過S中的某些頂點，而后到達vx的路徑。[證明]：可用反證法：假設下一條最短路徑上有一個頂點vy不在S中，即此路徑為（v0，…，vy，…，vx）。顯然，（v0，…，vy）的長度小于（v0，…，vy，…，vx）的長度，故下一條最短路徑應為（v0，…，vy），這與假設的下一條最短路徑（v0，…，vy，…，vx）相矛盾！因此，下一條最短路徑上不可能有不在S中的頂點vy，即假設不成立。算法中使用了輔助數(shù)組dist[]，dist[i]表示目前已經找到的、從開始點v0到終點vi的當前最短路徑的長度。它的初值為：如果從v0到vi有弧，則dist[i]為弧的權值；否則dist[i]為∞。根據(jù)上述定理，長度最短的一條最短路徑必為(v0,vk)，vk滿足如下條件：dist[k]=Min{dist[i]|vi∈V-S}求得頂點vk的最短路徑后，將vk加入到第一組頂點集S中。每加入一個新的頂點vk到頂點集S，則對第二組剩余的各個頂點而言，多了一個“中轉”結點，從而多了一個“中轉”路徑，所以要對第二組剩余的各個頂點的最短路徑長度dist[i]進行修正。原來v0到vi的最短路徑長度為dist[i]，加進vk之后，以vk作為中間頂點的“中轉”路徑長度為：dist[k]+wki，（wki為弧<vk,vi>上的權值），若“中轉”路徑長度小于dist[i]，則將頂點vi的最短路徑長度修正為“中轉”路徑長度。修正后，再選擇數(shù)組dist[]中值最小的頂點加入到第一組頂點集S中，如此進行下去，直到圖中所有頂點都加入到第一組頂點集S中為止。另外，為了記錄從v0出發(fā)到其余各點的最短路徑（頂點序列），引進輔助數(shù)組path[]，path[i]表示目前已經找到的、從開始點v0到終點vi的當前最短路徑頂點序列。它的初值為：如果從v0到vi有弧，則path[i]為（v0,vi）；否則path[i]為空。求圖的最短路徑的迪杰斯特拉算法typedefSeqListVertexSet;ShortestPath_DJS(AdjMatrixg,intv0,WeightTypedist[MAX_VERTEX_NUM],VertexSetpath[MAX_VERTEX_NUM])/*path[i]中存放頂點i的當前最短路徑。dist[i]中存放頂點i的當前最短路徑長度*/{VertexSets;/*s為已找到最短路徑的終點集合*/for(i=0;i<g.vexnum;i++)/*初始化dist[i]和path

[i]*/{InitList(&path[i]);dist[i]=g.arcs[v0][i];if(dist[i]<MAX){AddTail(&path[i],g.vexs[v0]);/*AddTail為表尾添加操作*/AddTail(&path[i],g.vexs[i]);}}

InitList(&s);AddTail(&s,g.vexs[v0]);/*將v0看成第一個已找到最短路徑的終點*/for(t=1;t<=g.vexnum-1;t++)/*求v0到其余n-1個頂點的最短路徑(n=g.vexnum)*/{min=MAX;for(i=0;i<g.vexnum;i++)if(!Member(g.vex[i],s)&&dist[i]<min){k=i;min=dist[i];}AddTail(&s,g.vexs[k]);for(i=0;i<g.vexnum;i++)/*修正dist[i],i∈V-S*/if(!Member(g.vex[i],s)&&(dist[k]+g.arcs[k][i]<dist[i])){dist[i]=dist[k]+g