第7章圖及其應(yīng)用

第7章圖及其應(yīng)用 圖(Graph)：是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)。是頂點(diǎn)集V和連接這些頂點(diǎn)的弧集(邊集)R所組成的結(jié)構(gòu)記為:G=(V,R）

若圖中的邊是頂點(diǎn)的有序?qū)?則稱此圖為有向圖。有向邊又稱為弧,通常用尖括弧表示一條有向邊,〈vi,vj〉表示從頂點(diǎn)vi到vj的一段弧,vi稱為邊的始點(diǎn)(或弧尾),vj稱為邊的終點(diǎn)(或弧頭),〈vi,vj〉和〈vj,vi〉代表兩條不同的弧。132 無向圖：若圖中的邊是頂點(diǎn)的無序?qū)?則稱此圖為無向圖。通常用圓括號表示無向邊,(vi,vj)表示頂點(diǎn)vi和vj間相連的邊。在無向圖中(vi,vj)和(vj,vi)表示同一條邊.2341完全圖、稠密圖、稀疏圖具有n個(gè)頂點(diǎn)，n(n-1)/2條邊的圖，稱為完全無向圖，具有n個(gè)頂點(diǎn)，n(n-1)條弧的有向圖,稱為完全有向圖。完全無向圖和完全有向圖都稱為完全圖。對于一般無向圖，頂點(diǎn)數(shù)為n，邊數(shù)為e，則0≤e≤n(n-1)/2。對于一般有向圖，頂點(diǎn)數(shù)為n，弧數(shù)為e，則0≤e≤n(n-1)。當(dāng)一個(gè)圖接近完全圖時(shí)，則稱它為稠密圖，相反地，當(dāng)一個(gè)圖中含有較少的邊或弧時(shí)，則稱它為稀疏圖。 子圖：對于圖G=(V,R),G′=(V′,R′),若有V′V,R′R,則稱圖G′是G的一個(gè)子圖。 下圖給出了G與其子圖G′。2435167圖G435167圖G′鄰接點(diǎn)對于無向圖G=(V,R)，如果邊(v，v′)∈R，則稱頂點(diǎn)v,v′互為鄰接點(diǎn)，即v,v′相鄰接。邊（v,v′）依附于頂點(diǎn)v和v′，或者說邊（v，v′）與頂點(diǎn)v和v′相關(guān)聯(lián)。對于有向圖G=(V，R)而言，若弧<v，v′>∈R，則稱頂點(diǎn)v鄰接到頂點(diǎn)v′，頂點(diǎn)v′鄰接自頂點(diǎn)v，或者說弧<v，v′>與頂點(diǎn)v和v′相關(guān)聯(lián)。2341132如：頂點(diǎn)1、2互為鄰接點(diǎn)如：頂點(diǎn)1鄰接到頂點(diǎn)2頂點(diǎn)2鄰接自頂點(diǎn)1權(quán)與網(wǎng)在實(shí)際應(yīng)用中，圖的邊或弧上往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，我們將這種帶權(quán)的圖叫做加權(quán)圖或網(wǎng)，如圖所示。路徑和回路路徑：所謂頂點(diǎn)vp到頂點(diǎn)vq之間的路徑,是指頂點(diǎn)序列vp,vi1,vi2,…,vim,vq,其中（vp,vi1）,（vi1,vi2）,…（vim,vq）分別為圖中的邊。路徑長度：路徑上邊的數(shù)目稱為路徑長度。簡單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑?；芈坊颦h(huán)：如果路徑的起點(diǎn)和終點(diǎn)相同(即vp=vq),則稱此路徑為回路或環(huán)。如圖所示的無向圖中,頂點(diǎn)v1到頂點(diǎn)v5的路徑有兩條,分別為v1,v2,v3,v4與v1,v5,v4,路徑長度分別為3和2。v1到v5的兩條路徑都為簡單路徑。簡單回路：除第一頂點(diǎn)與最后一個(gè)頂點(diǎn)之外,其它頂點(diǎn)不重復(fù)出現(xiàn)的回路為簡單回路或者簡單環(huán)。連通圖和強(qiáng)連通圖在無向圖中，若從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱頂點(diǎn)i和頂點(diǎn)j是連通的。若任意兩個(gè)頂點(diǎn)都是連通的，則稱此無向圖為連通圖，否則稱為非連通圖。連通圖和非連通圖示例見圖:對于有向圖來說,若圖中任意一對頂點(diǎn)vi和vj(i≠j)均有從vi到vj及從vj到vi的有向路徑,則稱該有向圖是強(qiáng)連通的。強(qiáng)連通圖和非強(qiáng)連通圖示例見圖:連通分量和強(qiáng)連通分量無向圖中，極大的連通子圖為該圖的連通分量。顯然，任何連通圖的連通分量只有一個(gè)，即它本身，而非連通圖有多個(gè)連通分量。24351672435167有向圖中的極大強(qiáng)連通子圖稱為該有向圖的強(qiáng)連通分量。顯然，任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即它本身，而非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。下圖不是強(qiáng)連通的,但它有兩個(gè)強(qiáng)連通分量:132321頂點(diǎn)的度2341如：頂點(diǎn)1的度為3頂點(diǎn)的度是指依附于某頂點(diǎn)vi的邊數(shù),通常記為D(v)頂點(diǎn)的度132如：頂點(diǎn)2的入度為2出度為1有向圖中,要區(qū)別頂點(diǎn)的入度和出度的概念。頂點(diǎn)v的入度是指以v為終點(diǎn)的弧的數(shù)目記為ID(v)頂點(diǎn)v的出度是指以v為始點(diǎn)的弧的數(shù)目記為OD(v)顯然：D(v)=ID(v)+OD(v)7.2.1鄰接矩陣存儲法7.2.2鄰接表表示法7.2圖的存儲圖的抽象數(shù)據(jù)類型classGraph{//對象:由一個(gè)頂點(diǎn)的非空集合和一個(gè)邊集合構(gòu)成//每條邊由一對頂點(diǎn)來表示。public:Graph(); //建立一個(gè)空的圖voidInsertVertex(constTvertex); //插入一個(gè)頂點(diǎn)vertex,該頂點(diǎn)暫時(shí)沒有入邊voidInsertEdge(intv1,intv2,intweight); //在圖中插入一條邊(v1,v2,w)voidRemoveVertex(intv); //在圖中刪除頂點(diǎn)v和所有關(guān)聯(lián)到它的邊voidRemoveEdge(intv1,intv2); //在圖中刪去邊(v1,v2)boolIsEmpty(); //若圖中沒有頂點(diǎn),則返回true,否則返回falseTGetWeight(intv1,intv2); //函數(shù)返回邊(v1,v2)的權(quán)值intGetFirstNeighbor(intv); //給出頂點(diǎn)v第一個(gè)鄰接頂點(diǎn)的位置intGetNextNeighbor(intv,intw); //給出頂點(diǎn)v的某鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)};圖的存儲表示圖的模板基類在模板類定義中的數(shù)據(jù)類型參數(shù)表<classT,classE>中，T是頂點(diǎn)數(shù)據(jù)的類型，E是邊上所附數(shù)據(jù)的類型。這個(gè)模板基類是按照最復(fù)雜的情況（即帶權(quán)無向圖）來定義的，如果需要使用非帶權(quán)圖，可將數(shù)據(jù)類型參數(shù)表<classT,classE>改為<classT>。如果使用的是有向圖，也可以對程序做相應(yīng)的改動。

圖的模板基類

constintmaxWeight=

0x7fffffff; //無窮大的值(=)constintDefaultVertices=30; //最大頂點(diǎn)數(shù)(=n)template<classT,classE>classGraph{ //圖的類定義protected:intmaxVertices; //圖中最大頂點(diǎn)數(shù)intnumEdges; //當(dāng)前邊數(shù) intnumVertices; //當(dāng)前頂點(diǎn)數(shù) intGetVertexPos(Tvertex); //給出頂點(diǎn)vertex在圖中位置public:Graph(intsz=DefaultVertices); //構(gòu)造函數(shù)～Graph(); //析構(gòu)函數(shù)boolIsEmpty() //判圖空否{returnnumEdges==0;} intNumberOfVertices(){returnnumVertices;}//返回當(dāng)前頂點(diǎn)數(shù) intNumberOfEdges(){returnnumEdges;}//返回當(dāng)前邊數(shù) virtualT

GetValue(inti); //取頂點(diǎn)i的值virtualE

GetWeight(intv1,intv2);//取邊上權(quán)值virtualintGetFirstNeighbor(intv);//取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn) virtualintGetNextNeighbor(intv,intw);//取鄰接頂點(diǎn)w的下一鄰接頂點(diǎn) virtualboolInsertVertex(constTvertex);//插入一個(gè)頂點(diǎn)vertex virtualboolInsertEdge(intv1,intv2,Ecost); //插入邊(v1,v2),權(quán)為cost virtualboolRemoveVertex(intv); //刪去頂點(diǎn)v和所有與相關(guān)聯(lián)邊 virtualboolRemoveEdge(intv1,intv2); //在圖中刪去邊(v1,v2)};鄰接矩陣：用一個(gè)二維數(shù)組（矩陣）來表示圖中頂點(diǎn)之間的相鄰關(guān)系。

設(shè)圖G=(V,R)有n(n≥1)個(gè)頂點(diǎn),則G的鄰接矩陣是按如下定義的n階方陣:1若(vi,vj)或<vi,vj>∈R(G)aij=0反之例:圖G1、G2的鄰接矩陣分別表示為A1和A2,矩陣的行、列號對應(yīng)于圖中結(jié)點(diǎn)的號。01111010110110100110010102341132G1G2從無向圖的鄰接矩陣可以得出如下結(jié)論：

（1）矩陣是對稱的，可壓縮存儲（上（下）三角）;（2）第i行或第i列中1的個(gè)數(shù)為頂點(diǎn)i的度;（3）矩陣中1的個(gè)數(shù)的一半為圖中邊的數(shù)目;（4）很容易判斷頂點(diǎn)i和頂點(diǎn)j之間是否有邊相連(看矩陣中i行j列值是否為1)。從有向圖的鄰接矩陣可以得出如下結(jié)論:（1）矩陣不一定是對稱的;（2）第i行中1的個(gè)數(shù)為頂點(diǎn)i的出度;（3）第i列中1的個(gè)數(shù)為頂點(diǎn)i的入度;（4）矩陣中1的個(gè)數(shù)為圖中弧的數(shù)目;（5）很容易判斷頂點(diǎn)i和頂點(diǎn)j是否有弧相連.網(wǎng)的鄰接矩陣表示：若圖G是一個(gè)有n個(gè)頂點(diǎn)的網(wǎng)，則它的鄰接矩陣是具有如下性質(zhì)的n×n矩陣A：若<vi,vj>或(vi,vj)∈VR(G)反之∞5∞7∞∞4∞8∞∞∞∞∞5∞234158475例：一個(gè)有向網(wǎng)N及其鄰接矩陣的示例。n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲邊(弧);空間效率為O(n2)。對稀疏圖而言尤其浪費(fèi)空間。鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。鄰接矩陣表示法的C++語言類型描述如下：template<classT,classE>classGraphmtx:publicGraph<T,E>{private:T*VerticesList; //頂點(diǎn)表 E**Edge; //鄰接矩陣 intGetVertexPos(Tvertex){//給出頂點(diǎn)vertex在圖中的位置for(inti=0;i<numVertices;i++) if(VerticesList[i]==Vertex)returni; return-1; }; public:Graphmtx(intsz=DefaultVertices);//構(gòu)造函數(shù)～Graphmtx(){ //析構(gòu)函數(shù)delete[]VerticesList;delete[]Edge;}TGetValue(inti){//取頂點(diǎn)i的值,i不合理返回0 returni>=0&&i<=numVertices?VerticesList[i]:NULL;} EGetWeight(intv1,intv2){//取邊(v1,v2)上權(quán)值 returnv1!=-1&&v2!=-1?Edge[v1][v2]:0;}intGetFirstNeighbor(intv);//取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)intGetNextNeighbor(intv,intw); //取v的鄰接頂點(diǎn)w的下一鄰接頂點(diǎn) boolInsertVertex(constTvertex); //插入頂點(diǎn)vertex boolInsertEdge(intv1,intv2,Ecost);//插入邊(v1,v2),權(quán)值為cost boolRemoveVertex(intv);//刪去頂點(diǎn)v和所有與它相關(guān)聯(lián)的邊 boolRemoveEdge(intv1,intv2);//在圖中刪去邊(v1,v2)};template<classT,classE>Graphmtx<T,E>::Graphmtx(intsz){//構(gòu)造函數(shù)

maxVertices=sz;

numVertices=0;numEdges=0; inti,j;

VerticesList=newT[maxVertices];//創(chuàng)建頂點(diǎn)表

Edge=newE*[maxVertices]; for(i=0;i<maxVertices;i++)

Edge[i]=newE[maxVertices];//鄰接矩陣

for(i=0;i<maxVertices;i++)//矩陣初始化 for(j=0;j<maxVertices;j++)

Edge[i][j]=(E)((i==j)？0:maxWeight);};template<classT,classE>intGraphmtx<T,E>::GetFirstNeighbor(intv){//給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置,//如果找不到,則函數(shù)返回-1if(v==-1)return-1；for(intcol=0;col<numVertices;col++)if(Edge[v][col]&&Edge[v][col]<maxWeight)

returncol; return-1;};獲取第一個(gè)鄰接點(diǎn)template<classT,classE>intGraphmtx<T,E>::getNextNeighbor(intv,intw){//給出頂點(diǎn)v的某鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)if(v==-1||w==-1)return-1；for(intcol=w+1;col<numVertices;col++)

if(Edge[v][col]&&Edge[v][col]<maxWeight)

returncol;} return-1;};獲取下一個(gè)鄰接點(diǎn)

