數據結構課件：第八章 圖

146-1圖的基本概念圖的存儲表示圖的遍歷與連通性最小生成樹最短路徑活動網絡第八章圖146-2圖的基本概念圖定義圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數據結構：

Graph＝(V,E)

其中

V={x|x

某個數據對象}

是頂點的有窮非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V&&Path(x,y)}

是頂點之間關系的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y的一條單向通路,它是有方向的。146-3

有向圖與無向圖在有向圖中，頂點對<x,y>是有序的。在無向圖中，頂點對(x,y)是無序的。完全圖若有

n個頂點的無向圖有n(n-1)/2

條邊,則此圖為完全無向圖。有

n個頂點的有向圖有n(n-1)條邊,則此圖為完全有向圖。00001111222265433146-4

鄰接頂點如果

(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。子圖設有兩個圖G＝(V,E)和G'＝(V',E')。若V'V且E'E,則稱圖G'是圖G的子圖。權某些圖的邊具有與它相關的數,稱之為權。這種帶權圖叫做網絡。子圖01230130123023146-5頂點的度一個頂點v的度是與它相關聯的邊的條數。記作TD(v)。在有向圖中,頂點的度等于該頂點的入度與出度之和。頂點v的入度是以v為終點的有向邊的條數,記作

ID(v);頂點v的出度是以v為始點的有向邊的條數,記作

OD(v)。路徑在圖G＝(V,E)中,若從頂點

vi

出發(fā),沿一些邊經過一些頂點

vp1,

vp2,…,

vpm，到達頂點vj。則稱頂點序列

(vi

vp1vp2...vpm

vj)

為從頂點vi到頂點

vj的路徑。它經過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應是屬于E的邊。146-6路徑長度非帶權圖的路徑長度是指此路徑上邊的條數。帶權圖的路徑長度是指路徑上各邊的權之和。簡單路徑若路徑上各頂點v1,v2,...,vm

均不互相重復,則稱這樣的路徑為簡單路徑?；芈啡袈窂缴系谝粋€頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)。012301230123146-7連通圖與連通分量在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。生成樹一個連通圖的生成樹是其極小連通子圖，在n個頂點的情形下，有

n-1

