1第12章圖的基本概念圖的定義圖的術語圖的運算圖的存儲圖的遍歷圖遍歷的應用2圖的定義圖可以用G=(V,E)表示。其中，V是頂點的集合，E是鏈接頂點的邊（?。┑募?。如果邊是有方向的，稱為有向圖。有向圖的邊用<>表示。<A,B>表示從A出發(fā)到B的一條邊。在有向圖中，<A,B>和<B,A>是不一樣的。如果邊是無方向的，稱為無向圖。無向圖的邊通常用圓括號表示。（A，B）表示頂點A和B之間有一條邊。無向圖也稱為雙向圖。加權圖：邊被賦予一個權值的圖稱為加權圖。如果圖是有向的，稱為加權有向圖，如果是無向的，稱為加權無向圖。3如G1：V={A，B，C，D}，

E={<A,B>,<B,A>,<A,C>,<C,A>,<C,D>,<D,A>}表示的圖如下所示ABCD4ABCDEV={A，B，C，D，E}，E={（A，B），（A，C），（B，D），（B,E),

（D，E），（C，E）}無向圖512435661655563421243566165556342加權圖中邊的表示：<Vi,Vj,W>或(Vi,Vj,W)加權圖6第12章圖的基本概念圖的定義圖的術語圖的運算圖的存儲圖的遍歷圖遍歷的應用7圖的基本術語鄰接：如（Vi，Vj）是圖中的一條邊，則稱Vi和Vj是鄰接的。如<Vi，Vj>是圖中的一條邊，則稱Vi鄰接到Vj，或Vj和Vi鄰接。度：無向圖中鄰接于某一結點的邊的總數。入度：有向圖中進入某一結點的邊數，稱為該結點的入度出度：有向圖中離開某一結點的邊數，稱為該結點的出度8子圖ABCDACABCD有向圖G1的子圖ABCD有向圖G1設有兩個圖G=（V，E）和G‘=（V’，E’），如果則稱G’是G的子圖9無向圖G2ABCDEABDEAABCDABCDE無向圖G2的子圖10路徑和路徑長度對1<i<N，結點序列w1,w2,……wN中的結點對（wi,wi+1）都有（wi,wi+1）∈

E或<wi,wi+1>∈E，那么，w1,w2,……wN是圖中的一條路徑。非加權的路徑長度就是組成路徑的邊數，對于路徑w1,w2,……wN，非加權路徑長度為N-1。加權路徑長度是指路徑上所有邊的權值之和。

簡單路徑和環(huán)：如果一條路徑上的所有結點，除了起始結點和終止結點可能相同外，其余的結點都不相同，則稱其為簡單路徑。一個回路或環(huán)是一條簡單路徑，其起始結點和終止結點相同，且路徑長度至少為1。11無向圖的連通性連通：頂點v至v’

之間有路徑存在連通圖：無向圖G的任意兩點之間都是連通的，則稱G是連通圖。連通分量：非連通圖中的極大連通子圖12ABCDEFGIJLHMKABCDEHMFGJILK無向圖G無向圖G的三個連通分量13有向圖的連通性強連通圖：有向圖G的任意兩點之間都是連通的，則稱G是強連通圖。強連通分量：極大連通子圖弱連通圖：如有向圖G不是強連通的，但如果把它看成是無向圖時是連通的，則稱該圖是弱連通的14有向圖G有向圖G的兩個強連通分量ABCDABCD不是強連通圖。因為B到其他結點都沒有路徑。但此圖是弱連通的。15完全圖完全圖：每兩個節(jié)點之間都有邊的無向圖稱為完全圖。完全圖有n(n-1)/2條邊的無向圖。其中n是結點個數。即有向完全圖：每兩個節(jié)點之間都有兩條弧的有向圖稱為有向完全圖。有向完全圖有n(n-1)條邊。其中n是結點個數。即如果一個有向圖中沒有環(huán)，則稱為有向無環(huán)圖，簡寫為DAGABCD無向完全圖16生成樹ABCDEHMABCDEHM無向圖G無向圖G的生成樹