鄰接表（AdjacencyList）表示法是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。它包括兩個(gè)部分,一部分是鏈表,另一部分是向量。在鏈表部分中共有n個(gè)鏈表(n為頂點(diǎn)數(shù)),用來存放邊的信息。將每個(gè)單鏈表的表頭結(jié)點(diǎn)順序存儲在一個(gè)向量中。2341這樣，一個(gè)n個(gè)頂點(diǎn)的圖的鄰接表表示由表頭結(jié)點(diǎn)表與邊鏈表兩部分構(gòu)成：

(1)表頭結(jié)點(diǎn)表：由所有表頭結(jié)點(diǎn)以順序結(jié)構(gòu)（向量）的形式存儲.。表頭結(jié)點(diǎn)的結(jié)構(gòu)如圖所示，由兩部分構(gòu)成：數(shù)據(jù)域（vexdata）用于存儲頂點(diǎn)的名(值)；指針域（firstarc）用于指向鏈表中第一個(gè)頂點(diǎn)（即與頂點(diǎn)vi鄰接的第一個(gè)鄰接點(diǎn)）。vexdatafirstarc(2)邊鏈表：由鄰接點(diǎn)鏈?zhǔn)酱鎯Φ膯捂湵?。單鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成:鄰接點(diǎn)域(adjvex)指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置；數(shù)據(jù)域(info)存儲和邊(或弧)相關(guān)的信息,如權(quán)值等；鏈域(next)指向頂點(diǎn)vi的下一個(gè)鄰接點(diǎn)。adjvexinfonextarc例：23415∧4∧23415從無向圖的鄰接表可以得到如下結(jié)論：