條邊。146-8圖的抽象數據類型classGraph{//對象:由一個頂點的非空集合和一個邊集合構成//每條邊由一個頂點對來表示。public:

Graph(); //建立一個空的圖

voidinsertVertex(constT&vertex);

//插入一個頂點vertex,該頂點暫時沒有入邊

voidinsertEdge(intv1,intv2,intweight);

//在圖中插入一條邊(v1,v2,w)voidremoveVertex(intv);

//在圖中刪除頂點v和所有關聯到它的邊

146-9voidremoveEdge(intv1,intv2);

//在圖中刪去邊(v1,v2)boolIsEmpty();

//若圖中沒有頂點,則返回true,否則返回false

T

getWeight(intv1,intv2);

//函數返回邊

(v1,v2)的權值

intgetFirstNeighbor(intv);

//給出頂點v第一個鄰接頂點的位置

intgetNextNeighbor(intv,intw);

//給出頂點v的某鄰接頂點w的下一個鄰接頂點};146-10圖的存儲表示圖的模板基類在模板類定義中的數據類型參數表<classT,classE>

中，T是頂點數據的類型，E是邊上所附數據的類型。這個模板基類是按照最復雜的情況（即帶權無向圖）來定義的，如果需要使用非帶權圖，可將數據類型參數表<classT,classE>

改為<classT>。如果使用的是有向圖，也可以對程序做相應的改動。

146-11圖的模板基類

constintmaxWeight=……; //無窮大的值(=)constintDefaultVertices=30; //最大頂點數(=n)template<classT,classE>classGraph{ //圖的類定義protected:intmaxVertices; //圖中最大頂點數

intnumEdges; //當前邊數

intnumVertices; //當前頂點數

intgetVertexPos(Tvertex);

//給出頂點vertex在圖中位置public:146-12Graph(intsz=DefaultVertices); //構造函數

～Graph(); //析構函數

boolGraphEmpty()const //判圖空否

{returnnumEdges==0;} intNumberOfVertices(){returnnumVertices;}

//返回當前頂點數

intNumberOfEdges(){returnnumEdges;}

//返回當前邊數

virtualT

getValue(inti); //取頂點

i的值

virtualE

getWeight(intv1,intv2);//取邊上權值

virtualintgetFirstNeighbor(intv);

//取頂點v的第一個鄰接頂點146-13 virtualintgetNextNeighbor(intv,intw);

//取鄰接頂點w的下一鄰接頂點

virtualboolinsertVertex(constTvertex);

//插入一個頂點vertex virtualboolinsertEdge(intv1,intv2,Ecost);

//插入邊(v1,v2),權為cost virtualboolremoveVertex(intv);

//刪去頂點

v和所有與相關聯邊

virtualboolremoveEdge(intv1,intv2);

//在圖中刪去邊(v1,v2)};146-14鄰接矩陣(AdjacencyMatrix)在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關系的鄰接矩陣。設圖A=(V,E)是一個有n

個頂點的圖,圖的鄰接矩陣是一個二維數組A.edge[n][n]，定義：146-15無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123012146-16在有向圖中,統計第i

行1的個數可得頂點i

的出度，統計第j列1的個數可得頂點j

的入度。在無向圖中,統計第i

行(列)1的個數可得頂點i

的度。網絡的鄰接矩陣146-17863129542031用鄰接矩陣表示的圖的類定義template<classT,classE>classGraphmtx:publicGraph<T,E>{friendistream&operator>>(istream&in,Graphmtx<T,E>&G); //輸入146-18friendostream&operator<<(ostream&out,Graphmtx<T,E>&G); //輸出private:

T*VerticesList; //頂點表

E**Edge; //鄰接矩陣

intgetVertexPos(Tvertex){

//給出頂點vertex在圖中的位置

for(inti=0;i<numVertices;i++) if(VerticesList[i]==Vertex)returni; return-1; };public:146-19Graphmtx(intsz=DefaultVertices);//構造函數

～Graphmtx()

//析構函數

{delete[]VerticesList;delete[]Edge;}

T

getValue(inti){

//取頂點i的值,i不合理返回0 returni>=0&&i<=numVertices?

VerticesList[i]:NULL;}

E

getWeight(intv1,intv2){//取邊(v1,v2)上權值

returnv1!=-1&&v2!=-1?Edge[v1][v2]:0;}intgetFirstNeighbor(intv);

//取頂點v的第一個鄰接頂點146-20intgetNextNeighbor(intv,intw);

//取v的鄰接頂點w的下一鄰接頂點

boolinsertVertex(constTvertex);

//插入頂點vertex boolinsertEdge(intv1,intv2,Ecost);

//插入邊(v1,v2),權值為cost boolremoveVertex(intv);

//刪去頂點v和所有與它相關聯的邊

boolremoveEdge(intv1,intv2);

//在圖中刪去邊(v1,v2)};146-21template<classT,classE>Graphmtx<T,E>::Graphmtx(intsz){//構造函數

maxVertices=sz;

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

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

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

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

for(i=0;i<maxVertices;i++)

//矩陣初始化

for(j=0;j<maxVertices;j++)

Edge[i][j]=(i==j)

？

0:maxWeight;};146-22template<classT,classE>intGraphmtx<T,E>::getFirstNeighbor(intv){//給出頂點位置為v的第一個鄰接頂點的位置,

//如果找不到,則函數返回-1if(v!=-1){ for(intcol=0;col<numVertices;col++)if(Edge[v][col]&&Edge[v][col]<maxWeight)

returncol; } return-1;};146-23template<classT,classE>intGraphmtx<T,E>::getNextNeighbor(intv,intw){//給出頂點v的某鄰接頂點w的下一個鄰接頂點

if(v!=-1&&w!=-1){ for(intcol=w+1;col<numVertices;col++)

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

returncol; } return-1;};146-24鄰接表是鄰接矩陣的改進形式。為此需要把鄰接矩陣的各行分別組織為一個單鏈表。在鄰接表中，同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊（邊結點），結點中有另一頂點的下標

dest和指針

link。對于帶權圖，邊結點中還要保存該邊的權值cost。頂點表的第i個頂點中保存該頂點的數據，以及它對應邊鏈表的頭指針adj。

鄰接表(AdjacencyList)146-25ABCDdataadjABCD0123destlinkdestlink130210無向圖的鄰接表統計某頂點對應邊鏈表中結點個數，可得該頂點的度。某條邊(vi,vj)在鄰接表中有兩個邊結點，分別在第i個頂點和第j個頂點對應的邊鏈表中。146-26dataadjABC012destlinkdestlink鄰接表(出邊表)dataadjABC012destlink逆鄰接表(入邊表)102011有向圖的鄰接表和逆鄰接表ABC146-27BACD69528dataadjABCD0123destcostlink1