生成樹是連通圖的極小連通子圖。包含圖的所有n個結點，但只含圖的n-1條邊。在生成樹中添加一條邊之后，必定會形成回路或環(huán)。17第12章圖的基本概念圖的定義圖的術語圖的運算圖的存儲圖的遍歷圖遍歷的應用18圖的運算常規(guī)操作：構造一個由若干個結點、若干條邊組成的圖；判斷兩個結點之間是否有邊存在；在圖中添加或刪除一條邊；返回圖中的結點數或邊數；按某種規(guī)則遍歷圖中的所有結點。和應用緊密結合的運算：拓撲排序找最小生成樹找最短路徑等。19圖的抽象類template<classTypeOfEdge>classgraph{ public: virtualboolinsert(intu,intv,TypeOfEdgew)=0; virtualboolremove(intu,intv)=0; virtualboolexist(intu,intv)const=0; virtualnumOfVer()const{returnVers;} virtualnumOfEdge()const{returnEdges;} protected: intVers,Edges;};20第12章圖的基本概念圖的定義圖的術語圖的運算圖的存儲圖的遍歷圖遍歷的應用21圖的存儲鄰接矩陣和加權鄰接矩陣鄰接表22鄰接矩陣—有向圖設有向圖具有n個結點，則用n行n列的布爾矩陣A表示該有向圖如果i至j有一條有向邊,

A[i,j]=1,如果i至j沒有一條有向邊,A[i,j]=0

ABCD表示成右圖矩陣0110000000011000注意：出度:i行之和。入度:j列之和。23鄰接矩陣—有向圖ABCD表示成右圖矩陣0110000000011000在物理實現時的考慮：分別用0、1、2、3分別標識結點A、B、C、D。而將真正的數據場之值放入以個一維數組之中。注意：這里的數據場之值是邏輯意義上的。01230123DABC012324鄰接矩陣—無向圖設無向圖具有n個結點，則用n行n列的布爾矩陣A表示該無向圖；并且A[i,j]=1,如果i至j有一條無向邊；A[i,j]=0如果i至j沒有一條無向邊表示成右圖矩陣0110010011100010100101110ABCDE在物理實現時的考慮，和前一頁的無向圖類似。注意：i結點的度:i行或

i列之和。25加權的鄰接矩陣—有向圖設有向圖具有n個結點，則用n行n列的矩陣A表示該有向圖；如果i至j有一條有向邊且它的權值為a，則A[i,j]=a。如果i至j沒有一條有向邊。則A[i,j]=空或其它標志表示成右圖矩陣∞ab∞

∞

∞

∞

b∞

∞

∞ba

∞a∞ABCDaaabbb26鄰接矩陣的特點優(yōu)點：判斷任意兩點之間是否有邊方便，僅耗費O(1)時間。缺點：即使<<n2

條邊，也需內存n2