（1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的度；（2）所有鏈表中結(jié)點(diǎn)數(shù)目的一半為圖中邊數(shù)；（3）占用的存儲單元數(shù)目為n+2e(e為邊數(shù))。從有向圖的鄰接表可以得到如下結(jié)論:（1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的出度；（2）所有鏈表中結(jié)點(diǎn)數(shù)目為圖中弧數(shù)；（3）占用的存儲單元數(shù)目為n+e。從有向圖的鄰接表可知，不能求出頂點(diǎn)的入度。若要求第i個(gè)頂點(diǎn)的入度，必須遍歷整個(gè)鄰接表，在所有邊鏈表中查找鄰接點(diǎn)域的值為i的結(jié)點(diǎn)并計(jì)數(shù)求和。由此可見，對于用鄰接表方式存儲的有向圖，求頂點(diǎn)的入度并不方便，它需要通過掃描整個(gè)鄰接表才能得到結(jié)果。

解決的方法：逆鄰接表法，對每一頂點(diǎn)vi再建立一個(gè)逆鄰接表，即對每個(gè)頂點(diǎn)vi建立一個(gè)所有以頂點(diǎn)vi為弧頭的弧的表，如圖所示：2341鄰接表的缺點(diǎn)：鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣方便。用鄰接表表示的圖的類定義

