實用數據結構基礎第7章圖1第7章圖知識點圖的邏輯結構及基本術語鄰接矩陣和鄰接表的存儲結構和特點深度優先搜索和廣度優先搜索兩種遍歷算法圖的連通性和生成樹的概念最短路徑的含義及求最短路徑的算法2難點圖的遍歷最小生成樹最短路徑要求熟練掌握以下內容：圖的存儲結構圖的遍歷算法了解以下內容：圖的最小生成樹和求最小生成樹算法帶權有向圖的最短路徑問題3第7章目錄7-1圖的定義和術語7-2圖的存儲表示7-3圖的遍歷7-4圖的連通性7-5最短路徑小結實驗7圖子系統習題747-1圖的定義和術語圖（Graph）是一種比樹形結構更復雜的非線性結構。在圖形結構中，每個結點都可以有多個直接前驅和多個直接后繼。7-1圖的定義和術語7-1-1圖的定義圖（Graph）是由非空的頂點（Vertices）集合和一個描述頂點之間關系——邊（Edges）的有限集合組成的一種數據結構。可以用二元組定義為：G＝（V，E）其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。5

圖7-1無向圖G1

圖7-2有向圖G2

V1V3V2V4V5V1V3V2V4

G1=（V，E）V＝{v1,v2,v3,v4,v5}；E＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。(vi,vj)表示頂點vi和頂點vj之間有一條無向直接連線，也稱為邊。G2=(V,E)V={v1,v2,v3,v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}<vi,vj>表示頂點vi和頂點vj之間有一條有向直接連線，也稱為弧。其中vi稱為弧尾，vj稱為弧頭。67-1-2圖的相關術語（1）無向圖（Undigraph）在一個圖中，如果每條邊都沒有方向（如圖7-1），則稱該圖為無向圖。（2）有向圖（Digraph）在一個圖中，如果每條邊都有方向（如圖7-2），則稱該圖為有向圖。（3）無向完全圖在一個無向圖中，如果任意兩頂點都有一條直接邊相連接，則稱該圖為無向完全圖。可以證明，在一個含有n個頂點的無向完全圖中，有n(n-1)/2條邊。7（4）有向完全圖在一個有向圖中，如果任意兩頂點之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個含有n個頂點的有向完全圖中，有n(n-1)條弧。（5）稠密圖、稀疏圖我們稱邊數很多的圖為稠密圖；稱邊數很少的圖為稀疏圖。（6）頂點的度在無向圖中：一個頂點擁有的邊數，稱為該頂點的度。記為TD(v)。8在有向圖中：(a)一個頂點擁有的弧頭的數目，稱為該頂點的入度，記為ID(v)；(b)一個頂點擁有的弧尾的數目，稱為該頂點的出度，記為OD(v)；(c)一個頂點度等于頂點的入度+出度，即：TD(v)=ID(v)＋OD(v)。在圖7-1的G1中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在圖7-2的G2中有：ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=29可以證明，對于具有n個頂點、e條邊的圖，頂點vi的度TD(vi)與頂點的個數以及邊的數目滿足關系：

（7）權圖的邊或弧有時具有與它有關的數據信息，這個數據信息就稱為權（Weight）。ACBD58697（8）網——邊（或弧）上帶權的圖稱為網（Network）。如圖7-3所示，就是一個無向網。如果邊是有方向的帶權圖，則就是一個有向網。圖7-3一個無向網示意圖7-3一個無向網示意10（9）路徑、路徑長度頂點vi到頂點vj之間的路徑是指頂點序列vi,vi1,vi2,…,vim,vj.。其中，（vi,vi1），(vi1,vi2)，…,(vim,.vj)分別為圖中的邊。路徑上邊的數目稱為路徑長度。在圖7-1的無向圖G1中，v1→v4→v3→v5與v1→v2→v5是從頂點v1到頂點v5的兩條路徑，路徑長度分別為3和2。（10）回路、簡單路徑、簡單回路在一條路徑中，如果其起始點和終止點是同一頂點，則稱其為回路或者環。如果一條路徑上所有頂點除起始點和終止點外彼此都是不同的，則稱該路徑為簡單路徑。在圖7-1中，前面提到的v1到v5的兩條路徑都為簡單路徑。除起始點和終止點外，其他頂點不重復出現的回路稱為簡單回路，或者簡單環。如圖7-2中的v1→v3→v4→v1。11（11）子圖對于圖G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，則稱圖G’是G的一個子圖。圖7-4示出了G1和G2的子圖。圖7-4圖G1和G2的兩個子圖示意(a)G1的子圖(b)G2的子圖V1V3V2V1V3V2V4V5V1V3V2V4V5