單元，太多;僅讀入數據耗費O(n2)時間，太長。而大多數的圖的邊數遠遠小于n2。27鄰接矩陣類的定義template<classTypeOfVer,classTypeOfEdge>classadjMatrixGraph:publicgraph<TypeOfEdge>{public:adjMatrixGraph(intvSize,constTypeOfVerd[],TypeOfEdgenoEdgeFlag); boolinsert(intu,intv,TypeOfEdgew); boolremove(intu,intv); boolexist(intu,intv)const; ~adjMatrixGraph()；

private: TypeOfEdge**edge;//存放鄰接矩陣

TypeOfVer*ver;//存放結點值

TypeOfEdgenoEdge;//鄰接矩陣中的∞的表示值};28構造函數template<classTypeOfVer,classTypeOfEdge>adjMatrixGraph<TypeOfVer,TypeOfEdge>::adjMatrixGraph(intvSize,constTypeOfVerd[],TypeOfEdgenoEdgeFlag){inti,j;Vers=vSize;Edges=0;noEdge=noEdgeFlag;//存放結點的數組的初始化

ver=newTypeOfVer[vSize];for(i=0;i<vSize;++i)ver[i]=d[i];29//鄰接矩陣的初始化

edge=newTypeOfEdge*[vSize];for(i=0;i<vSize;++i){

edge[i]=newTypeOfEdge[vSize]; for(j=0;j<vSize;++j)edge[i][j]=noEdge; edge[i][i]=0;}}30析構函數template<classTypeOfVer,classTypeOfEdge>adjMatrixGraph<TypeOfVer,TypeOfEdge>::~adjMatrixGraph(){ delete[]ver; for(inti=0;i<Vers;++i)delete[]edge[i

delete[]edge;}31Insert函數template<classTypeOfVer,classTypeOfEdge>booladjMatrixGraph<TypeOfVer,TypeOfEdge>::insert(intu,intv,TypeOfEdgew){if(u<0||u>Vers-1||v<0||v>Vers-1)returnfalse;if(edge[u][v]!=noEdge)returnfalse;edge[u][v]=w;++Edges;returntrue;}32Remove函數template<classTypeOfVer,classTypeOfEdge>booladjMatrixGraph<TypeOfVer,TypeOfEdge>::remove(intu,intv){if(u<0||u>Vers-1||v<0||v>Vers-1)returnfalse;if(edge[u][v]==noEdge)returnfalse;edge[u][v]=noEdge;--Edges;returntrue;}33Exist函數template<classTypeOfVer,classTypeOfEdge>booladjMatrixGraph<TypeOfVer,TypeOfEdge>::exist(intu,intv)const{if(u<0||u>Vers-1||v<0||v>Vers-1)returnfalse;if(edge[u][v]==noEdge)returnfalse;elsereturntrue;}34圖的存儲鄰接矩陣和加權鄰接矩陣鄰接表35鄰接表設有向圖或無向圖具有n個結點，則用結點表、邊表表示該有向圖或無向圖。結點表：用數組或單鏈表的形式存放所有的結點值。如果結點數n已知，則采用數組形式，否則應采用單鏈表的形式。邊表（邊結點表）：每條邊用一個結點進行表示。同一個結點的所有的邊形成它的邊結點單鏈表。36ABCD無向圖G2ABCDE有向圖G10123destlinkABCD1203dataadj∧∧∧∧12dataadj03041423AB01234CDE41destlink∧∧∧∧∧37鄰接表的特點鄰接表是圖的標準存儲方式優(yōu)點：內存＝結點數＋邊數，處理時間也是結點數＋邊數，即為O(|V|+|E|)。當我們談及圖的線性算法時，一般指的是O(|V|+|E|)

缺點：確定i-->j是否有邊，最壞需耗費O(n)時間。無向圖同一條邊表示兩次。邊表空間浪費一倍。有向圖中尋找進入某結點的邊，非常困難。38鄰接表類的定義template<classTypeOfVer,classTypeOfEdge>classadjListGraph:publicgraph<TypeOfEdge>{public:adjListGraph(intvSize,constTypeOfVerd[]); boolinsert(intu,intv,TypeOfEdgew); boolremove(intu,intv); boolexist(intu,intv)const; ~adjListGraph(); 39private:structedgeNode{//鄰接表中存儲邊的結點類

intend;//終點編號

TypeOfEdgeweight;//邊的權值

edgeNode*next; edgeNode(inte,TypeOfEdgew,edgeNode*n=NULL) {end=e;weight=w;next=n;} }; structverNode{//保存頂點的數據元素類型

TypeOfVerver;//頂點值

edgeNode*head;//對應的單鏈表的頭指針

verNode(edgeNode*h=NULL){head=h;} }; verNode*verList;};40構造函數template<classTypeOfVer,classTypeOfEdge>adjListGraph<TypeOfVer,TypeOfEdge>::adjListGraph(intvSize,constTypeOfVerd[]){Vers=vSize;Edges=0;

verList=newverNode[vSize];for(inti=0;i<Vers;++i)verList[i].ver=d[i];}41析構函數template<classTypeOfVer,classTypeOfEdge>adjListGraph<TypeOfVer,TypeOfEdge>::~adjListGraph(){inti;edgeNode*p;for(i=0;i<Vers;++i)

while((p=verList[i].head)!=NULL)｛

verList[i].head=p->next; deletep; }delete[]verList;}42Insert函數template<classTypeOfVer,classTypeOfEdge>booladjListGraph<TypeOfVer,TypeOfEdge>::insert(intu,intv,TypeOfEdgew){verList[u].head=newedgeNode(v,w,verList[u].head);++Edges;returntrue;}43Remove函數template<classTypeOfVer,classTypeOfEdge>booladjListGraph<TypeOfVer,TypeOfEdge>::remove(intu,intv){edgeNode*p=verList[u].head,*q;if(p==NULL)returnfalse;//結點u沒有相連的邊

if(p->end==v)//單鏈表中的第一個結點就是被刪除的邊

{verList[u].head=p->next;deletep;--Edges;returntrue;}while(p->next!=NULL&&p->next->end!=v)p=p->nextif(p->next==NULL)returnfalse;//沒有找到被刪除的邊

q=p->next;p->next=q->next;deleteq;--Edges;returntrue;}44Exist函數template<classTypeOfVer,classTypeOfEdge>booladjListGraph<TypeOfVer,TypeOfEdge>::exist(intu,intv)const{edgeNode*p=verList[u].head;while(p!=NULL&&p->end!=v)p=p->next;if(p==NULL)returnfalse;elsereturntrue;}45第12章圖的基本概念圖的定義圖的術語圖的運算圖的存儲圖的遍歷圖遍歷的應用46圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索對有向圖和無向圖進行遍歷是按照某種次序系統(tǒng)地訪問圖中的所有頂點，并且使得每個頂點只能被訪問一次。在圖中某個頂點可能和圖中的多個頂點鄰接并且存在回路，因此在圖中訪問一個頂點u之后，在以后的訪問過程中，又可能再次返回到頂點u，所以圖的遍歷要比樹的遍歷更復雜47深度優(yōu)先搜索1、選中第一個被訪問的頂點；2、對頂點作已訪問過的標志；3、依次從頂點的未被訪問過的第一個、第二個、第三個……