template<classT,classE>structEdge{ //邊鏈表結(jié)點(diǎn)的定義int

adjvex; //邊的另一頂點(diǎn)位置

E

info; //邊上的權(quán)值

Edge<T,E>*nextarc;//指向下一個(gè)邊鏈表結(jié)點(diǎn)的指針

Edge(){} //構(gòu)造函數(shù)

Edge(intnum,Ecost=0) //構(gòu)造函數(shù):adjvex(num),info(cost),nextarc(NULL){} booloperator!=(Edge<T,E>&R)const {returndest!=R.dest;} //判邊等否};template<classT,classE>structVertex{ //頂點(diǎn)的定義

Tvexdata; //頂點(diǎn)的名字

Edge<T,E>*firstarc; //邊鏈表的頭指針};template<classT,classE>classGraphlnk:publicGraph<T,E>{//圖的類定義private:

Vertex<T,E>*NodeTable;//頂點(diǎn)表(各邊鏈表的頭結(jié)點(diǎn)) intGetVertexPos(constTvertx){ //給出頂點(diǎn)vertex在圖中的位置 for(inti=0;i<numVertices;i++) if(NodeTable[i].vexdata==vertx)returni; return-1; }public:

Graphlnk(intsz=DefaultVertices);//構(gòu)造函數(shù) ~Graphlnk(); //析構(gòu)函數(shù)

E

GetWeight(intv1,intv2);//取邊(v1,v2)權(quán)值

T

GetValue(inti){ //取頂點(diǎn)i的值 return(i>=0&&i<NumVertices)?

NodeTable[i].vexdata:0;} boolInsertVertex(constT&vertex);boolRemoveVertex(intv);boolInsertEdge(intv1,intv2,Ecost); boolRemoveEdge(intv1,intv2);intGetFirstNeighbor(intv);intGetNextNeighbor(intv,intw); };template<classT,classE>Graphlnk<T,E>::Graphlnk(intsz){//構(gòu)造函數(shù)：建立一個(gè)空的鄰接表

maxVertices=sz;NodeTable=newVertex<T,E>[maxVertices];//創(chuàng)建頂點(diǎn)表數(shù)組assert(NodeTable);

numVertices=0;numEdges=0;for(inti=0;i<maxVertices;i++)

NodeTable[i].firstarc=NULL;};template<classT,classE>Graphlnk<T,E>::～Graphlnk(){ //析構(gòu)函數(shù)：刪除一個(gè)鄰接表for(inti=0;i<numVertices;i++){

Edge<T,E>*p=NodeTable[i].firstarc;while(p!=NULL){

NodeTable[i].firstarc=p->next;deletep;p=NodeTable[i].firstarc;} } delete[]NodeTable; //刪除頂點(diǎn)表數(shù)組};邊鏈表(單鏈表)的析構(gòu)獲取第一個(gè)鄰接點(diǎn)template<classT,classE>intGraphlnk<T,E>::GetFirstNeighbor(intv){//給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置,//如果找不到,則函數(shù)返回-1if(v==-1)return-1; //頂點(diǎn)v不存在

Edge<T,E>*p=NodeTable[v].firstarc;//對應(yīng)邊鏈表第一個(gè)邊結(jié)點(diǎn) if(p!=NULL)returnp->adjvex; //存在,返回第一個(gè)鄰接頂點(diǎn) return-1; //第一個(gè)鄰接頂點(diǎn)不存在};獲取下一個(gè)鄰接點(diǎn)template<classT,classE>intGraphlnk<T,E>::GetNextNeighbor(intv,intw){//給出頂點(diǎn)v的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)的位置,//若沒有下一個(gè)鄰接頂點(diǎn),則函數(shù)返回-1if(v!=-1){ //頂點(diǎn)v存在

Edge<T,E>*p=

NodeTable[v].firstarc;while(p!=NULL&&p->adjvex!=w)

p=p->nextarc; if(p!=NULL&&p->nextarc!=NULL)

returnp->nextarc->adjvex; //返回下一個(gè)鄰接頂點(diǎn) } return-1; //下一鄰接頂點(diǎn)不存在};討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個(gè)鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2.區(qū)別：①對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點(diǎn)編號一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號無關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。分析:在圖的鏈接存儲(鄰接表、逆鄰接表)中，表頭向量需要占用n個(gè)存儲單元，所有邊結(jié)點(diǎn)需要占用2e或e存儲單元，所以最多需要（n+2e）個(gè)存儲單元，稀疏圖采用這種存儲方式可節(jié)省存儲空間。 圖的遍歷：沿著某條搜索路徑對圖中所有頂點(diǎn)各作一次訪問。圖的遍歷比起樹的遍歷要復(fù)雜得多。圖中頂點(diǎn)關(guān)系是多對多的關(guān)系，圖可能是非連通圖，圖中還可能有回路存在，因此在訪問了某個(gè)頂點(diǎn)后，可能沿著某條路徑搜索后又回到該頂點(diǎn)上。

為了保證圖中的各頂點(diǎn)在遍歷過程中訪問且僅訪問一次，需要為每個(gè)頂點(diǎn)設(shè)一個(gè)訪問標(biāo)志。圖的遍歷為此我們設(shè)置一個(gè)訪問標(biāo)志數(shù)組visited[n]，用于標(biāo)示圖中每個(gè)頂點(diǎn)是否被訪問過，它的初始值為0(“假”)，表示頂點(diǎn)均未被訪問；一旦訪問過頂點(diǎn)vi，則置訪問標(biāo)志數(shù)組中的visited[i]為1(“真”)，以表示該頂點(diǎn)已訪問。根據(jù)搜索路徑的不同，圖的遍歷又分：

深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷

7.3.1深度優(yōu)先搜索遍歷7.3.2廣度優(yōu)先搜索遍歷7.3圖的遍歷

深度優(yōu)先搜索（Depth-FirstSearch）是指按照深度方向搜索，它類似于樹的先根遍歷，是樹的先根遍歷的推廣。特點(diǎn)：盡可能先對縱深方向進(jìn)行搜索。算法描述：從某個(gè)頂點(diǎn)v0出發(fā)，進(jìn)行dfs的算法描述如下：

(1)訪問v0。(2)

依次從v0的未被訪問的鄰接點(diǎn)出發(fā)作深度遍歷BAGDCFHEI下圖給出了一個(gè)深度優(yōu)先搜索的過程圖示，其中實(shí)箭頭代表訪問方向，虛箭頭代表回溯方向，箭頭旁邊的數(shù)字代表搜索順序，A為起始頂點(diǎn)。BAGDCFHEI遍歷過程深度優(yōu)先生成樹

