數(shù)據(jù)結(jié)構(gòu)：第八章 圖

圖的基本概念圖的存儲表示圖的遍歷與連通性

最小生成樹最短路徑

活動網(wǎng)絡(luò)

第八章圖圖的基本概念圖定義

圖是由頂點集合(vertex)及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中

V={x|x

某個數(shù)據(jù)對象}

是頂點的有窮非空集合；

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

V}

或

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

V&&Path(x,y)}

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

有向圖與無向圖在有向圖中，頂點對<x,y>是有序的。在無向圖中，頂點對(x,y)是無序的。完全圖若有n個頂點的無向圖有n(n-1)/2條邊,則此圖為完全無向圖。有n個頂點的有向圖有n(n-1)條邊,則此圖為完全有向圖。鄰接頂點如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。權(quán)某些圖的邊具有與它相關(guān)的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。子圖設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。頂點的度一個頂點v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點的度等于該頂點的入度與出度之和。頂點v的入度是以v為終點的有向邊的條數(shù),記作

ID(v);頂點v

的出度是以v為始點的有向邊的條數(shù),記作OD(v)。路徑在圖G＝(V,E)中,若從頂點

vi出發(fā),沿一些邊經(jīng)過一些頂點

vp1,vp2,…,

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

vp1vp2...vpm

vj

)

為從頂點vi到頂點vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑若路徑上各頂點v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡單路徑?；芈啡袈窂缴系谝粋€頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)。連通圖與連通分量在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。生成樹一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。但有向圖則可能得到它的由若干有向樹組成的生成森林。本章不予討論的圖圖的抽象數(shù)據(jù)類型classGraph{ public:

Graph();

void

InsertVertex(

constType&vertex);

void

InsertEdge

(constint

v1,

constint

v2,

int

weight);

void

RemoveVertex(

constint

v);

void

RemoveEdge(

constint

v1,

constint

v2);

int

IsEmpty(); Type

GetWeight(

constint

v1,

constint

v2);

int

GetFirstNeighbor

(

constintv);

int

GetNextNeighbor

(

constint

v1,

constint

v2);

}圖的存儲表示在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關(guān)系的鄰接矩陣。設(shè)圖A=(V,E)是一個有n個頂點的圖，則圖的鄰接矩陣是一個二維數(shù)組A.edge[n][n]，定義：無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的。鄰接矩陣(AdjacencyMatrix)在有向圖中,統(tǒng)計第i

行1的個數(shù)可得頂點

i

的出度，統(tǒng)計第j行1的個數(shù)可得頂點j

的入度。在無向圖中,統(tǒng)計第i

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

的度。網(wǎng)絡(luò)的鄰接矩陣用鄰接矩陣表示的圖的類的定義constintMaxEdges

=50; constintMaxVertices=10;template<classNameType,classDistType>class

Graph{ private:

SeqList<NameType>

VerticesList

(MaxVertices);

DistType

Edge[MaxVertices][MaxVertices];

intCurrentEdges;

int

FindVertex(

SeqList<NameType>&L;

constNameType&vertex)

{returnL.Find(vertex);}

int

GetVertexPos(

ConstNameType&vertex)

{return

FindVertex(VerticesList,vertex);

}public:

Graph(

constint

sz=MaxNumEdges);

int

GraphEmpty()

const{return

VerticesList.IsEmpty

();

}

intGraphFull()

const

{return

VerticesList.IsFull()||

CurrentEdges==MaxEdges;

}

int

NumberOfVertices()

{return

VerticesList.last;

}

int

NumberOfEdges(){return

CurrentEdges;

}

NameTypeGetValue

(

constint

i)

{return

i>=0&&

i<

VerticesList.last

?

VerticesList.data[i]:

NULL;

}

intGetWeight(constint

v1,

constint

v2);

int

GetFirstNeighbor(

constint

v);

int

GetNextNeighbor(

constint

v1,

constint

v2);

voidInsertVertex(

constNameType&

vertex);

void

InsertEdge

(

constint

v1,

constint

v2,

DistType

weight);

void

RemoveVertex

(

constint

v);

void

RemoveEdge(

constint

v1,

constint

v2); }鄰接矩陣實現(xiàn)的部分圖操作template<classNameType,classDistType>Graph<NameType,DistType>::Graph(constintsz){//構(gòu)造函數(shù)

for(inti=0;

i<sz;

i++)

for(

int

j=0;

j<sz;

j++)Edge[i][j]=0;

CurrentEdges

=0; }template<classNameType,classDistType>