鄰接頂點出發(fā)，進行深度優(yōu)先搜索；4、如果還有頂點未被訪問，則選中一個起始頂點，轉向2；5、所有的頂點都被訪問到，則結束。485672413從結點5開始進行深度優(yōu)先的搜索，則遍歷序列可以為：5，7，6，2，4，3，1，也可以為：5，6，2，3，1，4，7。深度優(yōu)先生成樹5672314567231449深度優(yōu)先生成森林

在進行深度優(yōu)先搜索DFS時，有時并不一定能夠保證從某一個結點出發(fā)能訪問到所有的頂點在這種情況下，必須再選中一個未訪問過的頂點，繼續(xù)進行深度優(yōu)先搜索。直至所有的頂點都被訪問到為止。這時，得到的是一組樹而不是一棵樹，這一組樹被稱為深度優(yōu)先生成森林。505672413從結點1開始深度優(yōu)先搜索124356751深度優(yōu)先搜索的實現深度優(yōu)先搜索DFS的實現方法和樹的前序遍歷算法類似，但必須對訪問過的頂點加以標記dfs函數不需要參數，也沒有返回值。它從編號最小的結點出發(fā)開始搜索，并將對當前對象的深度優(yōu)先搜索的序列顯示在顯示器上。52深度優(yōu)先搜索的實現以鄰接表為例設置一個數組visited，記錄節(jié)點是否被訪問過設計一個私有的深度優(yōu)先搜索的函數，從某一節(jié)點出發(fā)訪問所有可達節(jié)點如果是無向非連通圖的或有向非強連通，則對圖中尚未訪問的節(jié)點反復調用深度優(yōu)先搜索，形成深度優(yōu)先搜索的森林。53公有的dfs函數voiddfs(){

對每個節(jié)點vvisited[v]=false;

while(v=尚未訪問的節(jié)點）

dfs(v，visited);}54template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::dfs()const{bool*visited=newbool[Vers];

for(inti=0;i<Vers;++i)visited[i]=false;

cout<<"當前圖的深度優(yōu)先遍歷序列為："<<endl;

for(i=0;i<Vers;++i){

if(visited[i]==true)continue; dfs(i,visited); cout<<endl;}}55私有的dfsvoiddfs(v，visited){visited[v]=true;for每個v的鄰接點wif(!Visited[w])dfs(w,visited);}訪問從結點v出發(fā)可以訪問到的所有結點56template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::dfs(intstart,boolvisited[])const{edgeNode*p=verList[start].head;

cout<<verList[start].ver<<'\t';visited[start]=true;while(p!=NULL){ if(visited[p->end]==false)dfs(p->end,visited); p=p->next;}}575672413對圖調用dfs結果為：當前圖的深度優(yōu)先搜索序列為：124367即對應于左圖的深度優(yōu)先生成森林124356758時間性能分析dfs函數將對所有的頂點和邊進行訪問，因此它的時間代價和頂點數|V|及邊數|E|是相關的，即是O(|V|+|E|)。如果圖是用鄰接矩陣來表示，則所需要的時間是O（|V|2）。59圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索對有向圖和無向圖進行遍歷是按照某種次序系統(tǒng)地訪問圖中的所有頂點，并且使得每個頂點只能被訪問一次。在圖中某個頂點可能和圖中的多個頂點鄰接并且存在回路，因此在圖中訪問一個頂點u之后，在以后的訪問過程中，又可能再次返回到頂點u，所以圖的遍歷要比樹的遍歷更復雜60廣度優(yōu)先搜索BFS1、選中第一個被訪問的頂點；2、對頂點作已訪問過的標志；3、依次訪問已訪問頂點的未被訪問過的第一個、第二個、第三個……第m個鄰接頂點W1、W2、W3……Wm，進行訪問且進行標記，轉向3；4、如果還有頂點未被訪問，則選中一個起始頂點，轉向2；5、所有的頂點都被訪問到，則結束。廣度優(yōu)先搜索類似于樹的從樹根出發(fā)的按照層次的遍歷。它的訪問方式如下：615672413按照頂點序號小的先訪問，序號大的后訪問的原則，則它的廣度優(yōu)先訪問序列為：1，2，4，3，5，6，7。對應的廣度優(yōu)先生成森林為124356762從不同的結點開始可以得到不同的搜索序列。例如，從5開始廣度優(yōu)先搜索這個圖，得到的遍歷序列為：5，6，7，2，4，3，1。5672413124356763廣度優(yōu)先搜索的實現需要記錄每個結點是否已被訪問需要記住每個已被訪問的結點的后繼結點，然后依次訪問這些后繼結點。這可以用一個隊列來實現過程：將序號最小的頂點放入隊列重復取隊列的隊頭元素進行處理，直到隊列為空。對出隊的每個元素，首先檢查該元素是否已被訪問。如果沒有被訪問過，則訪問該元素，并將它的所有的沒有被訪問過的后繼入隊檢查是否還有結點未被訪問。如果有，重復上述兩個步驟64template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::bfs()const{bool*visited=newbool[Vers];

intcurrentNode;linkQueue<int>q;

edgeNode*p;for(inti=0;i<Vers;++i)visited[i]=false;cout<<"當前圖的廣度優(yōu)先遍歷序列為："<<endl;65for(i=0;i<Vers;++i){

if(visited[i]==true)continue; q.enQueue(i);while(!q.isEmpty()){ currentNode=q.deQueue(); if(visited[currentNode]==true)continue;

cout<<verList[currentNode].ver<<'\t';

visited[currentNode]=true; p=verList[currentNode].head; while(p!=NULL){ if(visited[p->end]==false)q.enQueue(p->end); p=p->next; }} cout<<endl;}}665672413對圖調用bfs結果為：當前圖的廣度優(yōu)先搜索序列為：124367即對應于左圖的深度優(yōu)先生成森林124356767時間性能分析在廣度優(yōu)先搜索中，每個頂點都入隊一次。對于每個出隊的結點，需要查看它的所有鄰接結點。假如圖是用鄰接表存儲，查看所有的鄰接結點需要O（|E|）的時間，每個結點入隊一次需要O（|V|）的時間，因此廣度優(yōu)先遍歷的時間復雜度為O（|E|+|V|）。如果圖是用鄰接矩陣存儲，查看某個結點所有的邊需要O（|V|）的時間，因此廣度優(yōu)先搜索的時間復雜度為O（|V|2）68第12章圖的基本概念圖的定義圖的術語圖的運算圖的存儲圖的遍歷圖遍歷的應用69圖遍歷的應用無向圖的連通性歐拉回路有向圖的連通性拓撲排序70無向圖的連通性深度優(yōu)先搜索和廣度優(yōu)先搜索都可以用來測試無向圖的連通性。如果無向圖是連通的，則從無向圖中的任意結點出發(fā)進行深度優(yōu)先搜索或廣度優(yōu)先搜索都可以訪問到每一個結點。訪問的次序是一棵深度/廣度優(yōu)先生成樹。如果圖是非連通的，深度/廣度優(yōu)先搜索可以找到一片深度/廣度優(yōu)先生成森林。每棵樹就是一個連通分量。對無向圖來說，深度/廣度優(yōu)先搜索可以找到了它的所有連通分量。前面介紹的討論的深度優(yōu)先和廣度優(yōu)先遍歷中，都已實現了這個功能。在這兩個函數的輸出中，每一行代表一個連通分量。71圖遍歷的應用無向圖的連通性歐拉回路有向圖的連通性拓撲排序72歐拉回路哥尼斯堡七橋問題就是：能否找到一條走遍這七座橋，而且每座橋只經過一次，最后又回到原出發(fā)點的路徑。島區(qū)東區(qū)北區(qū)南區(qū)73七橋問題的抽象東區(qū)北區(qū)島區(qū)南區(qū)74歐拉的證明如果有奇數橋的地方不止兩個，滿足要求的路徑是找不到的。如果只有兩個地方有奇數橋，可以從這兩個地方之一出發(fā)，經過所有的橋一次，再回到另一個地方。如果都是偶數橋，從任意地方出發(fā)都能回到原點。75歐拉回路和歐拉路徑如果能夠在一個圖中找到一條路徑，使得該路徑對圖的每一條邊正好經過一次，這條路徑被稱為歐拉路徑。如果再增加一個附加條件，即起點和終點是相同的，這條路徑被稱為歐拉回路。76基本想法執(zhí)行一次深度優(yōu)先的搜索。從起始結點開始，沿著這條路一直往下走，直到無路可走。而且在此過程中不允許回溯。因此歐拉回路問題也被稱為一筆畫問題。但是有很多的搜索方案是行不通的。77012345對于上圖，它的所有結點的度均為偶數，應該存在歐拉回路。但如果從結點5出發(fā)開始深度優(yōu)先的訪問，選擇的路徑為5->4->3->5，則此時，就無法訪問其他結點了,因為5沒有其他的尚未被訪問的邊了。78解決方法找出路徑上的另外一個尚有未訪問的邊的頂點，開始另一次深度優(yōu)先的搜索，將得到的遍歷序列拼接到原來的序列中，直到所有的邊都已被訪問。79012345先找到5->4->3->5在路徑上找一個尚有邊未被訪問的結點，如：4，開始另一次深度優(yōu)先遍歷。得到路徑4->2->1->4將第二條路徑拼接到第一條路徑上，得到：5->4->2->1->4->3->53號結點還有未訪問的邊，從3號結點再開始一次深度優(yōu)先遍歷，得到路徑3->1->0->2->3將第三條路徑拼接到第一條路徑上，得到：5->4->2->1->4->3->1->0->2->3->580尋找歐拉回路檢查存在性找出回路：執(zhí)行一次深度優(yōu)先的搜索。從起始結點開始，沿著這條路一直往下走，直到無路可走。而且在此過程中不允許回溯。路徑上是否有一個尚有未訪問的邊的頂點。如果有，開始另一次深度優(yōu)先的搜索，將得到的遍歷序列拼接到原來的序列中，直到所有的邊都已被訪問。81歐拉回路的實現歐拉回路是由一段一段的路徑拼接起來的。為此，設計了一個私有的成員函數EulerCircuit來獲得一段路徑。公有的EulerCircuit函數調用私有的EulerCircuit函數獲得一段段的路徑，并將它們拼接起來，形成一條完整的歐拉回路。為了拼接方便起見，找到的歐拉回路被保存在一個單鏈表中，單鏈表的結點類型為EulerNode。EulerNode保存兩個內容：結點的編號和下一結點的指針。它被定義為鄰接表類的私有的內嵌類。82歐拉回路的實現續(xù)歐拉回路中，一條邊不能走兩遍。為此，當一條邊被訪問以后，就將這條邊刪除Clone函數創(chuàng)建一份鄰接表的拷貝，以便在找完路徑后能恢復這個圖的鄰接表83公有的EulerCircuit函數template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::EulerCircuit(TypeOfVerstart){EulerNode*beg,*end,*p,*q,*tb,*te;intnumOfDegree;edgeNode*r;verNode*tmp;

//檢查是否存在歐拉回路for(inti=0;i<Vers;++i){

numOfDegree=0;r=verList[i].head; while(r!=0){++numOfDegree;r=r->next;}if(numOfDegree==0||numOfDegree%2){cout<<"不存在歐拉回路"<<endl;return;}}84//尋找起始結點的編號for(i=0;i<Vers;++i)

if(verList[i].ver==start)break;if(i==Vers){cout<<"起始結點不存在"<<endl;return;}//創(chuàng)建一份鄰接表的拷貝tmp=clone(); 85//尋找從i出發(fā)的路徑，//路徑的起點和終點地址分別是beg和endbeg=EulerCircuit(i,end);while(true){p=beg;while(p->next!=NULL) if(verList[p->next->NodeNum].head!=NULL)break;elsep=p->next; if(p->next==NULL)break; q=p->next;tb=EulerCircuit(q->NodeNum,te); te->next=q->next; p->next=tb; deleteq; }86//恢復原圖

delete[]verList;verList=tmp;

//顯示得到的歐拉回路

cout<<"歐拉回路是："<<endl;while(beg!=NULL){ cout<<verList[beg->NodeNum].ver<<'\t'; p=beg;beg=beg->next;

deletep;} cout<<endl;} 87歐拉路徑中的結點類structEulerNode{ intNodeNum; EulerNode*next; EulerNode(intver){NodeNum=ver;next=NULL;}};88clone函數的實現template<classTypeOfVer,classTypeOfEdge>adjListGraph<TypeOfVer,TypeOfEdge>::verNode*adjListGraph<TypeOfVer,TypeOfEdge>::clone()const{verNode*tmp=newverNode[Vers];edgeNode*p;

for(inti=0;i<Vers;++i){

tmp[i].ver=verList[i].ver;

p=verList[i].head; while(p!=NULL){ tmp[i].head=newedgeNode(p->end,p->weight,tmp[i].head); p=p->next; }}returntmp;}89私有的EulerCircuit函數template<classTypeOfVer,classTypeOfEdge>adjListGraph<TypeOfVer,TypeOfEdge>::EulerNode*adjListGraph<TypeOfVer,TypeOfEdge>::EulerCircuit(intstart,EulerNode*&end){EulerNode*beg;intnextNode;beg=end=newEulerNode(start);while(verList[start].head!=NULL){nextNode=verList[start].head->end;remove(start,nextNode);remove(nextNode,start);start=nextNode;end->next=newEulerNode(start);end=end->next;}returnbeg;}90哈密爾頓回路問題

