第7章圖及其應用

第7章圖及其應用 圖(Graph)：是一種網狀數據結構。是頂點集V和連接這些頂點的弧集(邊集)R所組成的結構記為:G=(V,R）

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

圖的模板基類

constintmaxWeight=

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

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

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

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

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

maxVertices=sz;

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

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

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){//給出頂點位置為v的第一個鄰接頂點的位置,//如果找不到,則函數返回-1if(v==-1)return-1；for(intcol=0;col<numVertices;col++)if(Edge[v][col]&&Edge[v][col]<maxWeight)

returncol; return-1;};獲取第一個鄰接點template<classT,classE>intGraphmtx<T,E>::getNextNeighbor(intv,intw){//給出頂點v的某鄰接頂點w的下一個鄰接頂點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;};獲取下一個鄰接點

鄰接表（AdjacencyList）表示法是圖的一種鏈式存儲結構。它包括兩個部分,一部分是鏈表,另一部分是向量。在鏈表部分中共有n個鏈表(n為頂點數),用來存放邊的信息。將每個單鏈表的表頭結點順序存儲在一個向量中。2341這樣，一個n個頂點的圖的鄰接表表示由表頭結點表與邊鏈表兩部分構成：

(1)表頭結點表：由所有表頭結點以順序結構（向量）的形式存儲.。表頭結點的結構如圖所示，由兩部分構成：數據域（vexdata）用于存儲頂點的名(值)；指針域（firstarc）用于指向鏈表中第一個頂點（即與頂點vi鄰接的第一個鄰接點）。vexdatafirstarc(2)邊鏈表：由鄰接點鏈式存儲的單鏈表。單鏈表中每個結點由三個域組成:鄰接點域(adjvex)指示與頂點vi鄰接的點在圖中的位置；數據域(info)存儲和邊(或弧)相關的信息,如權值等；鏈域(next)指向頂點vi的下一個鄰接點。adjvexinfonextarc例：23415∧4∧23415從無向圖的鄰接表可以得到如下結論：

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

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

template<classT,classE>structEdge{ //邊鏈表結點的定義int

adjvex; //邊的另一頂點位置

E

info; //邊上的權值

Edge<T,E>*nextarc;//指向下一個邊鏈表結點的指針

Edge(){} //構造函數

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

Tvexdata; //頂點的名字

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

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

Graphlnk(intsz=DefaultVertices);//構造函數 ~Graphlnk(); //析構函數

E

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

T

GetValue(inti){ //取頂點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){//構造函數：建立一個空的鄰接表

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

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

NodeTable[i].firstarc=NULL;};template<classT,classE>Graphlnk<T,E>::～Graphlnk(){ //析構函數：刪除一個鄰接表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; //刪除頂點表數組};邊鏈表(單鏈表)的析構獲取第一個鄰接點template<classT,classE>intGraphlnk<T,E>::GetFirstNeighbor(intv){//給出頂點位置為v的第一個鄰接頂點的位置,//如果找不到,則函數返回-1if(v==-1)return-1; //頂點v不存在

Edge<T,E>*p=NodeTable[v].firstarc;//對應邊鏈表第一個邊結點 if(p!=NULL)returnp->adjvex; //存在,返回第一個鄰接頂點 return-1; //第一個鄰接頂點不存在};獲取下一個鄰接點template<classT,classE>intGraphlnk<T,E>::GetNextNeighbor(intv,intw){//給出頂點v的鄰接頂點w的下一個鄰接頂點的位置,//若沒有下一個鄰接頂點,則函數返回-1if(v!=-1){ //頂點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; //返回下一個鄰接頂點 } return-1; //下一鄰接頂點不存在};討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數等于一行中非零元素的個數。2.區(qū)別：①對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。②鄰接矩陣的空間復雜度為O(n2),而鄰接表的空間復雜度為O(n+e)。分析:在圖的鏈接存儲(鄰接表、逆鄰接表)中，表頭向量需要占用n個存儲單元，所有邊結點需要占用2e或e存儲單元，所以最多需要（n+2e）個存儲單元，稀疏圖采用這種存儲方式可節(jié)省存儲空間。 圖的遍歷：沿著某條搜索路徑對圖中所有頂點各作一次訪問。圖的遍歷比起樹的遍歷要復雜得多。圖中頂點關系是多對多的關系，圖可能是非連通圖，圖中還可能有回路存在，因此在訪問了某個頂點后，可能沿著某條路徑搜索后又回到該頂點上。

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

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

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

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

(1)訪問v0。(2)

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

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

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

[i]=false; //輔助數組visited初始化

loc=G.GetVertexPos(v);

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

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

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

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

（2）依次訪問v0的各個未被訪問的鄰接點。（3）分別從這些鄰接點（端結點）出發(fā)，依次訪問它們的各個未被訪問的鄰接點（新的端結點）。BAGDCFHEIBEDCGBAGDCFHEI遍歷過程廣度優(yōu)先生成樹分析該算法的實現：1、需設置訪問標志數組，記錄已被訪問過的頂點。2、廣度優(yōu)先遍歷中，訪問過一個頂點后，下一個需要訪問的頂點可能是任何一個已訪問過的頂點的鄰接點；因此，為尋找下一個訪問頂點，需設置一個結構來保存已訪問過的頂點。該結構應該是“隊列”：???這樣，與該隊列相關的操作過程如下：(1)開始時，將隊列初始化為空隊；(2)選擇出發(fā)點v，訪問v，置visited[v]，將v入隊；(3)如果隊列為空，轉到(9)；(4)將隊首元素出隊到v；(5)取v的第一個鄰接點w；(6)如果w不存在，則轉到(3)；(7)如果w未訪問則訪問w，置visited[w],并將w入隊；(8)取v的下一個鄰接點并賦給w，轉到(6);(9)遍歷結束。visit(v);visited[v]=1;q.EnQueue(v);隊空v=q.DeQueue();w=FirstNeighbor(v)visit(w);visited[w]=1;w入隊w==0w已訪問過w=NextNeighbor(v,w)NNNYYY結束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();//初始化空隊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進隊

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

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

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

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

typedefstruct{VertexDatavexs[MAX_V_N];

//頂點向量

ArcNodearcs[MAX_V_N][MAX_V_N];

//鄰接矩陣

intvexnum,arcnum;

//圖的頂點數和弧數

GraphKindkind;

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

typedefstructArcNode{AdjTypeadj;

//AdjType是頂點關系類型，對無權圖，用1或0表示是否相鄰；對帶權圖，則為權值類型

InfoType*info;

//該弧相關信息的指針}ArcNode;假設開始頂點就選為頂點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

在頂點k1并入U之后，更新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];//求最小生成樹時的輔助數組MSpTree-Prim(AdjMatrixgn,VertexDatau){//從頂點u出發(fā)，按普里姆算法構造連通網gn的最小生成樹，并輸出生成樹的每條邊

k=LocateVertex(gn,u);//k為頂點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∈Uv0=gn.vexs［k0］//v0∈V-Uprintf(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;}}}2.克魯斯卡爾算法

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

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

設置一個路徑向量path[n]，其中path[i]為從源點到vi點的最短路徑上該點的前趨頂點。找下一條長度次短的路徑假設該次短路徑的終點是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＝{}算法結束。V445path123453002例：則：頂點V0到其余各頂點Vi的最短路徑分別為：:V0到V1的最短路徑是{V0V2V3V1

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

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

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

g為用鄰接矩陣表示的帶權圖。

S←{v0}，dist[i]=g.arcs[v0][vi]；將v0到其余頂點的路徑長度初始化為權值；(2)比較dist[i]，找到頂點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]；同時修改path[i]的值。(4)重復(2)、(3)n-1次，即可按最短路徑長度的遞增順序，逐個求出v0到圖中其它每個頂點的最短路徑。求最短路徑的算法描述如下：WeightTypedist[n];intpath[n],VertexSets[n];//s為已找到最短路徑的終點集合,若s[i]=1,則i∈s;//path[i]中存放頂點i的當前最短路徑上該點的前趨頂點;//dist[i]中存放頂點i的當前最短路徑長度ShortestPath_DJS(AdjMatrixg,intv0){fo