DistType

Graph<NameType,DistType>::GetWeight(

constint

v1,

constint

v2){//給出以頂點v1和v2為兩端點的邊上的權(quán)值

if(v1!=-1&&

v2!=-1)

return

Edge[v1][v2];

elsereturn0; }template<classNameType,classDistType>int

Graph<NameType,DistType>::GetFirstNeighbor(

constint

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

if(v!=-1){

for(

int

col

=0;

col

<

CurrentEdges;

col++)

if(Edge[row][col]>0)return

col;

}

return

-1;}

template<classNameType,classDistType>

int

Graph<NameType,DistType>::GetNextNeighbor(

constint

v1,

constint

v2){//給出頂點v1的某鄰接頂點v2的下一個鄰接頂點

if(v1!=-1&&

v2!=-1){

for(

int

col

=v2+1;

col

<

CurrentEdges;

col++)

if(Edge[v1][col]>0)returncol;

}

return

-1;}

鄰接表(AdjacencyList)無向圖的鄰接表

把同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，鏈表的每一個結(jié)點代表一條邊，叫做邊結(jié)點，結(jié)點中保存有與該邊相關(guān)聯(lián)的另一頂點的頂點下標dest

和指向同一鏈表中下一個邊結(jié)點的指針link。有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第i

個邊鏈表鏈接的邊都是頂點i

發(fā)出的邊。也叫做出邊表。在有向圖的逆鄰接表中，第i

個邊鏈表鏈接的邊都是進入頂點

i

的邊。也叫做入邊表。帶權(quán)圖的邊結(jié)點中保存該邊上的權(quán)值cost。頂點i

的邊鏈表的表頭指針

adj

在頂點表的下標為i的頂點記錄中，該記錄還保存了該頂點的其它信息。在鄰接表的邊鏈表中，各個邊結(jié)點的鏈入順序任意，視邊結(jié)點輸入次序而定。設(shè)圖中有n個頂點，e條邊，則用鄰接表表示無向圖時，需要n個頂點結(jié)點，2e個邊結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點結(jié)點，e個邊結(jié)點。鄰接表表示的圖的類定義constint

DefaultSize=10; template<classDistType>class

Graph;

template<classDistType>struct

Edge{

int

dest;

DistType

cost;

Edge<DistType>*link;

Edge(){}

Edge(

int

D,

DistType

C):

dest

(D),cost(C),link(NULL){}

intoperator!=(

const

Edge

&E)

const{return

dest!=E.dest;

}}template<classNameType,classDistType>struct

Vertex

{

NemeType

data; Edge<DistType>*adj;}template<classNameType,classDistType>classGraph{

friendclassvertex<NameType,DistType>;friendclassEdge<DistType>;private:

Vertex<NameType,DistType>*NodeTable;

int

NumVertices;

int

MaxVertices;

intNumEdges;

intGetVertexPos

(

constType&vertex);public:

Graph(

int

sz); ~Graph();

int

GraphEmpty()

const{returnNumVertices==0;

}

intGraphFull

()const

{return

NumVertices==MaxVertices

||

NumEdges==MaxEdges;

}

NameTypeGetValue

(

constinti)

{return

i>=0&&

i<

NumVertices

?

NodeTable[i].data

:NULL;

}

int

NumberOfVertices

(){returnNumVertices;

}

int

NumberOfEdges(){return

NumEdges;

}

void

InsertVertex(

constNameType&

vertex);

void

RemoveVertex(

constint

v);

void

InsertEdge(

constint

v1,

constint

v2,

constDistType

weight);

void

RemoveEdge

(

constint

v1,

constint

v2);

DistTypeGetWeight

(

constint

v1,

constint

v2);

int

GetFirstNeighbor(

constint

v);

int

GetNextNeighbor(

constint

v1,

constint

v2);}網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表鄰接表的構(gòu)造函數(shù)和析構(gòu)函數(shù)template<classNameType,classDistType>Graph<NameType,DistType>::Graph(

constint

sz

=

DefaultSize):NumVertices(0),