圖7-1無向圖G112（12）連通圖、連通分量在無向圖中，如果從一個頂點vi到另一個頂點vj(i≠j)有路徑，則稱頂點vi和vj是連通的。任意兩頂點都是連通的圖稱為連通圖。無向圖的極大連通子圖稱為連通分量。圖7-5(a)中有兩個連通分量，如圖7-5(b)所示。AEBFCDAEBFCD(a)無向圖G3(b)G3的兩個連通分量圖7-5無向圖及連通分量示意13（13）強連通圖、強連通分量對于有向圖來說，若圖中任意一對頂點vi

和vj(i≠j)均有從一個頂點vi到另一個頂點vj有路徑，也有從vj到vi的路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量。圖7-2中有兩個強連通分量，分別是{v1,v2,v3}和{v4}，如圖7-6所示。（14）生成樹連通圖G的一個子圖如果是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹（SpanningTree）。在生成樹中添加任意一條屬于原圖中的邊必定會產生回路，因為新添加的邊使其所依附的兩個頂點之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。n個頂點的生成樹具有n-1條邊。V1V3V2V4圖7-6有向圖G2的兩個強連通分量示意147-1-3圖的基本操作圖的基本操作有：（1）CreatGraph（G）輸入圖G的頂點和邊，建立圖G的存儲。（2）DFSTraverse（G，v）在圖G中，從頂點v出發深度優先遍歷圖G。（3）BFSTtaverse（G，v）在圖G中，從頂點v出發廣度優先遍歷圖G。

圖的存儲結構比較多。對于圖的存儲結構的選擇取決于具體的應用和需要進行的運算。下面介紹幾種常用的圖的存儲結構。7-2圖的存儲表示15鄰接矩陣是表示頂點之間相鄰關系的矩陣。假設圖G＝（V，E）有n個頂點，即V＝{v0,v1,…,vn-1}，則G的鄰接矩陣是具有如下性質的n階方陣：1若(vi,vj)或<vi,vj>是E(G)中的邊A[i][j]=

0若(vi,vj)或<vi,vj>不是E(G)中的邊若G是網，則鄰接矩陣可定義為：wij若(vi,vj)或<vi,vj>是E(G)中的邊A[i][j]=0或∞若(vi,vj)或<vi,vj>不是E(G)中的邊其中，wij表示邊(vi,vj)或<vi,vj>上的權值（如圖7-3）；∞表示一個計算機允許的、大于所有邊上權值的數。16

用鄰接矩陣表示法如圖7-7所示；用鄰接矩陣表示法如圖7-8所示。17圖的鄰接矩陣具有以下性質：（1）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上（或下）三角矩陣的元素即可。（2）對于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的度TD(vi)。（3）對于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的出度OD(vi)（或入度ID(vi)）。（4）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。18圖的鄰接矩陣存儲的描述如下：#defineMAXLEN10typedefstruct{charvexs[MAXLEN];intedges[MAXLEN][MAXLEN];intn,e;}MGraph;