53

62

83

21

9(出邊表)(頂點表)網絡(帶權圖)的鄰接表統計出邊表中結點個數，得到該頂點的出度；統計入邊表中結點個數，得到該頂點的入度。146-28在鄰接表的邊鏈表中，各個邊結點的鏈入順序任意，視邊結點輸入次序而定。設圖中有n個頂點，e條邊，則用鄰接表表示無向圖時，需要n個頂點結點，2e個邊結點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點結點，e個邊結點。當e

遠遠小于n2時，可以節(jié)省大量的存儲空間。此外，把同一個頂點的所有邊鏈接在一個單鏈表中，也使得圖的操作更為便捷。

146-29用鄰接表表示的圖的類定義

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

int

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

E

cost; //邊上的權值

Edge<T,E>*link; //下一條邊鏈指針

Edge(){} //構造函數

Edge(intnum,Eweight)

//構造函數

:dest(num),cost(weight),link(NULL){} booloperator!=(Edge<T,E>&R)const {returndest!=R.dest;} //判邊等否};146-30template<classT,classE>structVertex{ //頂點的定義

Tdata; //頂點的名字

Edge<T,E>*adj; //邊鏈表的頭指針};template<classT,classE>classGraphlnk:publicGraph<T,E>{//圖的類定義friendistream&operator>>(istream&in, Graphlnk<T,E>&G); //輸入friendostream&operator<<(ostream&out, Graphlnk<T,E>&G); //輸出146-31private:

Vertex<T,E>*NodeTable;

//頂點表(各邊鏈表的頭結點) intgetVertexPos(constTvertx){

//給出頂點vertex在圖中的位置

for(inti=0;i<numVertices;i++) if(NodeTable[i].data==vertx)returni; return-1; }public:

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

~Graphlnk(); //析構函數146-32

T

getValue(inti){ //取頂點

i的值

return(i>=0&&i<NumVertices)?

NodeTable[i].data:0;}

E

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

boolinsertVertex(constT&vertex);boolremoveVertex(intv);boolinsertEdge(intv1,intv2,Ecost); boolremoveEdge(intv1,intv2);intgetFirstNeighbor(intv);intgetNextNeighbor(intv,intw); };146-33template<classT,classE>Graphlnk<T,E>::Graphlnk(intsz){//構造函數：建立一個空的鄰接表

maxVertices=sz;

numVertices=0;numEdges=0;

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

if(NodeTable==NULL)

{cerr<<"存儲分配錯！"<<endl;exit(1);}for(inti=0;i<maxVertices;i++)

NodeTable[i].adj=NULL;};146-34template<classT,classE>Graphlnk<T,E>::～Graphlnk(){ //析構函數：刪除一個鄰接表

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

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

NodeTable[i].adj=p->link;deletep;p=NodeTable[i].adj;} } delete[]NodeTable; //刪除頂點表數組};146-35template<classT,classE>intGraphlnk<T,E>::getFirstNeighbor(intv){//給出頂點位置為

v的第一個鄰接頂點的位置,//如果找不到,則函數返回-1if(v!=-1){ //頂點v存在

Edge<T,E>*p=NodeTable[v].adj; //對應邊鏈表第一個邊結點

if(p!=NULL)returnp->dest; //存在,返回第一個鄰接頂點

} return-1; //第一個鄰接頂點不存在};146-36template<classT,classE>intGraphlnk<T,E>::getNextNeighbor(intv,intw){//給出頂點v的鄰接頂點w的下一個鄰接頂點的位置,//若沒有下一個鄰接頂點,則函數返回-1if(v!=-1){ //頂點v存在

Edge<T,E>*p=

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

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

returnp->link->dest; //返回下一個鄰接頂點

} return-1; //下一鄰接頂點不存在};146-37鄰接多重表(AdjacencyMultilist)在鄰接多重表中,每一條邊只有一個邊結點。為有關邊的處理提供了方便。無向圖的情形邊結點的結構其中,mark是記錄是否處理過的標記;vertex1和vertex2是該邊兩頂點位置。path1域是鏈接指針,指向下一條依附頂點vertex1的邊；path2是指向下一條依附頂點vertex2的邊鏈接指針。