MaxVertices(sz),

NumEdges(0){

int

n,e,k,j;

NameType

name,tail,head;

DistType

weight;

NodeTable=

//創(chuàng)建頂點表

new

Vertex<Nametype>[MaxVertices];

cin>>n; //輸入頂點個數(shù)

for(int

i=0;i<n;

i++)//輸入各頂點信息

{

cin>>name;

InserVertex(name);

}

cin

>>e;//輸入邊條數(shù)

for(i=0;

i<e;i++){//逐條邊輸入

cin

>>tail>>head>>weight;

k=

GetVertexPos

(tail);

j=

GetVertexPos

(head);

InsertEdge

(k,j,weight);}

}template<classNameType,classDistType>Graph<NameType,DistType>::~Graph(){

for(

int

i=0;

i<NumVertices;

i++){

Edge<DistType>*p=

NodeTable[i].adj;while(p!=NULL){//逐條邊釋放

NodeTable[i].adj=p→link;

delete

p;

p=

NodeTable[i].adj;}}

delete[]

NodeTable;//釋放頂點表}鄰接表部分成員函數(shù)的實現(xiàn)template<classNameType,classDistType>int

Graph<NameType,DistType>::GetVertexPos(

ConstNameType&

vertex){//根據(jù)頂點名vertex查找該頂點在鄰接表中的位置

for(

int

i=0;i<NumVertices;

i++)

if(

NodeTable[i].data==vertex)return

i;return

-1;}template<ClassNameType,classDistType>

int

Graph<NameType,DistType>::GetFirstNeighbor

(

constint

v){//查找頂點v的第一個鄰接頂點在鄰接表中的位置

if(v!=-1){ //若頂點存在

Edge<DistType>*p=

NodeTable[v].adj;if(p!=NULL)return

p→dest;}

return

-1;//若頂點不存在}template<ClassNameType,classDistTypeType>

int

Graph<NameType,DistType>::

GetNextNeighbor(

constint

v1,

constint

v2){//查找頂點v1

在鄰接頂點v2后下一個鄰接頂點

if(v1!=-1){

Edge<DistType>*p=

NodeTable[v1].adj;

while(p!=NULL){

if(p→dest==v2&&

p→link!=NULL)

return

p→link→dest;

//返回下一個鄰接頂點在鄰接表中的位置

else

p=p→link;

}}return

-1;//沒有查到下一個鄰接頂點返回-1}template<ClassNameType,classDistType>

DistType

Graph<NameType,DistType>::GetWeight(

constint

v1,

constint

v2){//取兩端點為v1和v2的邊上的權(quán)值

if(v1!=-1&&

v2!=-1){

Edge<DistType>*p=

NodeTable[v1].adj;

while(p!=NULL){

if(p→dest==v2

)return

p→cost;

else

p=p→link;

}

}

return0;}鄰接多重表(AdjacencyMultilist)在鄰接多重表中，每一條邊只有一個邊結(jié)點。為有關(guān)邊的處理提供了方便。無向圖的情形邊結(jié)點的結(jié)構(gòu)

markvertex1vertex2path1path2其中，mark是記錄是否處理過的標記；vertex1和vertex2是依附于該邊的兩頂點位置。path1域是鏈接指針，指向下一條依附于頂點vertex1的邊；path2也是鏈接指針，指向下一條依附于頂點vertex2的邊。需要時還可設(shè)置一個存放與該邊相關(guān)的權(quán)值的域cost。頂點結(jié)點的結(jié)構(gòu)存儲頂點信息的結(jié)點表以順序表方式組織，每一個頂點結(jié)點有兩個數(shù)據(jù)成員：其中，data存放與該頂點相關(guān)的信息，F(xiàn)irstout是指示第一條依附于該頂點的邊的指針。在鄰接多重表中,所有依附于同一個頂點的邊都鏈接在同一個單鏈表中。從頂點i

出發(fā),可以循鏈找到所有依附于該頂點的邊，也可以找到它的所有鄰接頂點。鄰接多重表的結(jié)構(gòu)

data

Firstout有向圖的情形在用鄰接表表示有向圖時，有時需要同時使用鄰接表和逆鄰接表。用有向圖的鄰接多重表(十字鏈表)可把這兩個表結(jié)合起來表示。邊結(jié)點的結(jié)構(gòu)

markvertex1vertex2path1path2

其中，mark是處理標記；vertex1和vertex2指明該有向邊始頂點和終頂點的位置。path1是指向始頂點與該邊相同的下一條邊的指針；path2是指向終頂點與該邊相同的下一條邊的指針。需要時還可有權(quán)值域cost。頂點結(jié)點的結(jié)構(gòu)每個頂點有一個結(jié)點，它相當于出邊表和入邊表的表頭結(jié)點：其中，數(shù)據(jù)成員data存放與該頂點相關(guān)的信息，指針Firstin指示以該頂點為始頂點的出邊表的第一條邊，F(xiàn)irstout指示以該頂點為終頂點的入邊表的第一條邊。

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

被訪問，就立即讓visited[i]

為1，防止它被多次訪問。深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索的示例DFS在訪問圖中某一起始頂點v后，由v出發(fā)，訪問它的任一鄰接頂點w1；再從w1出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點w2；然后再從

w2出發(fā)，進行類似的訪問，…如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。圖的深度優(yōu)先搜索算法viod

Graph::DFS(

constint

v,

intvisited[]){

cout

<<

GetValue(v)<<‘’;//訪問頂點

v

visited[v]=1;

//頂點v

作訪問標記

int

w=

GetFirstNeighbor

(v);

//取

v

的第一個鄰接頂點

w

while(w!=-1){

//若鄰接頂點w

存在

if(!visited[w])DFS(w,visited);

//若頂點

w

未訪問過,遞歸訪問頂點

w

w=

GetNextNeighbor(v,w);

//取頂點

v

的排在

w

后面的下一個鄰接頂點

}}

void

Graph::DFS(){

visited=new

Boolean[n];//創(chuàng)建數(shù)組visited

for(int

i=0;

i<n;

i++)visited[i]=0;

//訪問標記數(shù)組

visited

初始化

DFS(0);

delete[]visited;//釋放visited

}算法分析圖中有n個頂點，e條邊。如果用鄰接表表示圖，沿

Firstout

link鏈可以找到某個頂點v的所有鄰接頂點w。由于總共有2e個邊結(jié)點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)。廣度優(yōu)先搜索BFS(BreadthFirstSearch

)廣度優(yōu)先搜索的示例

廣度優(yōu)先搜索過程

廣度優(yōu)先生成樹使用廣度優(yōu)先搜索在訪問了起始頂點v之后，由v出發(fā)，依次訪問v的各個未曾被訪問過的鄰接頂點w1,w2,…,wt，然后再順序訪問w1,w2,…,wt的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點，…如此做下去，直到圖中所有頂點都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。為了實現(xiàn)逐層訪問，算法中使用了一個隊列，以記憶正在訪問的這一層和上一層的頂點，以便于向下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復(fù)訪問，需要一個輔助數(shù)組visited[]，給被訪問過的頂點加標記。圖的廣度優(yōu)先搜索算法void

Graph::BFS(

constint

v){

visited=newint[NumCertices];//創(chuàng)建visited

for(

int

i=0;

i<NumVertices;

i++)visited[i]=0; //visited

初始化

cout<<

GetValue(v)<<'';visited[v]=1;

Queue<int>q;

q.EnQueue

(v);//訪問v,進隊列

while(!q.IsEmpty()){//隊空搜索結(jié)束

v=q.DeQueue(); //不空,出隊列

int

w=

GetFirstNeighbor(v);

//取頂點

v

的第一個鄰接頂點

w

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

w

存在

if(!visited[w]){//若該鄰接頂點未訪問過

cout<<

GetValue(w)<<‘’;//訪問

visited[w]=1;

q.EnQueue(w);//進隊

}

w=

GetNextNeighbor(v,w);

//取頂點

v

的排在

w

后面的下一鄰接頂點}//重復(fù)檢測

v

的所有鄰接頂點

}

delete[]visited;}算法分析如果使用鄰接表表示圖，則循環(huán)的總時間代價為d0+d1+…+dn-1=O(e)，其中的di是頂點i的度。如果使用鄰接矩陣，則對于每一個被訪問過的頂點，循環(huán)要檢測矩陣中的n個元素，總的時間代價為O(n2)。連通分量(Connectedcomponent)當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷，可求得無向圖的所有連通分量。在算法中，需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。確定連通分量的算法

void

Graph::Components(){

visited=newint[NumCertices];//創(chuàng)建visited

for(

inti=0;i<NumVertices;

i++)

visited[i]=0; //visited初始化

for(i=0;

i<NumVertices;

i++)

if(!visited[i]){ //檢測所有頂點是否訪問過

DFS(i,visited);//從未訪問的頂點出發(fā)訪問

OutputNewComponent();

//輸出一個連通分量

}

delete[]visited;//釋放visited}重連通分量(BiconnectedComponent)在無向連通圖G中，當且僅當刪去G中的頂點v及所有依附于v的所有邊后，可將圖分割成兩個或兩個以上的連通分量，則稱頂點v為關(guān)節(jié)點。沒有關(guān)節(jié)點的連通圖叫做重連通圖。在重連通圖上,任何一對頂點之間至少存在有兩條路徑,在刪去某個頂點及與該頂點相關(guān)聯(lián)的邊時,也不破壞圖的連通性。一個連通圖G如果不是重連通圖，那么它可以包括幾個重連通分量。在一個無向連通圖G中,重連通分量可以利用深度優(yōu)先生成樹找到。dfn頂點的深度優(yōu)先數(shù)，標明進行深度優(yōu)先搜索時各頂點訪問的次序。如果在深度優(yōu)先生成樹中，頂點u是頂點v的祖先,則有dfn[u]<

dfn[v]。深度優(yōu)先生成樹的根是關(guān)節(jié)點的充要條件是它至少有兩個子女。其它頂點u是關(guān)節(jié)點的充要條件是它至少有一個子女w,從w出發(fā),不能通過w、w的子孫及一條回邊所組成的路徑到達u的祖先。在圖G的每一個頂點上定義一個low值，low[u]是從u或u的子孫出發(fā)通過回邊可以到達的最低深度優(yōu)先數(shù)。u是關(guān)節(jié)點的充要條件是：

u是具有兩個以上子女的生成樹的根

u

不是根，但它有一個子女w，使得

low[w]

dfn[u]這時w及其子孫不存在指向頂點u的祖先的回邊。low[u]=min{

dfn[u],min{low[w]|w是u的一個子女},

min{

dfn[x]|(u,x)是一條回邊}}計算dfn與low的算法(1)void

Graph::DfnLow(

constint

x){

//公有函數(shù)：從頂點x開始深度優(yōu)先搜索

int

num=1;

//num是訪問計數(shù)器

dfn

=newint[NumVertices];

low=newint[NumVertices];

//dfn是深度優(yōu)先數(shù),low是最小祖先訪問順序號

for(int

i=0;i<NumVertices;

i++){

dfn[i]=low[i]=0;

}

//給予訪問計數(shù)器num及dfn[u],low[u]初值

DfnLow(x,-1);

//從根x開始

delete[]

dfn;

delete[]low;}計算dfn與low的算法(2)voidGraph::DfnLow

(

constint

u,

constint

v){//私有函數(shù)：從頂點u

開始深度優(yōu)先搜索計算dfn//和low。在產(chǎn)生的生成樹中v

是u

的雙親。

dfn[u]=low[u]=

num++;

int

w=

GetFirstNeighbor(u);

while(w!=-1){//對u所有鄰接頂點w循環(huán)

if(

dfn[w]==0){//未訪問過,w是u的孩子

DfnLow(w,u);//從w遞歸深度優(yōu)先搜索

low[u]=min2(low[u],low[w]);

//子女w的low[w]先求出,再求low[u]

}elseif(w!=v)//w訪問過且w不是v，是回邊

low[u]=min2(low[u],

dfn[w]);

//根據(jù)回邊另一頂點w調(diào)整low[u]

w=

GetNextNeighbor(u,w);

//找頂點u在w后面的下一個鄰接頂點

}}

在算法DfnLow增加一些語句,可把連通圖的邊劃分到各重連通分量中。首先,根據(jù)DfnLow

(w,u)的返回,計算low[w]。如果low[w]

dfn[u]，則開始計算新的重連通分量。在算法中利用一個棧，在遇到一條邊時保存它?？稍诤瘮?shù)Biconnected中就能輸出一個重連通分量的所有的邊。當n>1時輸出重連通分量（1）void

Graph::Biconnected(){//公有函數(shù)：從頂點0開始深度優(yōu)先搜索

int

num=1;

//訪問計數(shù)器num

dfn=newint[NumVertices];//dfn是深度優(yōu)先數(shù)

low=newint[NumVertices];//low是最小祖先號

for(

int

i=0;i<NumVertices;i++)

{

dfn[i]=low[i]=0;

}

DfnLow(0,-1); //從頂點0開始

delete[]

dfn;

delete[]low;}

當n>1時輸出重連通分量（2）void

Graph::Biconnected(constintu,

constint

v){//私有函數(shù)：計算dfn與low,根據(jù)其重連通分量輸//出Graph的邊。在產(chǎn)生的生成樹中,

v

是u

的雙親//結(jié)點,S

是一個初始為空的棧，應(yīng)聲明為圖的數(shù)//據(jù)成員。

int

x,y,w;

dfn[u]=low[u]=

num++;

w=

GetFirstNeighbor(u);

//找頂點u的第一個鄰接頂點w

while(w!=-1){

if(v!=w

&&

dfn[w]<

dfn[u])S.Push((u,w));

//w不是u的雙親且w先于u被訪問,(u,w)進棧

if(

dfn[w]==0){//未訪問過,w是u的孩子

Biconnected(w,u);//從w遞歸深度優(yōu)先訪問

low[u]=min2(low[u],low[w]);

//根據(jù)先求出的low[w],調(diào)整low[u]

if(low[w]>=

dfn[u]){

//無回邊,原來的重連通分量結(jié)束

cout<<“新重連通分量:”<<end1;

do{(x,y)=S.Pop();

cout

<<x<<","<<y<<

endl;

}while((x,y)與(u,w)不是同一條邊);

}//輸出該重連通分量的各邊

}

elseif(w!=v)

//有回邊,計算

low[u]=min2(low[u],

dfn[w]);//根據(jù)回邊另一頂點w調(diào)整low[u]

w=

GetNextNeighbor

(u,w);

//找頂點u的鄰接頂點w的下一個鄰接頂點

}}算法Biconnected

的時間代價是O(n+e)。其中n

是該連通圖的頂點數(shù)，e是該連通圖的邊數(shù)。此算法的前提條件是連通圖中至少有兩個頂點,因為正好有一個頂點的圖連一條邊也沒有。最小生成樹

(minimumcostspanningtree)使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n個頂點的連通網(wǎng)絡(luò)的生成樹有n個頂點、n-1條邊。構(gòu)造最小生成樹的準則必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；必須使用且僅使用n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點；不能使用產(chǎn)生回路的邊?？唆斔箍?Kruskal)算法克魯斯卡爾算法的基本思想：設(shè)有一個有n個頂點的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個只有n個頂點，沒有邊的非連通圖T={V,},