該回路通過圖的每一個結點一次，且僅通過一次。一個圖是否存在哈密爾頓回路至今仍未找到滿足該問題的充要條件。91圖遍歷的應用無向圖的連通性歐拉回路有向圖的連通性拓撲排序92對有向圖，深度優(yōu)先搜索可以測試是否強連通，并找出所有強連通分量找強連通分量的方法從任意節(jié)點開始深度優(yōu)先遍歷G。對森林中的每棵樹進行深度優(yōu)先遍歷，并按遍歷的順序給每個節(jié)點編號將G的每條邊逆向，形成Gr。從編號最大的節(jié)點開始深度優(yōu)先遍歷Gr。得到的深度優(yōu)先遍歷森林的每棵樹就是G的強連通分量。有向圖的連通性93ABDGHCJEIF從B開始深度優(yōu)先搜索BEDAFCIHG10J97865432194ABDGHCJEIFGrGIHJBACFDE因此，圖G有5個強連通分量95圖遍歷的應用無向圖的連通性歐拉回路有向圖的連通性拓撲排序96拓撲排序設G=（V，E）是一個具有n個頂點的有向無環(huán)圖。V中的頂點序列V1，V2，…，Vn稱為一個拓撲序列，當且僅當該序列滿足下列條件：若在G中，從Vi到Vj有一條路徑，則序列中Vi必須排在Vj的前面。97下