markvertex1vertex2path1path2146-38需要時還可設置一個存放與該邊相關的權值的域cost。頂點結點的結構頂點信息的結點表以順序表方式組織,每一個頂點結點有兩個數據成員：其中，data存放與該頂點相關的信息，Firstout

是指示第一條依附該頂點的邊的指針。在鄰接多重表中,所有依附同一個頂點的邊都鏈接在同一個單鏈表中。

dataFirstout146-39markvtx1vtx2path1path2010213e1e2e3dataFoutABCD0123e1e2e3ABCD從頂點i

出發(fā),可以循鏈找到所有依附于該頂點的邊，也可以找到它的所有鄰接頂點。鄰接多重表的結構146-40有向圖的情形在用鄰接表表示有向圖時,有時需要同時使用鄰接表和逆鄰接表。用有向圖的鄰接多重表(十字鏈表)可把兩個表結合起來表示。邊結點的結構其中，mark是處理標記；vertex1和vertex2指明該有向邊始頂點和終頂點的位置。path1是指向始頂點與該邊相同的下一條邊的指針；path2是指向終頂點與該邊相同的下一條邊的指針。需要時還可有權值域cost。

markvertex1vertex2path1path2146-41頂點結點的結構每個頂點有一個結點，它相當于出邊表和入邊表的表頭結點：其中，數據成員data存放與該頂點相關的信息，指針Firstout指示以該頂點為始頂點的出邊表的第一條邊，Firstin指示以該頂點為終頂點的入邊表的第一條邊。

dataFirstinFirstout146-42markvtx1vtx2path1path2010312233440e1e2e3e4e5e6dataFinFoutABCDE01234e1e2e3e4e5e6ABCDE鄰接多重表的結構146-43圖的遍歷與連通性從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷(GraphTraversal)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數組visited[]。146-44輔助數組visited[]的初始狀態(tài)為0,在圖的遍歷過程中,一旦某一個頂點i

被訪問,就立即讓visited[i]為1,防止它被多次訪問。圖的遍歷的分類:深度優(yōu)先搜索

DFS(DepthFirstSearch)廣度優(yōu)先搜索

BFS(BreadthFirstSearch)146-45深度優(yōu)先搜索DFS

(DepthFirstSearch)深度優(yōu)先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前進回退深度優(yōu)先搜索過程深度優(yōu)先生成樹146-46DFS

在訪問圖中某一起始頂點v

后,由

v

出發(fā),訪問它的任一鄰接頂點

w1;再從w1出發(fā),訪問與w1鄰

接但還沒有訪問過的頂點w2;然后再從w2出發(fā),進行類似的訪問,…如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發(fā),進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復上述過程,直到連通圖中所有頂點都被訪問過為止。146-47圖的深度優(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};146-48template<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);//下一個鄰接頂點

}};146-49廣度優(yōu)先搜索BFS