圖中每個頂點自成一個連通分量。當在E中選到一條具有最小權(quán)值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中；否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去，直到所有頂點在同一個連通分量上為止。算法的框架 我們利用最小堆(MinHeap)和并查集(DisjointSets)來實現(xiàn)克魯斯卡爾算法。首先，利用最小堆來存放E中的所有的邊,堆中每個結(jié)點的格式為在構(gòu)造最小生成樹的過程中，最小堆中存放剩余的邊，并且利用并查集的運算檢查依附于一條邊的兩個頂點tail、haed是否在同一個連通分量(即并查集的同一個子集合)上,是則舍去這條邊；否則將此邊加入T，同時將這兩個頂點放在同一個連通分量上。隨著各邊逐步加入到最小生成樹的邊集合中，各連通分量也在逐步合并，直到形成一個連通分量為止。tailheadcost

邊的兩個頂點位置邊的權(quán)值應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程最小生成樹類定義constint

MAXINT=機器可表示的, 問題中不可能出現(xiàn)的大數(shù)class

MinSpanTree;

class

MSTEdgeNode

{

//生成樹邊結(jié)點類定義friendclass

MinSpanTree;private:

int

tail,head;

//生成樹各邊的兩頂點

int

cost; //生成樹各邊的代價};class

MinSpanTree

{ //生成樹的類定義public:

MinSpanTree

(

int

sz=MaxEdges

-1):

MaxSize

(sz),n(0)

{

edgevalue=new

MSTEdgeNode[MaxSize];

}

int

Insert(MSTEdgeNode&item);

//將item加到最小生成樹中protected:

MSTEdgeNode*edgevalue;

//邊值數(shù)組

int

MaxSize,n;

//最大邊數(shù),當前邊數(shù)};利用克魯斯卡爾算法建立最小生成樹void

Graph<string,float>::Kruskal(

MinSpanTree

&T){

MSTEdgeNodee;

//邊結(jié)點輔助單元

MinHeap<MstEdgeNode>

H(CurrentEdges);

intNumVertices=VerticesList.last;

//頂點個數(shù)

UFSets

F(NumVertices);//并查集F并初始化

for(

int

u=0;

u<

NumVertices;

u++)//鄰接矩陣

for(

int

v=i+1;

v<

NumVertices;

v++)

if(Edge[u][v]!=MAXINT){//檢出所有邊

e.tail=u;

e.head=v;

e.cost=w;

H.Insert(e);

//插入最小堆 }

int

count=1;

//最小生成樹加入邊數(shù)的計數(shù)

while(count<

NumVertices){//

e=H.RemoveMin(); //從堆中退出一條邊

u=F.Find(e.tail);//檢測兩端點的根

v=F.Find(e.head);

if(u!=v){//根不同,不在同一連通分量上

F.Union(u,v);//合并

T.Insert(e);

//該邊存入最小生成樹T中

count++;}}}在建立最小堆時需要檢測鄰接矩陣，計算的時間代價為O(n2)。且做了e

次堆插入操作,每次插入調(diào)用了一個堆調(diào)整算法SiftUp()算法,因此堆插入需要的時間代價為O(elog2e)。在構(gòu)造最小生成樹時，最多調(diào)用了e次出堆操作RemoveMin(

)，2e次并查集的Find()操作，n-1次Union()操作，計算時間分別為O(elog2e)，O(elog2n)和O(n)。總的計算時間為O(elog2e+elog2n+n)普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡(luò)N={V,E}中的某一頂點u0

出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v)，將其頂點加入到生成樹的頂點集合U中。 以后每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續(xù)下去，直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合U中為止。采用鄰接矩陣作為圖的存儲表示。用普里姆算法構(gòu)造最小生成樹的過程在構(gòu)造過程中，還設(shè)置了兩個輔助數(shù)組：

lowcost[]

存放生成樹頂點集合內(nèi)頂點到生成樹外各頂點的各邊上的當前最小權(quán)值；

nearvex[]

記錄生成樹頂點集合外各頂點距離集合內(nèi)哪個頂點最近(即權(quán)值最小)。例子若選擇從頂點0出發(fā)，即u0=0，則兩個輔助數(shù)組的初始狀態(tài)為：然后反復(fù)做以下工作：

在

lowcost

[]中選擇

nearvex[i]

-1

&&

lowcost[i]最小的邊

i

用v

標記它。則選中的權(quán)值最小的邊為(nearvex[v],v)，相應(yīng)的權(quán)值為

lowcost[v]。

將nearvex[v]改為-1,表示它已加入生成樹頂點集合。將邊(nearvex[v],v,

lowcost[v])

加入生成樹的邊集合。

取lowcost[i]=min{

lowcost[i],Edge[v][i]

}，即用生成樹頂點集合外各頂點

i

到剛加入該集合的新頂點v

的距離Edge[v][i]

與原來它們到生成樹頂點集合中頂點的最短距離lowcost[i]

做比較,取距離近的作為這些集合外頂點到生成樹頂點集合內(nèi)頂點的最短距離。如果生成樹頂點集合外頂點i到剛加入該集合的新頂點v的距離比原來它到生成樹頂點集合中頂點的最短距離還要近，則修改nearvex[i]：nearvex[i]=v。表示生成樹外頂點i到生成樹內(nèi)頂點v當前距離最近。

繼續(xù)重復(fù)得：頂點5加入生成樹頂點集合：v=5v=4最后生成樹中邊集合里存入得各條邊為：

(0,5,10),(5,4,25),(4,3,22), (3,2,12),(2,1,16),(1,6,14)利用普里姆算法建立最小生成樹void

Graph<string,float>::Prim(

MinSpanTree&T){

int

NumVertices

=

VerticesList.last;

//圖中頂點數(shù)

lowcost=newint[NumVertices];

nearvex=newint[NumVertices];

for(

int

i=1;

i<NumVertices;

i++){

lowcost[i]=Edge[0][i];//頂點0到各邊的代價

nearvex[i]=0; //及最短帶權(quán)路徑

}

nearvex[0]=-1;//頂點0加到生成樹頂點集合

int

count=0;//生成樹邊值數(shù)組存放指針

MSTEdgeNodee;//最小生成樹結(jié)點輔助單元

for(i=1;

i<NumVertices;

i++){

//循環(huán)n-1次,加入n-1條邊

int

min=MAXINT;

int

v=0; for(

int

j=0;

j<NumVertices;

j++)

if(

nearvex[j]!=-1&&

lowcost[j]<min)

{

v=j;

min=

lowcost[j];}//求生成樹外頂點到生成樹內(nèi)頂點具有最小//權(quán)值的邊,v是當前具最小權(quán)值的邊的位置

if(v){//v==0表示再也找不到要求的頂點了

count++; //向生成樹邊值數(shù)組內(nèi)存放

e.tail=

nearvex[v];e.head=v;

e.cost=

lowcost[v];

T.Insert

(e);

//選出的邊加入生成樹

nearvex[v]=-1;//作該邊已加入生成樹標記

for(j=1;

j<

NumVertices;

j++)

if(

nearvex[j]!=-1&&

//j不在生成樹中

Edge[v][j]<

lowcost[j]){//需要修改

lowcost[j]=Edge[v][j];

nearvex[j]=v;}

}

}}

分析以上算法，設(shè)連通網(wǎng)絡(luò)有n個頂點

，則該算法的時間復(fù)雜度為O(n2),它適用于邊稠密的網(wǎng)絡(luò)。最短路徑(ShortestPath)最短路徑問題：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。問題解法邊上權(quán)值非負情形的單源最短路徑問題—

Dijkstra算法邊上權(quán)值為任意值的單源最短路徑問題

—Bellman和Ford算法所有頂點之間的最短路徑—Floyd算法邊上權(quán)值非負情形的單源最短路徑問題問題的提法：給定一個帶權(quán)有向圖D與源點v，求從v到D中其它頂點的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。舉例說明Dijkstra逐步求解的過程引入一個輔助數(shù)組dist。它的每一個分量dist[i]表示當前找到的從源點v0到終點vi

的最短路徑的長度。初始狀態(tài)：若從源點v0到頂點vi有邊，則dist[i]為該邊上的權(quán)值；若從源點v0到頂點vi

沒有邊，則dist[i]為+。一般情況下，假設(shè)S是已求得的最短路徑的終點的集合，則可證明：下一條最短路徑必然是從v0出發(fā)，中間只經(jīng)過S中的頂點便可到達的那些頂點vx(vx

V-S)的路徑中的一條。每次求得一條最短路徑之后，其終點vk

加入集合S，然后對所有的vi

V-S，修改其dist[i]值。Dijkstra算法可描述如下：初始化：S←{v0};

dist[j]←Edge[0][j],j=1,2,…,n-1;

//n為圖中頂點個數(shù)求出最短路徑的長度：

dist[k]←min{dist[i]},i

V-S;S←S

U{k

};

修改：

dist[i]←min{dist[i],dist[k]+Edge[k][i]},