若圖是連通的或強(qiáng)連通的，則從圖中某一個(gè)頂點(diǎn)出發(fā)可以訪問到圖中所有頂點(diǎn)，否則只能訪問到一部分頂點(diǎn)。另外，從剛才寫出的遍歷結(jié)果可以看出，從某一個(gè)頂點(diǎn)出發(fā)的遍歷結(jié)果是不唯一的。但是,若我們給定圖的存儲結(jié)構(gòu),則從某一頂點(diǎn)出發(fā)的遍歷結(jié)果應(yīng)是唯一的。分析與總結(jié)：分析連通圖的深度遍歷算法的實(shí)現(xiàn):(1)為防止重復(fù)訪問頂點(diǎn)，需為每個(gè)頂點(diǎn)設(shè)置一個(gè)訪問標(biāo)志visited[i]，其值為0時(shí)，表示頂點(diǎn)i未被訪問過；值為1時(shí)，表示頂點(diǎn)i已被訪問過。(2)算法中需依次找v0的各鄰接點(diǎn)，可根據(jù)不同的存儲結(jié)構(gòu)具體實(shí)現(xiàn)。訪問v0置訪問標(biāo)志visited[v0]=1w=GetFirstNeighbor(v0)w==0w已被訪問過dfs(w)w=GetNextNeighbor(v0,w)NNYY結(jié)束圖的深度優(yōu)先搜索算法template<classT,classE>voidDFS(Graph<T,E>G,constT

v){//從頂點(diǎn)v出發(fā)對圖G進(jìn)行深度優(yōu)先遍歷的主過程inti,loc,n=G.NumberOfVertices();//頂點(diǎn)個(gè)數(shù)bool*visited=newbool[n];//創(chuàng)建輔助數(shù)組 for(i=0;i<n;i++)visited

[i]=false; //輔助數(shù)組visited初始化

loc=G.GetVertexPos(v);

DFS(G,loc,visited);//從頂點(diǎn)0開始深度優(yōu)先搜索 delete[]visited; //釋放visited};template<classT,classE>voidDFS(Graph<T,E>G,intv,boolvisited[]){cout<<G.GetValue(v)<<'';//訪問頂點(diǎn)v

visited[v]=true; //作訪問標(biāo)記intw=G.GetFirstNeighbor(v);//第一個(gè)鄰接頂點(diǎn) while(w!=-1){ //若鄰接頂點(diǎn)w存在 if(!visited[w])DFS(G,w,visited); //若w未訪問過,遞歸訪問頂點(diǎn)w

w=G.GetNextNeighbor(v,w);//下一個(gè)鄰接頂點(diǎn)}};非連通圖的深度優(yōu)先搜索：若圖是非連通的或非強(qiáng)連通圖，則從圖中某一個(gè)頂點(diǎn)出發(fā)。不能用深度優(yōu)先搜索訪問到圖中所有頂點(diǎn)，而只能訪問到一個(gè)連通分量或只能訪問到一個(gè)強(qiáng)連通分量。這時(shí)，可以在每個(gè)連通分量或每個(gè)強(qiáng)連通分量中都選一個(gè)頂點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，最后將每個(gè)連通分量或每個(gè)強(qiáng)連通分量的遍歷結(jié)果合起來，則得到整個(gè)非連通圖的遍歷結(jié)果。非連通圖的遍歷算法實(shí)現(xiàn)與連通圖的只有一點(diǎn)不同，即對所有頂點(diǎn)進(jìn)行循環(huán)，反復(fù)調(diào)用連通圖的深度優(yōu)先搜索遍歷算法即可。具體實(shí)現(xiàn)如下：for(inti=1;i<=n;i++)if(!visited[i])DFS(G,i,visited);下圖是一個(gè)非連通圖，按照它的鄰接表進(jìn)行深度優(yōu)先搜索遍歷，三次調(diào)用DFS過程得到的訪問頂點(diǎn)序列為：1，2，4，3，95，6，78，10

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

（2）依次訪問v0的各個(gè)未被訪問的鄰接點(diǎn)。（3）分別從這些鄰接點(diǎn)（端結(jié)點(diǎn)）出發(fā)，依次訪問它們的各個(gè)未被訪問的鄰接點(diǎn)（新的端結(jié)點(diǎn)）。BAGDCFHEIBEDCGBAGDCFHEI遍歷過程廣度優(yōu)先生成樹分析該算法的實(shí)現(xiàn)：1、需設(shè)置訪問標(biāo)志數(shù)組，記錄已被訪問過的頂點(diǎn)。2、廣度優(yōu)先遍歷中，訪問過一個(gè)頂點(diǎn)后，下一個(gè)需要訪問的頂點(diǎn)可能是任何一個(gè)已訪問過的頂點(diǎn)的鄰接點(diǎn)；因此，為尋找下一個(gè)訪問頂點(diǎn)，需設(shè)置一個(gè)結(jié)構(gòu)來保存已訪問過的頂點(diǎn)。該結(jié)構(gòu)應(yīng)該是“隊(duì)列”：???這樣，與該隊(duì)列相關(guān)的操作過程如下：(1)開始時(shí)，將隊(duì)列初始化為空隊(duì)；(2)選擇出發(fā)點(diǎn)v，訪問v，置visited[v]，將v入隊(duì)；(3)如果隊(duì)列為空，轉(zhuǎn)到(9)；(4)將隊(duì)首元素出隊(duì)到v；(5)取v的第一個(gè)鄰接點(diǎn)w；(6)如果w不存在，則轉(zhuǎn)到(3)；(7)如果w未訪問則訪問w，置visited[w],并將w入隊(duì)；(8)取v的下一個(gè)鄰接點(diǎn)并賦給w，轉(zhuǎn)到(6);(9)遍歷結(jié)束。visit(v);visited[v]=1;q.EnQueue(v);隊(duì)空v=q.DeQueue();w=FirstNeighbor(v)visit(w);visited[w]=1;w入隊(duì)w==0w已訪問過w=NextNeighbor(v,w)NNNYYY結(jié)束BAGDCFHEIBEDCG000000000ABCDEFGHIvisited輸出：queue......v:w:ABEDCGFHIA111111111ABEDCGFHIBEDCGFHIfr廣度優(yōu)先搜索連通子圖的算法如下：

template<classT,classE>voidBFS(Graph<T,E>G,constTv0){//廣度優(yōu)先搜索圖G中v0所在的連通子圖inti,v,w,n=G.NumberOfVertices();

Queue<Vertex<T,E>>queue();//初始化空隊(duì)bool*visited=newbool[n];for(i=0;i<n;i++)visited[i]=false;v=G.GetVertexPos(v0);visit(v);visited[v]=1;queue.EnQueue(v)；//v進(jìn)隊(duì)

while(!queue.IsEmpty()){v=queue.DeQueue();//隊(duì)首元素出隊(duì)w=G.FirstNeighbor(v);//求v的第一個(gè)鄰接點(diǎn)while(w!=-1){if(!visited(w)){visit(w);visited[w]=True;queue.EnQueue(w);}w=G.NextNeighbor(v,w);//求v相對于w的下一個(gè)鄰接點(diǎn)}}}分析上述算法，圖中每個(gè)頂點(diǎn)至多入隊(duì)一次，因此外循環(huán)次數(shù)為n。

當(dāng)圖g采用鄰接表方式存儲，則當(dāng)結(jié)點(diǎn)v出隊(duì)后，內(nèi)循環(huán)次數(shù)等于結(jié)點(diǎn)v的度。由于訪問所有頂點(diǎn)的鄰接點(diǎn)的總的時(shí)間復(fù)雜度為O(d0+d1+d2+…+dn-1)=O(e)，因此圖采用鄰接表方式存儲，廣度優(yōu)先搜索算法的時(shí)間復(fù)雜度為O(n*e)；當(dāng)圖g采用鄰接矩陣方式存儲，由于找每個(gè)頂點(diǎn)的鄰接點(diǎn)時(shí)，內(nèi)循環(huán)次數(shù)等于n，因此廣度優(yōu)先搜索算法的時(shí)間復(fù)雜度為O(n2)。

非連通圖的廣度優(yōu)先搜索：與非連通圖的深度優(yōu)先搜索一樣，非連通的或非強(qiáng)連通圖的廣度優(yōu)先搜索從圖中某一個(gè)頂點(diǎn)出發(fā)，也不能訪問到圖中所有頂點(diǎn)，而只能訪問到一個(gè)連通子圖（既連通分量）或只能訪問到一個(gè)強(qiáng)連通子圖（既強(qiáng)連通分量）。遍歷算法實(shí)現(xiàn)時(shí)，對所有頂點(diǎn)進(jìn)行循環(huán)，反復(fù)調(diào)用連通圖的廣度優(yōu)先搜索遍歷算法即可。具體可以表示如下：for(inti=1;i<=n;i++)if(!visited[i])bfs(i);分析上述過程，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)質(zhì)上是通過邊或弧找鄰接點(diǎn)的過程。因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對頂點(diǎn)訪問的順序不同。深度優(yōu)先及廣度優(yōu)先遍歷圖的過程中，所經(jīng)過的邊的集合和頂點(diǎn)集合，一起構(gòu)成連通圖的極小連通子圖。它是連通圖的一顆生成樹。生成樹：是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有n-1條邊。由深度優(yōu)先搜索遍歷得到的生成樹，稱為深度優(yōu)先生成樹，由廣度優(yōu)先搜索遍歷得到的生成樹，稱為廣度優(yōu)先生成樹。生成樹與最小生成樹例：畫出下圖的生成樹DFS生成樹v0v1v2v4v4v3鄰接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成樹v0v1v3v2v4可以看出：圖的生成樹不是唯一的。當(dāng)按深度和廣度優(yōu)先搜索法進(jìn)行遍歷就可以得到兩種不同的生成樹。最小生成樹一般情況下，若圖中的每條邊給定了權(quán)值，這時(shí)，我們所關(guān)心的不是生成樹，而是生成樹中邊上權(quán)值之和。若某生成樹中每條邊上權(quán)值之和達(dá)到最小，稱其為最小代價(jià)生成樹（MinimumCostSpanningTree），簡稱為最小生成樹(MST)。例：連通圖的生成樹。413265666555213441326566554(a)41326562134(b)41326552134(c)其中(a)的權(quán)值之和為26,(b)的權(quán)值之和為16,(c)的權(quán)值之和為15,可以證明(c)為一棵最小生成樹。欲在n個(gè)城市間建立通信網(wǎng)，則n個(gè)城市應(yīng)鋪n-1條線路；但因?yàn)槊織l線路都會有對應(yīng)的經(jīng)濟(jì)成本，而n個(gè)城市可能有n(n-1)/2條線路，那么，如何選擇n–1條線路，使總費(fèi)用最少？典型用途：數(shù)學(xué)模型：頂點(diǎn)———表示城市，有n個(gè)；邊————表示線路，有n–1條；邊的權(quán)值—表示線路的經(jīng)濟(jì)代價(jià)；連通網(wǎng)——表示n個(gè)城市間通信網(wǎng)。顯然此連通網(wǎng)是一個(gè)生成樹！如何選擇其中的n-1條線路(邊)在n個(gè)城市間建成全都能相互通訊的網(wǎng),并且總的建設(shè)花費(fèi)為最小?——這就是求該網(wǎng)絡(luò)的最小生成樹問題。最小生成樹有如下重要性質(zhì)(MST性質(zhì))：設(shè)N=(V,R)是一連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若（u,v）是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U，則存在一棵包含邊（u,v）的最小生成樹。我們可以利用MST性質(zhì)來生成一個(gè)連通網(wǎng)的最小生成樹。普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法便是利用了這個(gè)性質(zhì)。1.普里姆算法基本思想：每一次在滿足如下條件的邊中，選一條最小權(quán)值的邊。條件：一端頂點(diǎn)已入選，而另一端未選。具體描述如下：假設(shè)N=(V,R)是連通網(wǎng)，TE為最小生成樹中邊的集合。（1）初始U={u0}(u0∈V),TE=

（2）在所有u∈U,v∈V-U的邊中選一條代價(jià)最小的邊(u0,v0)并入集合TE，同時(shí)將v0并入U(xiǎn)；（3）重復(fù)（2），直到U=V為止。此時(shí)，TE中必含有n-1條邊，則T=（V，TE）為N的最小生成樹。4132656665552134

例：利用普里姆算法從v1開始構(gòu)造最小生成樹。1666555213413135522446可以看出，普利姆算法逐步增加U中的頂點(diǎn)，可稱為“加點(diǎn)法”。為了實(shí)現(xiàn)這個(gè)算法需要設(shè)置一個(gè)輔助數(shù)組closedge[]，以記錄從U到V-U具有最小代價(jià)的邊。對每個(gè)頂點(diǎn)v∈V-U，在輔助數(shù)組中存在一個(gè)分量closedge[v],它包括兩個(gè)域adjvex和lowcost,其中l(wèi)owcost存儲該邊上的權(quán)，顯然有closedge[v].lowcost=Min({cost(u,v)|u∈U})struct{VertexDataadjvex;intlowcost;}closedge[MAX_V_N];//求最小生成樹時(shí)的輔助數(shù)組

typedefstruct{VertexDatavexs[MAX_V_N];

//頂點(diǎn)向量

ArcNodearcs[MAX_V_N][MAX_V_N];

//鄰接矩陣

intvexnum,arcnum;

//圖的頂點(diǎn)數(shù)和弧數(shù)

GraphKindkind;

//圖的種類標(biāo)志}AdjMatrix;//(AdjacencyMatrixGraph)

typedefstructArcNode{AdjTypeadj;

//AdjType是頂點(diǎn)關(guān)系類型，對無權(quán)圖，用1或0表示是否相鄰；對帶權(quán)圖，則為權(quán)值類型

InfoType*info;

//該弧相關(guān)信息的指針}ArcNode;假設(shè)開始頂點(diǎn)就選為頂點(diǎn)1，首先有U={1}，U-V={2，3，4，5，6}i123456closedge[i].adjvex111111closedge[i].lowcost0615∞∞4132656665552134413265651∞∞for(i=1;i<=gn.vexnum;i++){closedge[i].adjvex=k0;//k0∈Uclosedge[i].lowcost=gn.arcs[k0][i].adj;}

i123456closedge[i].adjvex133133closedge[i].lowcost050564

在頂點(diǎn)k1并入U(xiǎn)之后，更新closedge［i］for(i=1;i<=gn.vexnum;i++)if(gn.arcs[k1][i].adj<closedge[i].lowcost){closedge[i].lowcost=gn.arcs[k1][i].adj;closedge[i].adjvex=k1;}

41326565514U={1,3}，U-V={2，4，5，6}i123456closedge[i].adjvex111111closedge[i].lowcost0615∞∞i123456closedge[i].adjvex133636closedge[i].lowcost0502

60U={1,3,6}，U-V={2，4，5}24132656514i123456closedge[i].adjvex133133closedge[i].lowcost050564

i123456closedge[i].adjvex133636closedge[i].lowcost0502

6041326565142U={1,3,6,4}，U-V={2，5}i123456closedge[i].adjvex133436closedge[i].lowcost050060i123456closedge[i].adjvex123426closedge[i].lowcost000030U={1,3,6,4,2}，U-V={5}24132655143i123456closedge[i].adjvex133436closedge[i].lowcost050060i123456closedge[i].adjvex123456closedge[i].lowcost000000U={1,3,6,4,2,5}，U-V={}41326552134i123456closedge[i].adjvex123426closedge[i].lowcost000030普里姆算法可描述如下：

struct{VertexDataadjvex;intlowcost;}closedge[MAX_V_N];//求最小生成樹時(shí)的輔助數(shù)組MSpTree-Prim(AdjMatrixgn,VertexDatau){//從頂點(diǎn)u出發(fā)，按普里姆算法構(gòu)造連通網(wǎng)gn的最小生成樹，并輸出生成樹的每條邊

k=LocateVertex(gn,u);//k為頂點(diǎn)u的位置

closedge［k］.lowcost=0;//初始化，U={u}for(i=0;i<gn.vexnum;i++)if(i!=k){//對V-U中的頂點(diǎn)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］中存有當(dāng)前最小邊（u0,v0）的信息u0=closedge［k0］.adjvex;//u0∈Uv0=gn.vexs［k0］//v0∈V-Uprintf(u0,v0);//輸出生成樹的當(dāng)前最小邊(u0,v0)closedge[k0].lowcost=0;//將頂點(diǎn)v0納入U(xiǎn)集合for(i=0;i<vexnum;i++)

//在頂點(diǎn)v0并入U(xiǎn)之后，更新closedge［i］if(gn.arcs[k0][i].adj<closedge[i].lowcost){closedge[i].lowcost=gn.arcs[k0][i].adj;closedge[i].adjvex=v0;}}}2.克魯斯卡爾算法

基本思想：每一次在滿足如下條件的邊中，選一條權(quán)值最小的邊。條件：與已選邊不構(gòu)成回路。41326516191865621143311例：利用克魯斯卡爾算法構(gòu)造最小生成樹。41326516186561411可以看出，克魯斯卡爾算法逐步增加生成樹的邊，與普里姆算法相比，可稱為“加邊法”。普里姆算法的時(shí)間效率為O(n2);克魯斯卡爾算法的時(shí)間效率為O(eloge)。典型用途：求圖的最短路徑問題用途很廣，例如：交通網(wǎng)絡(luò)中常常提出這樣的問題：從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短?交通網(wǎng)絡(luò)可用帶權(quán)有向圖來表示。頂點(diǎn)表示城市名稱，邊表示兩個(gè)城市有路連通，邊上權(quán)值可表示兩城市之間的距離、交通費(fèi)或途中所花費(fèi)的時(shí)間等。如何能夠使一個(gè)城市到另一個(gè)城市的運(yùn)輸時(shí)間最短或運(yùn)費(fèi)最??？這就是一個(gè)求兩座城市間的最短路徑問題。最短路徑問題抽象：在帶權(quán)有向圖中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑（注：最短路徑與最小生成樹不同，路徑上不一定包含n個(gè)頂點(diǎn)）本節(jié)討論帶權(quán)有向圖（有向網(wǎng)）的兩種最短路徑問題：（1）求一結(jié)點(diǎn)到其它結(jié)點(diǎn)的最短路徑※（2）求任意兩點(diǎn)間的最短路徑

7.5.1單源最短路徑7.5.2任意兩點(diǎn)間的最短路徑7.5最短路徑求某一頂點(diǎn)到其它各頂點(diǎn)的最短路徑:設(shè)從頂點(diǎn)v1出發(fā),找從它到圖中所有其它各頂點(diǎn)的最短路徑。迪杰斯特拉(Dijkstra)提出了一個(gè)按路徑長度遞增的順序產(chǎn)生最短路徑的方法。算法的基本思想是:?把圖中頂點(diǎn)集合分成兩組，第一組為集合S，存放已求出其最短路徑的頂點(diǎn)，第二組為尚未確定最短路徑的頂點(diǎn)集合是V-S（用U表示），其中V為網(wǎng)中所有頂點(diǎn)集合。?按最短路徑長度遞增的順序逐個(gè)把U中的頂點(diǎn)加到S中，直到S中包含全部頂點(diǎn)，而U為空。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度，U中的頂點(diǎn)的距離從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。算法分析：我們可以將圖中的頂點(diǎn)分為兩組：S——已求出的最短路徑的終點(diǎn)集合(開始為{v0})V-S——尚未求出最短路徑的頂點(diǎn)集合(開始為V－{v0}的全部結(jié)點(diǎn))。按最短路徑長度的遞增順序逐個(gè)將第二組的頂點(diǎn)加入到第一組中。引進(jìn)輔助向量dist[]，它的每一個(gè)分量dist[i]表示已經(jīng)找到的且從開始點(diǎn)v0到每一個(gè)終點(diǎn)vi的當(dāng)前最短路徑的長度。它的初態(tài)為：如果從v0到vi有弧，則dist[i]為弧的權(quán)值；否則，dist[i]為∞。

設(shè)置一個(gè)路徑向量path[n]，其中path[i]為從源點(diǎn)到vi點(diǎn)的最短路徑上該點(diǎn)的前趨頂點(diǎn)。找下一條長度次短的路徑假設(shè)該次短路徑的終點(diǎn)是vk，則這條路徑可能是(v0,vk)或者是(v0,vj,vk)V0V3V2V4V1V5455010102015153353015例：S＝{V0}U＝V-S＝{V1,V2,

V3,

V4,

V5}dist[1]dist[2]dist[3]dist[4]dist[5]V0到Vi的距離dist[i]:初始：5010∞45∞V0path12345000V0V3V2V4V1V5455010102015153353015例：S＝{V0,V2}U＝V-S＝{V1,

V3,

V4,

V5}dist[1]dist[2]dist[3]dist[4]dist[5]V0到Vi的距離dist[i]:5010∞45∞V0S＝{V0}U＝V-S＝{V1,V2,

V3,

V4,

V5}V210接下來，V0到Vi的距離是min({V0Vi}，{V0

V2Vi})path12345000V0V3V2V4V1V5455010102015153353015例：S＝{V0,V2}U＝V-S＝{V1,

V3,

V4,

V5}dist[1]dist[2]dist[3]dist[4]dist[5]V0到Vi的距離dist[i]:5010∞45∞V0V210{V0V1}為50{V0

V2V1}為∞{V0V3}為∞

{V0

V2V3}為2525{V0V4}為45{V0

V2V4}為∞

{V0V5}為∞

{V0

V2V5}為∞

S＝{V0,V2,

V3

}U＝V-S＝{V1,

V4,

V5}15V3接下來，V0到Vi的距離是min({V0Vi}，{V0

V3Vi})注意：V0到V3的距離是25path123450002V0V3V2V4V1V5455010102015153353015例：dist[1]dist[2]dist[3]dist[4]dist[5]V0到Vi的距離dist[i]:501045∞V0V210{V0V1}為50{V0

V3V1}為4025{V0V4}為45{V0

V3V4}為60

{V0V5}為∞

{V0

V3V5}為∞

S＝{V0,V2,

V3

}U＝V-S＝{V1,

V4,

V5}15V340S＝{V0,V2,

V3

,

V1}U＝V-S＝{V4,

V5}V115接下來，V0到Vi的距離是min({V0Vi}，{V0

V1Vi})注意：V0到V1的距離是40path1234500023V0V3V2V4V1V5455010102015153353015例：dist[1]dist[2]dist[3]dist[4]dist[5]V0到Vi的距離dist[i]:1045∞V0V21025{V0V4}為45{V0

V1V4}為50

{V0V5}為∞

{V0

V1V5}為∞

15V340S＝{V0,V2,

V3

,

V1}U＝V-S＝{V4,

V5}V115S＝{V0,V2,

V3

,

V1,

V4}U＝V-S＝{V5}接下來，V0到Vi的距離是min({V0Vi}，{V0

V4Vi})注意：V0到V4的距離是45V445path123453002V0V3V2V4V1V5455010102015153353015例：dist[1]dist[2]dist[3]dist[4]dist[5]V0到Vi的距離dist[i]:1045∞V0V21025{V0V5}為∞

{V0

V4V5}為∞

15V340V115S＝{V0,V2,

V3

,

V1,

V4}U＝V-S＝{V5}V5S＝{V0,V2,

V3

,

V1,

V4,

V5}U＝V-S＝{}算法結(jié)束。V445path123453002例：則：頂點(diǎn)V0到其余各頂點(diǎn)Vi的最短路徑分別為：:V0到V1的最短路徑是{V0V2V3V1

}，距離值為40V0到V2的最短路徑是{V0V2}，距離值為10V0到V3的最短路徑是{V0V2V3

}，距離值為25V0到V4的最短路徑是{V0V4

}，距離值為45V0到V5無最短路徑.V0V3V2V4V1V5455010102015153353015V0V21015V3V115V5V445迪杰斯特拉算法實(shí)現(xiàn)的主要步驟如下：

g為用鄰接矩陣表示的帶權(quán)圖。

S←{v0}，dist[i]=g.arcs[v0][vi]；將v0到其余頂點(diǎn)的路徑長度初始化為權(quán)值；(2)比較dist[i]，找到頂點(diǎn)vk，使得

dist[k]=Min{dist[i]},i,k∈V；將vk并入S集(3)比較<v0,vi>與<v0,vk,vi>的大小，若dist[k]+g.arcs[k][i]<dist[i]則將dist[i]修改為dist[k]+g.arcs[k][i]；同時(shí)修改path[i]的值。(4)重復(fù)(2)、(3)n-1次，即可按最短路徑長度的遞增順序，逐個(gè)求出v0到圖中其它每個(gè)頂點(diǎn)的最短路徑。求最短路徑的算法描述如下：WeightTypedist[n];intpath[n],VertexSets[n];//s為已找到最短路徑的終點(diǎn)集合,若s[i]=1,則i∈s;//path[i]中存放頂點(diǎn)i的當(dāng)前最短路徑上該點(diǎn)的前趨頂點(diǎn);//dist[i]中存放頂點(diǎn)i的當(dāng)前最短路徑長度ShortestPath_DJS(AdjMatrixg,intv0){fo