(BreadthFirstSearch)廣度優(yōu)先搜索的示例廣度優(yōu)先搜索過程廣度優(yōu)先生成樹ACDEGBFIHACDEGBFH123456789123456789I146-50BFS在訪問了起始頂點v之后,由v出發(fā),依次訪問v的各個未被訪問過的鄰接頂點w1,w2,…,wt,然后再順序訪問w1,w2,…,wt的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點，…如此做下去，直到圖中所有頂點都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點,不像深度優(yōu)先搜索那樣有往回退的情況。因此,廣度優(yōu)先搜索不是一個遞歸的過程。146-51為了實現逐層訪問,算法中使用了一個隊列,以記憶正在訪問的這一層和上一層的頂點,以便于向下一層訪問。為避免重復訪問,需要一個輔助數組visited[]，給被訪問過的頂點加標記。template<classT,classE>voidBFS(Graph<T,E>&G,constT&v){inti,w,n=G.NumberOfVertices();

//圖中頂點個數圖的廣度優(yōu)先搜索算法146-52

bool*visited=newbool[n];

for(i=0;i<n;i++)visited[i]=false;intloc=G.getVertexPos(v); //取頂點號

cout<<G.getValue(loc)<<''; //訪問頂點v

visited[loc]=true; //做已訪問標記

Queue<int>Q;Q.EnQueue(loc); //頂點進隊列,實現分層訪問

while(!Q.IsEmpty()){ //循環(huán),訪問所有結點

Q.DeQueue(loc);

w=G.getFirstNeighbor(loc);//第一個鄰接頂點

while(w!=-1){ //若鄰接頂點w存在

if(!visited[w]){ //若未訪問過146-53cout<<G.getValue(w)<<''; //訪問

visited[w]=true;

Q.EnQueue(w); //頂點w進隊列

}

w=G.getNextNeighbor(loc,w); //找頂點loc的下一個鄰接頂點

}} //外層循環(huán)，判隊列空否

delete[]visited;};146-54連通分量(Connectedcomponent)當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在最大連通子圖（連通分量）的所有頂點。若從無向圖每一連通分量中的一個頂點出發(fā)進行遍歷,可求得無向圖的所有連通分量。例如，對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。146-55ACDEBFGOIHJNMLK非連通無向圖AHKCDEIBFOGJNML非連通圖的連通分量146-56確定連通分量的算法template<classT,classE>voidComponents(Graph<T,E>&G){//通過DFS，找出無向圖的所有連通分量

inti,n=G.NumberOfVertices(); //圖中頂點個數

bool*visited=newbool[n]; //訪問標記數組

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

//掃描所有頂點

if(!visited[i]){ //若沒有訪問過

DFS(G,i,visited); //訪問

OutputNewComponent(); //輸出連通分量

} 146-57delete[]visited;}例：以深度優(yōu)先搜索方法從頂點出發(fā)遍歷圖,建立深度優(yōu)先生成森林。A有向圖深度優(yōu)先生成森林ABCDEFGABDECFG146-58template<classT,classE>voidDFS_Forest

(Graph<T,E>&G,Tree<T,E>&F){TreeNode<T,E>*rt,*subT;intn=G.NumberOfVertices();staticint*visited=newint[n];//訪問數組

for(inti=0;i<n;i++)visited[i]=0;for(i=0;i<n;i++)//遍歷所有頂點

if(!visited[i]){//頂點

i未訪問過

if(F.IsEmpty())

//F原為空生成森林,建根

subT=rt=F.BuildRoot(G.GetValue(i));

//頂點

i

的值成為根

rt

的值

146-59elsesubT=F.InsertRightSibling(subT,G.GetValue(i));

//頂點

i

的值成為subT

右兄弟的值

DFS_Tree(G,F,subT,i,visited);

//從頂點

i出發(fā)深度優(yōu)先遍歷,建子樹

}}template<classT,classE>voidDFS_Tree(Graph<T,E>&G,Tree<T,E>&F,

TreeNode<T,E>*rt,intv,intvisited[]){TreeNode<T,E>*p;146-60visited[v]=1;//頂點v作訪問過標志

intw=G.GetFirstNeighbor(v);

//取頂點v的第一個鄰接頂點wintFirstChild=1;

//第一個未訪問子女應是v的左子女

while(w!=-1){//鄰接頂點w存在

if(!visited[w]){

//w未訪問過,將成為v的子女

if(FirstChild){

p=F.InsertLeftChild(rt,G.GetValue(w));

//p插入為rt的左子女146-61FirstChild=0;//建右兄弟

}elsep=F.InsertRightSibling

(p,G.GetValue(w));

//p插入為

p的左子女

DFS_Tree(G,F,p,w,visited);

//遞歸建立

w的以

p為根的子樹

}//鄰接頂點

w處理完

w=G.GetNextNeighbor(v,w);

//取v的下一個鄰接頂點

w}//回到

while判鄰接頂點

w存在};146-62重連通分量

(BiconnectedComponent)在無向連通圖G中,當且僅當刪去G中的頂點v及所有依附于v的所有邊后,可將圖分割成兩個或兩個以上的連通分量，則稱頂點v為關節(jié)點。沒有關節(jié)點的連通圖叫做重連通圖。在重連通圖上,任何一對頂點之間至少存在有兩條路徑,在刪去某個頂點及與該頂點相關聯的邊時,也不破壞圖的連通性。146-63一個連通圖G如果不是重連通圖，那么它可以包括幾個重連通分量。在一個無向連通圖G中,重連通分量可以利用深度優(yōu)先生成樹找到。在圖中各頂點旁標明的深度優(yōu)先數,給出進行深度優(yōu)先搜索時各頂點訪問的次序。深度優(yōu)先生成樹的根是關節(jié)點的充要條件是它至少有兩個子女。其它頂點u是關節(jié)點的充要條件是它至少有一個子女w,從w出發(fā),不能通過w、w的子孫及一條回邊所組成的路徑到達u的祖先。146-64ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有兩個子女關節(jié)點關節(jié)點關節(jié)點146-65最小生成樹