19建立一個圖的鄰接矩陣存儲的算法如下：voidCreateMGraph(MGraph*G){inti,j,k;charch1,ch2;printf("請輸入頂點數和邊數(輸入格式為:頂點數,邊數):\n");scanf("%d,%d",&(G->n),&(G->e));printf("請輸入頂點信息(頂點號<CR>)每個頂點以回車作為結束:\n");for(i=0;i<G->n;i++){getchar();scanf("%c",&(G->vexs[i])); }for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;20printf("請輸入每條邊對應的兩個頂點的序號(輸入格式為:i,j):\n");for(k=0;k<G->e;k++){getchar();printf("請輸入第%d條邊的頂點序號：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++); G->edges[i][j]=1;}}217-2-2鄰接表鄰接表(AdjacencyList)是圖的一種順序存儲與鏈式存儲結合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖G中的每個頂點vi，該方法將所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表。再將所有點的鄰接表表頭放到數組中，就構成了圖的鄰接表。在鄰接表表示中有兩種結點結構，如圖7-9所示。頂點域邊表頭指針鄰接點域指針域

頂點表邊表圖7-9鄰接矩陣表示的結點結構vertexfirstedgeadjvexnext22

一種是頂點表的結點結構，它由頂點域（vertex）和指向第一條鄰接邊的指針域（firstedge）構成，另一種是邊表結點，它由鄰接點域(adjvex)和指向下一條鄰接邊的指針域(next)構成。對于網的邊表需再增設一個存儲邊上信息（如權值等）的域（info），網的邊表結構如圖7-10所示。鄰接點域邊上信息指針域

圖7-10網的邊表結構adjvexinfonext23圖7-11給出無向圖7-7對應的鄰接表表示。

鄰接表表示形式描述如下：24＃defineMAXLEN10//最大頂點數為10typedefstructnode//邊表結點{intadjvex; //鄰接點域structnode*next;//指向下一個鄰接點的指針域

//若要表示邊上信息，則應增加一個數據域info}EdgeNode;typedefstructvnode//頂點表結點{VertexTypevertex;//頂點域EdgeNode*firstedge;//邊表頭指針}VertexNode;typedefVertexNodeAdjList[MAXLEN];//AdjList是鄰接表類型typedefstruct{AdjListadjlist;//接表intn,e;//頂點數和邊數}ALGraph;//ALGraph是以鄰接表方式存儲的圖類型25

建立一個有向圖的鄰接表存儲的算法如下：voidCreateGraphAL(ALGraph*G){inti,j,k;EdgeNode*s;printf(“請輸入頂點數和邊數(輸入格式為:頂點數,邊數)：\n");scanf("%d,%d",&(G->n),&(G->e));//讀入頂點數和邊數printf("請輸入頂點(格式為:頂點號<CR>)以回車作為結束:\n");for(i=0;i<G->n;i++) //立有n個頂點的頂點表{scanf("\n%c",&(G->adjlist[i].vertex));//讀入頂點信息G->adjlist[i].firstedge=NULL;}//點的邊表頭指針設為空printf("請輸入邊的信息(輸入格式為:i,j)：\n");for(k=0;k<G->e;k++) //建立邊表{scanf(“\n%d,%d”,&i,&j);//讀入邊<Vi,Vj>的頂點對應序號

s=newEdgeNode; //生成新邊表結點ss->adjvex=j; //鄰接點序號為js->next=G->adjlist[i].firstedge;//新邊表插入到頂點邊表頭部G->adjlist[i].firstedge=s;}}26

若無向圖中有n個頂點、e條邊，則它的鄰接表需n個頭結點和2e個表結點。顯然，在邊稀疏(e<<n(n-1)/2)的情況下，用鄰接表表示圖比鄰接矩陣節省存儲空間，當和邊相關的信息較多時更是如此。在無向圖的鄰接表中，頂點vi的度恰為第i個鏈表中的結點數；但在有向圖中，第i個鏈表中的結點個數只是頂點vi的出度。如果要求入度，則必須遍歷整個鄰接表才能得到結果。有時，為了便于確定頂點的入度或以頂點vi為頭的弧，可以建立一個有向圖的逆鄰接表，即對每個頂點vi建立一個鏈接，以vi為弧頭的弧的鏈表。例如圖7-12所示為有向圖G2（圖7-2）的鄰接表和逆鄰接表。27

在建立鄰接表或逆鄰接表時，若輸入的頂點信息即為頂點的編號，則建立鄰接表的復雜度為O（n+e），否則，需要通過查找才能得到頂點在圖中位置，則時間復雜度為O（n*e）。

287-3

圖的遍歷圖的遍歷（traversinggraph）是指從圖中的某一頂點出發，對圖中的所有頂點訪問一次，而且僅訪問一次。圖的遍歷是圖的一種基本操作。由于圖結構本身的復雜性，所以圖的遍歷操作也較復雜，主要表現在以下四個方面：（1）在圖結構中，每一個結點的地位都是相同的，沒有一個“自然”的首結點，圖中任意一個頂點都可作為訪問的起始結點。（2）在非連通圖中，從一個頂點出發，只能夠訪問它所在的連通分量上的所有頂點，因此，還需考慮如何訪問圖中其余的連通分量。（3）在圖結構中，如果有回路存在，那么一個頂點被訪問之后，有可能沿回路又回到該頂點。（4）在圖中，一個頂點可以和其它多個頂點相連，當這個頂點訪問過后，就要考慮如何選取下一個要訪問的頂點。297-3-1深度優先搜索深度優先搜索（Depth-FisrstSearch）遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設初始狀態是圖中所有頂點未曾被訪問，則深度優先搜索可從圖中某個頂點發v出發，首先訪問此頂點，然后任選一個v的未被訪問的鄰接點w出發，繼續進行深度優先搜索，直到圖中所有和v路徑相通的頂點都被訪問到；若此時圖中還有頂點未被訪問到，則另選一個未被訪問的頂點作為起始點，重復上面的做法，直至圖中所有的頂點都被訪問。V1V5V2V4V8V3V6V7圖7-13無向圖G5

以圖7-13的無向圖G5為例，其深度優先搜索得到的頂點訪問序列為：v1→v2→v4→v8→v5→v3

→v6、→v730顯然，以上方法是一個遞歸的過程。為了在遍歷過程中便于區分頂點是否已被訪問，需附設訪問標志數組visited[0:n-1],，其初值為FALSE，一旦某個頂點被訪問，則其相應的分量置為TRUE。從圖的某一點v出發，遞歸地進行深度優先遍歷的過程如下面算法所示。

voidDFSTraverseM(MGraph*G)

{inti;

for(i=0;i<G->n;i++)

visited[i]=FALSE; //FALSE在c語言中定義為0，以下同

for(i=0;i<G->n;i++)

if(!visited[i])

DFSM(G,i);

}31voidDFSM(MGraph*G,inti){intj;printf("\t\t深度優先遍歷結點:結點%c\n",G->vexs[i]);visited[i]=TRUE; //TRUE在c語言中定義為1，以下同for(j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j]) DFSM(G,j);}在遍歷時，對圖中每個頂點至多調用一次DFSM函數，因為一旦某個頂點被標志成已被訪問，就不再從它出發進行搜索。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構。當用二維數組表示鄰接矩陣圖的存儲結構時，查找每個頂點的鄰接點所需時間為O(n2)，其中n為圖中頂點數。32當以鄰接表作圖的存儲結構時，找鄰接點所需時間為O(e)，其中e為無向圖中邊的數或有向圖中弧的數。由此，當以鄰接表作存儲結構時，深度優先搜索遍歷圖的時間復雜度為O(n+e)。

7-3-2廣度優先搜索廣度優先搜索遍歷類似于樹的按層次遍歷。假設從圖中某頂點v出發，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。換句話說，廣度優先搜索遍歷圖的過程中以v為起始點，由近至遠，依次訪問和v有路徑相通且路徑長度為1,2,…的頂點。33對圖7-13無向圖G5進行廣度優先搜索遍歷，首先訪問v1和v1的鄰接點v2和v3，然后依次訪問v2的鄰接點v4和v5及v3的鄰接點v6和v7，最后訪問v4的鄰接點v8。由于這些頂點的鄰接點均已被訪問，并且圖中所有頂點都被訪問，由些完成了圖的遍歷。得到的頂點訪問序列為：v1→v2→v3→v4→v5→v6→v7→v8和深度優先搜索類似，在遍歷的過程中也需要一個訪問標志數組。并且，為了順次訪問路徑長度為2、3、…的頂點，需附設隊列以存儲已被訪問的路徑長度為1、2、…的頂點。V1V5V2V4V8V3V6V7圖7-13無向圖G5

34從圖的某一點v出發，遞歸地進行廣度優先遍歷的過程如下面的算法所示。voidBFSTraverseM(MGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)if(!visited[i])BFSM(G,i);}35voidBFSM(MGraph*G,intk){inti,j;CirQueueQ;InitQueue(&Q);printf("廣度優先遍歷結點:結點%c\n",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j]){printf("廣度優先遍歷結點:%c\n",G->vexs[j]);visited[j]=TRUE;EnQueue(&Q,j);}}}36圖7-4圖的連通性

分析上述算法，每個頂點至多進一次隊列。遍歷圖的過程實質是通過邊或弧找鄰接點的過程，因此廣度優先搜索遍歷圖和深度優先搜索遍歷的時間復雜度是相同的，兩者不同之處僅僅在于對頂點訪問的順序不同。

判定一個圖的連通性是圖的一個應用問題，我們可以利用圖的遍歷算法來求解這一問題。本節將討論無向圖的連通性問題，并討論最小代價生成樹等問題。377-4-1無向圖的連通分量和生成樹

在對無向圖進行遍歷時，對于連通圖，僅需從圖中任一頂點出發，進行深度優先搜索或廣度優先搜索，便可訪問到圖中所有頂點。對非連通圖，則需從多個頂點出發進行搜索，而每一次從一個新的起始點出發進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。例如，圖7-14(a)是一個非連通圖G6，按照圖7-14(b)所示G3的鄰接表進行深度優先搜索遍歷AEBFCD圖7-14(a)非連通圖圖7-14(b)G6的鄰接表38

兩次調用DFS過程（即分別從頂點A和D出發），得到的頂點訪問序列為：ABFECE這兩個頂點集分別加上所有依附于這些頂點的邊，便構成了非連通圖G3的兩個連通分量。

因此，要想判定一個無向圖是否為連通圖，或有幾個連通分量，就可設一個計數變量count，初始時取值為0，在深度優先搜索算法循環中，每調用一次DFS，就給count增1。這樣，當整個算法結束時，依據count的值，就可確定圖的連通性了。

設E(G)為連通圖G中所有邊的集合，則從圖中任一頂點出發遍歷圖時，必定將E(G)分成兩個集合T(G)和B(G)，其中T(G)是遍歷圖過程中歷經的邊的集合；B(G)是剩余的邊的集合。顯然，T(G)和圖G中所有頂點一起構成連通圖G的極小連通子圖。39按照7-1-2節的定義，它是連通圖的一棵生成樹，并且由深度優先搜索得到的為深度優先生成樹；由廣度優先搜索得到的為廣度優先生成樹。例如，圖7-15(a)和(b)所示分別為圖7-13連通圖G5的深度優先生成樹和廣度優先生成樹。圖中虛線為集合B(G)中的邊，實線為集合T(G)中的邊。圖7-15(a)G5的深度優先生成樹圖7-15(b)G5的廣度優先生成樹V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V740對于非連通圖，通過這樣的遍歷，將得到的是生成森林。例如，圖7-16(b)所示為圖7-16(a)的深度優先生成森林，它由三棵深度優先生成樹組成。圖7-16(a)非連通無向圖G7圖7-16(b)G7的深度優先生成樹林JHKLMAICFGBDEJHKLMAICFGBDE417-4-2最小生成樹1．最小生成樹的基本概念由生成樹的定義可知，無向連通圖的生成樹不一定是唯一的。連通圖的一次遍歷所經過的邊的集合及圖中所有頂點的集合就構成了該圖的一棵生成樹，對連通圖的不同遍歷，就可能得到不同的生成樹。圖7-17(a)、(b)和(c)所示的均為圖7-13的無向連通圖G5的生成樹。V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7圖7-17無向連通圖G5的三棵生成樹（a）（b）（c）42可以證明，對于有n個頂點的無向連通圖，無論其生成樹的形態如何，所有生成樹中都有且僅有n-1條邊。如果無向連通圖是一個網，那么，它的所有生成樹中必有一棵邊的權值之和為最小的生成樹，簡稱為最小生成樹。最小生成樹的概念可以應用到許多實際問題中。例如有這樣一個問題：以盡可能抵的總造價建造城市間的通訊網絡，把十個城市聯系在一起。在這十個城市中，任意兩個城市之間都可以建造通訊線路，通訊線路的造價依據城市間的距離不同而有不同的造價，可以構造一個通訊線路造價網絡，在網絡中，每個頂點表示城市，頂點之間的邊表示城市之間可構造通訊線路，每條邊的權值表示該條通訊線路的造價，要想使總的造價最低，實際上就是尋找該網絡的最小生成樹。432．常用的構造最小生成樹的方法（1）構造最小生成樹的Prim算法假設G＝（V，E）為一連通網，頂點集V={v1，v2，…，vn}，E為網中所有帶權邊的集合。設置兩個新的集合U和T，其中集合U用于存放G的最小生成樹中的頂點，集合T存放G的最小生成樹中的邊。令集合U的初值為U＝{v1}（假設構造最小生成樹時，從頂點v1出發），集合T的初值為T＝{}。Prim算法的基本思想：從所有u∈U，v∈V－U的邊中，選取具有最小權值的邊（u，v），將頂點v加入集合U中，將邊（u，v）加入集合T中，如此不斷重復，直到U＝V時，最小生成樹構造完畢，這時集合T中包含了最小生成樹的所有邊。圖7-18(a)所示的一個網，按照Prim方法，從頂點A出發，該網的最小生成樹的產生過程如圖7-18(b)、(c)、(d)、(e)、(f)所示。44圖7-18Prim算法構造最小生成樹的過程示意圖

AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)681214161751566666888881212121414545（2）構造最小生成樹的Kruskal算法

Kruskal算法是一種按照網中邊的權值遞增的順序構造最小生成樹的方法。其基本思想是：首先選取全部的n個頂點，將其看成n個連通分量；然后按照網中邊的權值由小到大的順序，不斷選取當前未被選取的邊集中權值最小的邊。依據生成樹的概念，n個結點的生成樹，有n-1條邊，故反復上述過程，直到選取了n-1條邊為止，就構成了一棵最小生成樹。46圖7-19Kruskal算法構造最小生成樹的過程示意圖

AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)68121416175155666688885121255145返回477-5最短路徑

最短路徑問題是圖的又一個比較典型的應用問題。例如，某一地區的一個交通網，給定了該網內的n個城市以及這些城市之間的相通公路的距離，問題是如何在城市A和城市B之間找一條最近的通路。如果將城市用頂點表示，城市間的公路用邊表示，公路的長度則作為邊的權值，那么，這個問題就可歸結為在網中，求點A到點B的所有路徑中，邊的權值之和最短的那一條路徑。這條路徑就稱為兩點之間的最短路徑，并稱路徑上的第一個頂點為源點（Sourse），最后一個頂點為終點（Destination）。在不帶權的圖中，最短路徑是指兩點之間經歷的邊數最少的路徑。例如在圖7-20中，設V1為源點，則從V1出發的路徑有（括號里為路徑長度）：48V1到V2的路徑有條：V1→V2(20)V1到V3的路徑有條：V1→V3(15),V1→V2→V3(55)V1到V4的路徑有條：V1→V2→V4(30),V1→V3→V4(45),V1→V2→V3→V4(85)V1到V5的路徑有條：V1→V2→V3→V5(65),V1→V3→V5(25)選出V1到其它各頂點的最短路徑，并按路徑長度遞增順序排列如下：V1→V3(15)，V1→V2(20)，V1→V3→V5(25)，V1→V2→V4(30)。

圖7-20V1出發的路徑V1V5V2V4V320103510153049從上面的序列中，可以看出一個規律：按路徑長度遞增順序生成從源點到其它各頂點的最短路徑時，當前正生成的最短路徑上除終點外，其它頂點的最短路徑已經生成。迪杰斯特拉算法正是根據此規律得到的。迪杰斯特拉（Dijkstra）算法的基本思想：設置兩個頂點集S和T，S中存放已確定最短路徑的頂點，T中存放待確定最短路徑的頂點。初始時S中僅有一個源點，T中含除源點外其余頂點，此時各頂點的當前最短長度為源點到該頂點的弧上的權值。接著選取T中當前最短路徑長度最小的一個頂點v加入S，然后修改T中剩余頂點的當前最短路徑長度，修改原則是：當v的最短路徑長度與v到T中頂點之間的權值之和小于該頂點的當前最短路徑長度時，用前者替換后者。重復以上過程，直到S中包含所有頂點。

50圖7-21用迪杰斯特拉算法求有向圖的最短路徑過程

V1V5V2V4V3201035101530V1V5V2V4V32015V1V5V2V4V320101530V1V5V2V4V320101530V1V5V2V4V3201015301051小結（1）圖是一種復雜的數據結構，圖中的每一個頂點都可以有多個直接前驅和多個直接后繼，所以是一種非線性的數據結構。（2）因為圖是由頂點的集合和頂點間邊的集合組成，所以圖的存儲也包括頂點信息和邊的信息兩個方面。（3）圖的存儲結構常用的有：鄰接矩陣和鄰接表等要求掌握。（4）對于n個頂點的圖來說，它的鄰接矩陣是一個n×n階的方陣。鄰接矩陣中的元素取值只能是0或1，若圖為無向圖，則矩陣一定是對稱矩陣，所以