(minimumcostspanningtree)使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n

個頂點的連通網絡的生成樹有n個頂點、n-1條邊。構造最小生成樹假設有一個網絡，用以表示n

個城市之間架設通信線路，邊上的權值代表架設通信線路的成本。如何架設才能使線路架設的成本達到最?。?46-66構造最小生成樹的準則必須使用且僅使用該網絡中的n-1條邊來聯結網絡中的n

個頂點；不能使用產生回路的邊；各邊上的權值的總和達到最小。北京天津南京上海廣州西安成都昆明武漢34764158312419253822221931394450146-67北京天津南京上海廣州西安成都昆明武漢76241922221931北京天津南京上海廣州西安成都昆明武漢34764158312419253822221931394450146-68克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的基本思想： 設有一個有n個頂點的連通網絡N={V,E},最初先構造一個只有n個頂點,沒有邊的非連通圖T={V,},圖中每個頂點自成一個連通分量。當在E中選到一條具有最小權值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權值最小的邊。如此重復下去,直到所有頂點在同一個連通分量上為止。146-69Kruskal算法的偽代碼描述

T=; //T是最小生成樹的邊集合

//E是帶權無向圖的邊集合

while(T包含的邊少于n-1&&E不空){

從E中選一條具有最小代價的邊(v,w);

從E中刪去(v,w);

如果(v,w)加到T中后不會產生回路,則將

(v,w)加入T;否則放棄(v,w); } if(T中包含的邊少于n-1條)cout<<"不是最小生成樹"<<endl;146-70算法的框架利用最小堆(MinHeap)和并查集(DisjointSets)來實現克魯斯卡爾算法。首先,利用最小堆來存放E中的所有的邊,堆中每個結點的格式為在構造最小生成樹過程中,利用并查集的運算檢查依附一條邊的兩頂點tail、head

是否在同一連通分量(即并查集的同一個子集合)上,是則舍去這條邊；否則將此邊加入T,同時將這兩個頂點放在同一個連通分量上。邊的兩個頂點位置邊的權值

tailheadcost

146-71隨著各邊逐步加入到最小生成樹的邊集合中,各連通分量也在逐步合并,直到形成一個連通分量為止。10504613228102514242216181250461325046132原圖(a)(b)構造最小生成樹的過程146-721012504613228102514242216181250461325046132101412原圖(c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123146-73最小生成樹類定義constfloatmaxValue=FLOAT_MAX

//機器可表示的、問題中不可能出現的大數template<classT,classE>structMSTEdgeNode{ //樹邊結點的類定義

inttail,head; //兩頂點位置

Ecost; //邊上的權值

MSTEdgeNode():tail(-1),head(-1),cost(0){} //構造函數

};

template<classT,classE>146-74classMinSpanTree{ //樹的類定義protected:

MSTEdgeNode<T,E>*edgevalue; //邊值數組

intmaxSize,n; //最大元素個數和當前個數public:

MinSpanTree(intsz=DefaultSize-1):

MaxSize(sz),n(0){

edgevalue=newMSTEdgeNode<T,E>[sz]; } intInsert(MSTEdgeNode&item);};146-75在求解最小生成樹時，可以用鄰接矩陣存儲圖，也可以用鄰接表存儲圖。算法中使用圖的抽象基類的操作，無需考慮圖及其操作的具體實現。#include"heap.h"#include"UFSets.h"template<classT,classE>voidKruskal(Graph<T,E>&G,

MinSpanTree<T,E>&MST){Kruskal算法的實現

146-76

MSTEdgeNode<T,E>ed;//邊結點輔助單元

intu,v,count;

intn=G.NumberOfVertices();//頂點數

intm=G.NumberOfEdges();

//邊數

MinHeap<MSTEdgeNode<T,E>>H(m);

//最小堆

UFSetsF(n); //并查集

for(u=0;u<n;u++)

for(v=u+1;v<n;v++)

if(G.getWeight(u,v)!=maxValue){ed.tail=u;ed.head=v;

//插入堆

ed.cost=G.getWeight(u,v);H.Insert(ed);

}146-77

count=1;

//最小生成樹邊數計數

while(count<n){

//反復執(zhí)行,取n-1條邊

H.Remove(ed);

//退出具最小權值的邊

u=F.Find(ed.tail);v=F.Find(ed.head);

//取兩頂點所在集合的根u與v

if(u!=v){//不是同一集合,不連通

F.Union(u,v);

//合并,連通它們

MST.Insert(ed);

//該邊存入MSTcount++;

}

}}；146-78出堆順序

(0,5,10)

選中

(2,3,12)

選中

(1,6,14)

選中

(1,2,16)

選中(3,6,18)舍棄

(3,4,22)

選中(4,6,24)舍棄(4,5,25)

選中并查集原圖-2-2-2-2-1-1-1-1-1-1-1-1-1-1-1-102-1-1-10-2200000123456-21-11-2-1-421-2-51211-711211F5046132281025142422161812(0,5,10)(2,3,12)(1,6,14)(1,2,16)(3,4,22)(4,5,25)146-79普里姆(Prim)算法普里姆算法的基本思想：從連通網絡N={V,E}中的某一頂點u0

出發(fā),選擇與它關聯的具有最小權值的邊(u0,v),將其頂點加入到生成樹頂點集合U中。 以后每一步從一個頂點在集合U中,而另一個頂點不在集合U中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續(xù)下去,直到網絡中的所有頂點都加入到生成樹頂點集合U中為止。146-80普里姆(Prim)的偽代碼描述

選定構造最小生成樹的出發(fā)頂點u0;

Vmst

={u0}，Emst=; while(Vmst包含的頂點少于n&&E不空){

從E中選一條邊(u,v),

uVmst∩vV-Vmst,且具有最小代價(cost);

令Vmst

=Vmst∪{v},Emst=Emst∪{(u,v)};

將新選出的邊從E中剔除：E=E-{(u,v)}; } if(Vmst包含的頂點少于n)cout<<"不是最小生成樹"<<endl;146-81252510504613228102514242216185046132504613210原圖(a)

(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212146-82Prim算法的實現#include"heap.h"template<classT,classE>voidPrim(Graph<T,E>&G,constTu0,

MinSpanTree<T,E>&MST){

MSTEdgeNode<T,E>ed;//邊結點輔助單元

inti,u,v,count; intn=G.NumberOfVertices(); //頂點數

intm=G.NumberOfEdges(); //邊數

intu=G.getVertexPos(u0); //起始頂點號

MinHeap<MSTEdgeNode<T,E>>H(m);//最小堆146-83

boolVmst=newbool[n];//最小生成樹頂點集合

for(i=0;i<n;i++)

Vmst[i]=false;

Vmst[u]=true; //u加入生成樹

count=1;

do{ //迭代

v=G.getFirstNeighbor(u);while(v!=-1){ //檢測u所有鄰接頂點

if(!Vmst[v]){ //v不在mst中

ed.tail=u;ed.head=v;

ed.cost=G.getWeight(u,v);

H.Insert(ed); //(u,v)加入堆

}//堆中存所有u在mst中,v不在mst中的邊

v=G.getNextNeighbor(u,v);146-84}while(!H.IsEmpty()&&count<n){

H.Remove(ed); //選堆中具最小權的邊

if(!Vmst[ed.head]){

MST.Insert(ed);//加入最小生成樹

u=ed.head;Vmst[u]=true;

//u加入生成樹頂點集合

count++;break;}}}while(count<n);};146-85例子50461322810251424221618125046132281025142422161812H={(0,5,10),(0,1,28)}ed=(0,5,10)Vmst={t,f,f,f,f,f,f}Vmst={t,f,f,f,f,t,f}146-865046132281025142422161812H={(5,4,25),(0,1,28)}ed=(5,4,25)Vmst={t,f,f,f,f,t,f}Vmst={t,f,f,f,t,

t,f}5046132281025142422161812H={(4,3,22),(4,6,24),(0,1,28)}ed=(4,3,22)Vmst={t,f,f,f,t,

t,f}Vmst={t,f,f,t,

t,

t,f}146-875046132281025142422161812H={(3,2,12),(3,6,18),(4,6,24),(0,1,28)}ed=(3,2,12)Vmst={t,f,f,t,

t,

t,f}Vmst={t,f,t,

t,

t,