課程大數(shù)據(jù)結(jié)構(gòu)第8章2011秋季

圖的基本概念圖的存儲表示圖的遍歷與連通性最小生成樹最短路徑活動網(wǎng)絡(luò)1第八章

圖圖的基本概念2圖定義

圖是由頂點集合(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的一條單向通路,

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

n個頂點的無向圖有

n(n-1)/2條邊,則此圖為完全無向圖。有

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

0

0

111221225

6433子圖鄰接頂點

如果

(u,

v)

是

E(G)

中的一條邊，則稱

u與

v

互為鄰接頂點。子圖

設(shè)有兩個圖G＝(V,

E)

和G'＝(V',

E')。若V

'?

V

且E'?

E,

則稱圖G'是圖G的子圖。0

0

0

041

2

1

1

2

23

3

3

3權(quán)

某些圖的邊具有與它相關(guān)的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。頂點的度一個頂點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，到達(dá)頂點vj。則稱頂點序列(vi

vp1vp2...vpm

vj)為從頂點vi到頂點vj

的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。5路徑長度

非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑

若路徑上各頂點

v1,

v2,...,

vm均不互相重復(fù),

則稱這樣的路徑為簡單路徑?；芈?/p>

若路徑上第一個頂點

v1與最后一個頂點vm

重合,

則稱這樣的路徑為回路或環(huán)。0

0

01

2

1

2

1

23

3

36連通圖與連通分量

在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強(qiáng)連通圖與強(qiáng)連通分量在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。生成樹一個連通圖的生成樹是其極小連通子圖，在n

個頂點的情形下，有n-1

條邊。7圖的抽象數(shù)據(jù)類型8class

Graph

{//對象:由一個頂點的非空集合和一個邊集合構(gòu)成//每條邊由一個頂點對來表示。

public:Graph();

//建立一個空的圖

void

insertVertex(const

T&

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

insertEdge

(intv1,

int

v2,int

weight);//在圖中插入一條邊(v1,

v2,

w)void

removeVertex

(int

v);//在圖中刪除頂點v和所有關(guān)聯(lián)到它的邊void

removeEdge(int

v1,

int

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

IsEmpty();//若圖中沒有頂點,則返回true,

否則返回falseT

getWeight

(intv1,

int

v2);//函數(shù)返回邊(v1,v2)

的權(quán)值int

getFirstNeighbor(int

v);//給出頂點v

第一個鄰接頂點的位置int

getNextNeighbor

(int

v,

int

w);//給出頂點v的某鄰接頂點w的下一個鄰接頂點};9圖的存儲表示10圖的模板基類

在模板類定義中的數(shù)據(jù)類型參數(shù)表<classT,classE>

中，T是頂點數(shù)據(jù)的類型，E是邊上所附數(shù)據(jù)的類型。這個模板基類是按照最復(fù)雜的情況（即帶權(quán)無向圖）來定義的，如果需要使用非帶權(quán)圖，可將數(shù)據(jù)類型參數(shù)表<class

T,

classE>改為<class

T>。如果使用的是有向圖，也可以對程序做相應(yīng)的改動。圖的模板基類11//無窮大的值(=￥)//最大頂點數(shù)(=n)constintmaxWeight

=

……;constintDefaultVertices

=30;template

<class

T,class

E>//圖的類定義class

Graph{protected:int

maxVertices;int

numEdges;int

numVertices;//圖中最大頂點數(shù)//當(dāng)前邊數(shù)//當(dāng)前頂點數(shù)int

getVertexPos

(T

vertex);//給出頂點vertex在圖中位置

public:Graph(int

sz=DefaultVertices);

//構(gòu)造函數(shù)12//析構(gòu)函數(shù)//判圖空否～Graph();bool

GraphEmpty()

const{return

numEdges

==

0;

}int

NumberOfVertices

()

{

return

numVertices;

}//返回當(dāng)前頂點數(shù)int

NumberOfEdges

()

{

return

numEdges;

}//返回當(dāng)前邊數(shù)virtual

T

getValue

(int

i);

//取頂點

i

的值virtual

E

getWeight

(int

v1,int

v2);

//取邊上權(quán)值virtual

int

getFirstNeighbor

(intv);//取頂點v

的第一個鄰接頂點virtualint

getNextNeighbor

(int

v,

intw);//取鄰接頂點w

的下一鄰接頂點virtual

bool

insertVertex

(const

T

vertex);//插入一個頂點vertexvirtual

bool

insertEdge

(intv1,

int

v2,

E

cost);//插入邊(v1,v2),

權(quán)為costvirtualbool

removeVertex(int

v);//刪去頂點v

和所有與相關(guān)聯(lián)邊virtual

bool

removeEdge

(intv1,

int

v2);//在圖中刪去邊(v1,v2)};13鄰接矩陣(Adjacency

Matrix)14在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關(guān)系的鄰接矩陣。設(shè)圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數(shù)組A.edge[n][n]，定義：如果<

i,

j

>?

E

或者

(i,

j)

?

E0,

否則A.Edge[i][

j]

=

1,

0

1

0

1

1

0

1

0

0

1

0

1

=

1

0

1

0

A.edge0123012無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0

1

0

A.edge

=

1

0

10

0

015在有向圖中,統(tǒng)計第i行1的個數(shù)可得頂點i的出度，統(tǒng)計第j

列1

的個數(shù)可得頂點j

的入度。在無向圖中,統(tǒng)計第i行(列)1的個數(shù)可得頂點i的度。網(wǎng)絡(luò)的鄰接矩陣160,若i

?j且<i,

j

>?

E或(i,

j)?

E若i

?j且<i,

j

>ˇ

E或(i,

j)ˇ

E若i

==jW(i,

j),A.edge[i][

j]

=

￥

,

0

1

￥

40

9

2

3

5

0

8￥

￥

6

0A.edge

=

￥86312954230

1用鄰接矩陣表示的圖的類定義template

<class

T,class

E>class

Graphmtx

:

public

Graph<T,E>

{friend

istream&

operator

>>

(

istream&

in,Graphmtx<T,E>&

G);

//輸入17friend

ostream&

operator

<<

(ostream&

out,18//輸出//頂點表//鄰接矩陣Graphmtx<T,E>&

G);private:T

*VerticesList;E

**Edge;int

getVertexPos

(T

vertex)

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

for

(int

i=0;i

<numVertices;i++)if(VerticesList[i]

==

Vertex)

return

i;return-1;};public:Graphmtx

(int

sz

=DefaultVertices);～Graphmtx

()19//構(gòu)造函數(shù)//析構(gòu)函數(shù){delete[]VerticesList; delete

[]Edge;

}T

getValue

(int

i){//取頂點i

的值,i

不合理返回0return

i

>=

0

&&

i<=

numVertices

?VerticesList[i]

:NULL;}E

getWeight(intv1,int

v2)

{

//取邊(v1,v2)上權(quán)值

return

v1!=-1

&&

v2

!=-1

?Edge[v1][v2]

:0;}int

getFirstNeighbor

(int

v);//取頂點v

的第一個鄰接頂點int

getNextNeighbor(int

v,

int

w);//取v

的鄰接頂點w

的下一鄰接頂點bool

insertVertex

(const

Tvertex);//插入頂點vertexbool

insertEdge

(intv1,

int

v2,

E

cost);//插入邊(v1,v2),權(quán)值為costbool

removeVertex(int

v);//刪去頂點v

和所有與它相關(guān)聯(lián)的邊bool

removeEdge

(int

v1,int

v2);//在圖中刪去邊(v1,v2)};20//構(gòu)造函數(shù)21template

<class

T,class

E>Graphmtx<T,

E>::Graphmtx

(int

sz)

{maxVertices

=

sz;numVertices

=

0;

numEdges=0;int

i,

j;VerticesList

=newT[maxVertices];

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

=

(int

**)

new

int*[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;};template

<class

T,class

E>int

Graphmtx<T,E>::getFirstNeighbor

(int

v)

{//給出頂點位置為v的第一個鄰接頂點的位置,//如果找不到,則函數(shù)返回-1if(v

!=

-1)

{for

(intcol

=

0;

col<

numVertices;

col++)if

(Edge[v][col]

&&

Edge[v][col]

<

maxWeight)return

col;}return-1;};22template

<class

T,class

E>intGraphmtx<T,

E>::getNextNeighbor

(int

v,

int

w)

{//給出頂點v

的某鄰接頂點w

的下一個鄰接頂點if(v!=-1

&&

w

!=

-1)

{for

(int

col

=

w+1;

col

<

numVertices;

col++)if

(Edge[v][col]

&&

Edge[v][col]

<

maxWeight)return

col;}return-1;};23鄰接表是鄰接矩陣的改進(jìn)形式。為此需要

把鄰接矩陣的各行分別組織為一個單鏈表。在鄰接表中，同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點代表一條邊（邊結(jié)點），結(jié)點中有另一頂點的下標(biāo)

dest和指針link。對于帶權(quán)圖，邊結(jié)點中還要保存該邊的權(quán)值cost。頂點表的第i個頂點中保存該頂點的數(shù)據(jù)，以及它對應(yīng)邊鏈表的頭指針adj。24鄰接表(Adjacency

List)ABCDBCD123dataadj destlink25destlink0

A

130210無向圖的鄰接表統(tǒng)計某頂點對應(yīng)邊鏈表中結(jié)點個數(shù)，可得該頂點的度。某條邊(vi,vj)在鄰接表中有兩個邊結(jié)點，分別在第

i

個頂點和第j

個頂點對應(yīng)的邊鏈表中。ABC012dataadj dest

linkdestlinkdataadjBC0

A12鄰接表(出邊表)destlink逆鄰接表(入邊表)102011有向圖的鄰接表和逆鄰接表A26BC69A5BD2C8ABCD0123dataadj dest

cost

link1536283219(出邊表)27(頂點表)網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表統(tǒng)計出邊表中結(jié)點個數(shù)，得到該頂點的出度；統(tǒng)計入邊表中結(jié)點個數(shù)，得到該頂點的入度。用鄰接表表示的圖的類定義28template

<class

T,class

E>struct

Edge

{int

dest;E

cost;Edge<T,

E>

*link;Edge

()

{}Edge

(int

num,E

cost)//邊結(jié)點的定義//邊的另一頂點位置//邊上的權(quán)值//下一條邊鏈指針//構(gòu)造函數(shù)//構(gòu)造函數(shù):

dest(num),

weight

(cost),

link

(NULL)

{

}booloperator

!=

(Edge<T,E>&

R)const{return

dest

!=R.dest;}

//判邊等否};//頂點的定義//頂點的名字//邊鏈表的頭指針29template

<class

T,classE>struct

Vertex{T

data;Edge<T,E>

*adj;};//圖的類定template

<class

T,classE>class

Graphlnk

:

publicGraph<T,

E>

{義friend

istream&

operator

>>

(istream&

in,Graphlnk<T,E>&

G);

//輸入

friendostream&operator<<(ostream&out,Graphlnk<T,E>&

G);

//輸出private:Vertex<T,

E>

*NodeTable;//頂點表(各邊鏈表的頭結(jié)點)int

getVertexPos

(const

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

for(int

i=0;i

<numVertices;i++)if(NodeTable[i].data

==

vertx)return

i;return

-1;}public:Graphlnk(intsz=DefaultVertices);

//構(gòu)造函數(shù)~Graphlnk();

//析構(gòu)函數(shù)30T

getValue(int

i){

//取頂點i

的值return

(i

>=

0

&&

i<

NumVertices)

?NodeTable[i].data

:

0;}E

getWeight(int

v1,int

v2);

//取邊(v1,v2)權(quán)值

bool

insertVertex(const

T&

vertex);bool

removeVertex

(int

v);bool

insertEdge

(int

v1,

int

v2,

E

cost);bool

removeEdge

(int

v1,int

v2);int

getFirstNeighbor

(int

v);int

getNextNeighbor(int

v,

int

w);};31template

<class

T,classE>Graphlnk<T,

E>::Graphlnk

(int

sz){//構(gòu)造函數(shù)：建立一個空的鄰接表maxVertices

=

sz;numVertices=0;

numEdges

=

0;NodeTable

=new

Vertex<T,

E>[maxVertices];//創(chuàng)建頂點表數(shù)組

if(NodeTable

==NULL){

cerr

<<

"存儲分配錯！"

<<

endl;

exit(1);}for

(inti

=

0;

i

<

maxVertices;

i++)NodeTable[i].adj

=

NULL;};32template

<class

T,classE>Graphlnk<T,

E>::～Graphlnk(){//析構(gòu)函數(shù)：刪除一個鄰接表for

(int

i=0;

i<numVertices;

i++

)

{Edge<T,E>*p

=

NodeTable[i].adj;while

(p!=

NULL)

{NodeTable[i].adj

=

p->link;deletep;

p

=NodeTable[i].link;}}delete

[]NodeTable;

//刪除頂點表數(shù)組};33//對34template

<class

T,class

E>intGraphlnk<T,

E>::getFirstNeighbor

(int

v)

{//給出頂點位置為v

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

!=-1)

{ //頂點v存在Edge<T,

E>

*p

=

NodeTable[v].adj;應(yīng)邊鏈表第一個邊結(jié)點if

(p

!=

NULL)

return

p->dest;//存在,返回第一個鄰接頂點}return-1;

//第一個鄰接頂點不存在};template

<class

T,class

E>intGraphlnk<T,

E>::getNextNeighbor(int

v,int

w)

{//給出頂點v的鄰接頂點w的下一個鄰接頂點的位置,//若沒有下一個鄰接頂點,則函數(shù)返回-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)return

p->link->dest;

//返回下一個鄰接頂點}return-1;

//下一鄰接頂點不存在};35鄰接多重表(Adjacency

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

是記錄是否處理過的標(biāo)記;vertex1和vertex2是該邊兩頂點位置。path1域是鏈接指針,指向下一條依附頂點vertex1的邊；path2是指向下一條依附頂點vertex2的邊鏈接指針。markvertex1vertex2path1path236需要時還可設(shè)置一個存放與該邊相關(guān)的權(quán)值的域cost。頂點結(jié)點的結(jié)構(gòu)data

Firstout頂點信息的結(jié)點表以順序表方式組織,每一個頂點結(jié)點有兩個數(shù)據(jù)成員：其中，data存放與該頂點相關(guān)的信息，F(xiàn)irstout是指示第一條依附該頂點的邊的指針。在鄰接多重表中,

所有依附同一個頂點的邊都鏈接在同一個單鏈表中。37mark

vtx1

vtx2

path1

path2010213e1e2e3ABD012

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

Fout38有向圖的情形在用鄰接表表示有向圖時,有時需要同時使用鄰接表和逆鄰接表。用有向圖的鄰接多重表(十字鏈表)可把兩個表結(jié)合起來表示。邊結(jié)點的結(jié)構(gòu)其中，mark是處理標(biāo)記；vertex1和vertex2指明該有向邊始頂點和終頂點的位置。path1是指向始頂點與該邊相同的下一條邊的指針；path2是指向終頂點與該邊相同的下一條邊的指針。需要時還可有權(quán)值域cost。markvertex1vertex2path1path239頂點結(jié)點的結(jié)構(gòu)每個頂點有一個結(jié)點，它相當(dāng)于出邊表和入邊表的表頭結(jié)點：其中，數(shù)據(jù)成員data存放與該頂點相關(guān)的信息，指針Firstin

指示以該頂點為始頂點的出邊表的第一條邊，F(xiàn)irstout指示以該頂點為終頂點的入邊表的第一條邊。data40FirstinFirstout0

1031223344

0e1e2e3e4e5e6data

Fin

Fout

mark

vtx1

vtx2

path1

path2E0

A2

C3

D4e411e3e

1

B5ABe4Ce6e2DE鄰接多重表的結(jié)構(gòu)圖的遍歷與連通性42從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪

遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷(Graph

Traversal)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。為了避免重復(fù)訪問，可設(shè)置一個標(biāo)志頂點是否被訪問過的輔助數(shù)組visited[]。輔助數(shù)組visited[]的初始狀態(tài)為0,在圖的遍歷過程中,一旦某一個頂點i

被訪問,就立即讓

visited[i]為1,

防止它被多次訪問。圖的遍歷的分類:深度優(yōu)先搜索DFS

(Depth

First

Search)廣度優(yōu)先搜索BFS

(Breadth

First

Search)43深度優(yōu)先搜索DFS(Depth

First

Search)深度優(yōu)先搜索的示例FH

ICH1A2B3EG

4C

567

D1A2B3EG

456

F7

D8I9回退8

9前進(jìn)深度優(yōu)先搜索過程44深度優(yōu)先生成樹DFS

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

后,由v

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

出發(fā),訪問與w1鄰接但還沒有訪問過的頂點w2;然后再從w2出發(fā),進(jìn)行類似的訪問,…如此進(jìn)行下去,直至到達(dá)所有的鄰接頂點都被訪問過的頂點u

為止。接著,

退回一步,

退到前一次剛訪問過的頂點,

看是否還有其它沒有被訪問的鄰接頂點。如果有,

則訪問此頂點,

之后再從此頂點出發(fā),

進(jìn)行與前述類似的訪問;

如果沒有,

就再退回一步進(jìn)行搜索。重復(fù)上述過程,直到連通圖中所有頂點都被訪問過為止。45圖的深度優(yōu)先搜索算法46template<class

T,

class

E>void

DFS

(Graph<T,

E>&

G,const

T&

v)

{//從頂點v出發(fā)對圖G進(jìn)行深度優(yōu)先遍歷的主過程int

i,

loc,n=G.NumberOfVertices();

//頂點個數(shù)bool

*visited

=

new

bool[n];

//創(chuàng)建輔助數(shù)組for

(i

=

0;

i

<

n;i++)

visited[i]

=

false;//輔助數(shù)組visited初始化loc

=G.getVertexPos(v);DFS

(G,

loc,

visited);

//從頂點0開始深度優(yōu)先搜索delete[]

visited;

//釋放visited};template<class

T,

class

E>void

DFS

(Graph<T,

E>&

G,int

v,

bool

visited[])

{47cout<<

G.getValue(v)

<<'';visited[v]

=

true;//訪問頂點v//作訪問標(biāo)記int

w=G.getFirstNeighbor

(v);

//第一個鄰接頂點

while

(w

!=-1)

{//若鄰接頂點w存在if

(!visited[w]

)

DFS(G,

w,

visited);//若w未訪問過,遞歸訪問頂點ww

=G.getNextNeighbor(v,w);//下一個鄰接頂點}};廣度優(yōu)先搜索BFS

(Breadth

First

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

34

D5E6G

78

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

34

D5E6

FG

78

9廣度優(yōu)先生成樹I48BFS在訪問了起始頂點v

之后,由v

出發(fā),依次訪問v

的各個未被訪問過的鄰接頂點w1,

w2,

…,

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

<class

T,classE>void

BFS

(Graph<T,

E>&

G,

const

T&

v){int

i,

w,

n

=

G.NumberOfVertices();//圖中頂點個數(shù)50bool

*visited

=

new

bool[n];for

(i

=

0;

i

<

n;

i++)

visited[i]

=

false;51//取頂點號//訪問頂點v//做已訪問標(biāo)記int

loc

=

G.getVertexPos

(v);cout

<<

G.getValue

(loc)

<<

'

';visited[loc]

=

true;Queue<int>

Q;

Q.EnQueue

(loc);//頂點進(jìn)隊列,實現(xiàn)分層訪問while

(!Q.IsEmpty()){

//循環(huán),訪問所有結(jié)點Q.DeQueue

(loc);w=G.getFirstNeighbor

(loc);

//第一個鄰接頂點while

(w

!=

-1)

{if

(!visited[w])

{//若鄰接頂點w存在//若未訪問過cout<<G.getValue

(w)<<'';

//訪問visited[w]

=

true;Q.EnQueue

(w);

//頂點w進(jìn)隊列}w

=

G.getNextNeighbor

(loc,

w);//找頂點loc的下一個鄰接頂點}}

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

delete

[]visited;};52連通分量(Connected

component)53當(dāng)無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在最大連通子圖（連通分量）的所有頂點。若從無向圖每一連通分量中的一個頂點出發(fā)進(jìn)行遍歷,可求得無向圖的所有連通分量。例如，對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。ADEB

CFGOIHL

M

NKAJ非連通無向圖HKDEIB

CFOL

M

NG

J非連通圖的生成森林54確定連通分量的算法55template

<class

T,class

E>void

Components

(Graph<T,E>&

G)

{//通過DFS，找出無向圖的所有連通分量//圖中頂點個數(shù)//訪問標(biāo)記數(shù)組int

i,

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();

//輸出連通分量}delete[]visited;}例：以深度優(yōu)先搜索方法從頂點

A

出發(fā)遍歷圖,建立深度優(yōu)先生成森林。有向圖A

B

CDEFGABCE

D

FG深度優(yōu)先生成森林56template<class

T,

classE>void

DFS_Forest

(Graph<T,

E>&

G,Tree

<T,

E>&

F)

{TreeNode

<T,

E>

*

rt,

*

subT;int

n

=

G.NumberOfVertices();static

int

*visited=new

int[n];

//訪問數(shù)組

for

(int

i=0;i

<n;i++)

visited

[i]=0;57for

(i

=

0;

i

<

n;

i++)if

(!visited[i])

{if

(F.IsEmpty())//遍歷所有頂點//頂點i

未訪問過//F原為空生成森林,建根subT

=

rt

=

F.BuildRoot(G.GetValue(i));//頂點i

的值成為根rt

的值else

subT

=

F.InsertRightSibling(subT,

G.GetValue(i));//頂點i

的值成為subT

右兄弟的值DFS_Tree

(G,

F,

subT,

i,

visited);//從頂點i

出發(fā)深度優(yōu)先遍歷,建子樹}}template<class

T,

class

E>void

DFS_Tree

(Graph<T,

E>&

G,

Tree<T,

E>&F,TreeNode

<T,

E>*

rt,

int

v, int

visited

[])

{TreeNode<T,

E>

*

p;58visited[v]=1;

//頂點v作訪問過標(biāo)志

int

w=G.GetFirstNeighbor

(v);//取頂點v的第一個鄰接頂點wint

FirstChild=1;//第一個未訪問子女應(yīng)是v的左子女while

(

w

!=

-1

)

{

//鄰接頂點w存在if

(!

visited

[w])

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

(FirstChild)

{p

=

F.InsertLeftChild

(rt,

G.GetValue(w));//p插入為rt的左子女59FirstChild=0;

//建右兄弟}else

p

=

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

存在};60重連通分量

(Biconnected

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

的祖先。62ABCDEFGHIJJABCED

FGHJII2

B3

A1

6D

FG

7H

8910根有兩個子女關(guān)節(jié)點關(guān)節(jié)

4

C點5

E關(guān)節(jié)點63最小生成樹(

minimum

cost

spanning

tree

)64使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n個頂點的連通網(wǎng)絡(luò)的生成樹有n

個頂點、n-1條邊。構(gòu)造最小生成樹假設(shè)有一個網(wǎng)絡(luò)，用以表示n個城市之間架設(shè)通信線路，邊上的權(quán)值代表架設(shè)通信線路的成本。如何架設(shè)才能使線路架設(shè)的成本達(dá)到最?。繕?gòu)造最小生成樹的準(zhǔn)則必須使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n

個頂點；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達(dá)到最小。北京

天津65廣州34南京6上海4131724武漢1925382222西安19成都31昆明3944585066廣州南京6上海724武漢192222西安19成都31昆明北京

天津廣州34南京6上海41北京

天津31724武漢1925382222西安19成都31昆明39445850克魯斯卡爾(Kruskal)算法67克魯斯卡爾算法的基本思想：設(shè)有一個有n個頂點的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個只有n

個頂點,沒有邊的非連通圖T={V,?

},

圖中每個頂點自成一個連通分量。當(dāng)在E

中選到一條具有最小權(quán)值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T

中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點在同一個連通分量上為止。Kruskal算法的偽代碼描述68T

=?

;

//T是最小生成樹的邊集合//E是帶權(quán)無向圖的邊集合while(T

包含的邊少于n-1

&&E不空){從E

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

中刪去(v,w);如果(v,w)加到T

中后不會產(chǎn)生回路,則將(v,w)加入T;否則放棄(v,w);}if(T

中包含的邊少于n-1條)cout<<"不是最小生成樹"<<endl;算法的框架

利用最小堆(MinHeap)和并查集(DisjointSets)來實現(xiàn)克魯斯卡爾算法。首先,利用最小堆來存放E中的所有的邊,堆中每個結(jié)點的格式為邊的兩個頂點位置 邊的權(quán)值在構(gòu)造最小生成樹過程中,

利用并查集的運算檢查依附一條邊的兩頂點tail、head是否在同一連通分量

(即并查集的同一個子集合)

上,

是則舍去這條邊；否則將此邊加入T,

同時將這兩個頂點放在同一個連通分量上。69tailheadcost隨著各邊逐步加入到最小生成樹的邊集合中,各連通分量也在逐步合并,直到形成一個連通分量為止。0

128105251462442216218

123544106

2

5

60

1

0

12原圖3(a)3(b)構(gòu)造最小生成樹的過程70120128105251462442218316

102

51204610412102

514612原圖413010514612(e)(f)(g)43016

102

53(c)11462243(d)1016

102

512

251462216212371最小生成樹類定義72constfloat

maxValue

=

FLOAT_MAX//機(jī)器可表示的、問題中不可能出現(xiàn)的大數(shù)

template

<class

T,class

E>struct

MSTEdgeNode

{int

tail,

head;E

cost;//樹邊結(jié)點的類定義//兩頂點位置//邊上的權(quán)值MSTEdgeNode()

:

tail(-1),

head(-1),cost(0)

{

}//構(gòu)造函數(shù)};template

<class

T,class

E>class

MinSpanTree

{

//樹的類定義

protected:MSTEdgeNode<T,E>*edgevalue;//邊值數(shù)組

int

maxSize,n;//最大元素個數(shù)和當(dāng)前個數(shù)public:MinSpanTree

(int

sz

=DefaultSize-1)

:MaxSize

(sz),

n

(0)

{edgevalue=

new

MSTEdgeNode<T,

E>[sz];}int

Insert

(MSTEdgeNode&

item);};73在求解最小生成樹時，可以用鄰接矩陣存儲圖，也可以用鄰接表存儲圖。算法中使用圖的抽象基類的操作，無需考慮圖及其操作的具體實現(xiàn)。Kruskal算法的實現(xiàn)#include

"heap.h"#include

"UFSets.h"template

<class

T,class

E>void

Kruskal

(Graph<T,

E>&

G,MinSpanTree<T,

E>&

MST)

{74//邊結(jié)點輔助單元75MSTEdgeNode<T,

E>

ed;int

u,

v,

count;int

n

=

G.NumberOfVertices();int

m

=

G.NumberOfEdges();//頂點數(shù)//邊數(shù)MinHeap

<MSTEdgeNode<T,

E>>

H(m);//最小堆//并查集UFSets

F(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);}count

=

1;while

(count

<

n)

{H.Remove(ed);76//最小生成樹邊數(shù)計數(shù)//反復(fù)執(zhí)行,取n-1條邊//退出具最小權(quán)值的邊u

=

F.Find(ed.tail);

v

=

F.Find(ed.head);//取兩頂點所在集合的根u與v//不是同一集合,不連通//合并,連通它們//該邊存入MSTif

(u

!=

v)

{F.Union(u,

v);MST.Insert(ed);count++;}}}；出堆順序(1,6,14)

選中(0,5,10)

選中(1,2,16)

選中(4,6,24)

舍棄(2,3,12)

選中(3,6,18)

舍棄(4,5,25)

選中并查集原圖-2-2-2-2-1-1-1-1-1-1-1-1-1-1-1-102-1-1-10-220000(3,4,22)

選中0

1

2

3

4

5

6-21-11-2-1-421-2-51211-711211F012877105251462442216218

123(0,5,10)(2,3,12)(1,6,14)(1,2,16)(3,4,22)(4,5,25)普里姆(Prim)算法78普里姆算法的基本思想：從連通網(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中為止。普里姆(Prim)的偽代碼描述79選定構(gòu)造最小生成樹的出發(fā)頂點u0;Vmst

=

{u0}，Emst

=?

;while(Vmst包含的頂點少于n

&&

E不空){從E中選一條邊(u,v),u?

Vmst∩v?

V-Vmst,且具有最小代價(cost);令Vmst

=

Vmst∪{v},

Emst

=

Emst∪{(u,

v)};將新選出的邊從E中剔除：E

=E-{(u,v)};}if(Vmst包含的頂點少于n)cout<<"不是最小生成樹"<<endl;40

28

11052514624221830461046126原圖130105254(d)(e)

(f)63(a)130102

52542243(b)10102

512

2514622162123102

52522(c)8016

102

512例子04128105251462422183162120412810525146242218316212H

=

{(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}8104128105251462418316212H

=

{(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}041222810525146242218316212H

=

{(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}8204128105251462418316212H

=

{(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,

t,

f}041222810525146242218316212H

=

{(2,1,16),

(3,6,18),

(4,6,24),(0,1,28)}ed

=

(2,

1,

16)Vmst

=

{t,

f,

t,

t,

t,

t,

f}Vmst

=

{t,

t,

t,

t,

t,

t,

f}830412810525146242218316212H

=

{(1,6,14),

(3,6,18),

(4,6,24),(0,1,28)}ed

=

(1,

6,

14)Vmst

=

{t,

t,

t,

t,

t,

t,

f}Vmst

=

{t,

t,

t,

t,

t,

t,

t}最小生成樹中邊集合里存入的各條邊為：(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14)84Prim算法的實現(xiàn)85#include

"heap.h"template

<class

T,class

E>void

Prim

(Graph<T,

E>&

G,const

T

u0,MinSpanTree<T,

E>&

MST)

{MSTEdgeNode<T,E>ed;//邊結(jié)點輔助單元int

i,

u,

v,count;int

n=G.NumberOfVertices();int

m

=

G.NumberOfEdges();int

u=G.getVertexPos(u0);//頂點數(shù)//邊數(shù)//起始頂點號MinHeap

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

//最小堆boolVmst=new

bool[n];

//最小生成樹頂點集合

for

(i=0;i

<n;i++)

Vmst[i]=false;86//u

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

1;do{//迭代v

=G.getFirstNeighbor(u);while

(v

!=

-1){if(!Vmst[v])

{//檢測u所有鄰接頂點//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);}while

(!H.IsEmpty()

&&

count

<

n)

{87//選堆中具最小權(quán)的邊H.Remove(ed);if

(!Vmst[ed.head])

{MST.Insert(ed);//加入最小生成樹u=ed.head;

Vmst[u]

=true;//u加入生成樹頂點集合count++;break;}}}

while

(count

<

n);};prim算法適用于邊稠密的網(wǎng)絡(luò)。Kruskal算法適合于邊稀疏的情形。注意：當(dāng)各邊有相同權(quán)值時，由于選擇的隨意性，產(chǎn)生的生成樹可能不唯一。88最短路徑(Shortest

Path)89最短路徑問題：如果從圖中某一頂點（稱為源點）另一頂點（稱為終點）的路徑可能不止一條，如

何找到一條路徑使得沿此路徑上各邊上的權(quán)值總

和達(dá)到最小。問題解法邊上權(quán)值非負(fù)情形的單源最短路徑問題—

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

·

(不講)所有頂點之間的最短路徑Floyd算法邊上權(quán)值非負(fù)情形的單源最短路徑問題90問題的提法：給定一個帶權(quán)有向圖D與源點v，求從v到D中其他頂點的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑,Dijkstra提出按路徑長度的遞增次序,

逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。Dijkstra逐步求解的過程源點終點最短路徑

路徑長度v0v1(v0,v1)10v2v3(v0,v3)(v0,v1,v2)(v0,v3,v2)￥,60,5030v4(v0,v4)(v0,v3,v4)

(v0,v3,v2

,v4)100,90,601432100

100502030

106091引入輔助數(shù)組dist。它的每一個分量dist[i]表示當(dāng)前找到的從源點v0

到終點vi

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

。假設(shè)S是已求得的最短路徑的終點的集合，則可證明：下一條最短路徑必然是從v0

出發(fā)，中間只經(jīng)過

S中的頂點便可到達(dá)的那些頂點vx

(vx?

V-S)的路徑中的一條。每次求得一條最短路徑后,其終點vk加入集合S，然后對所有的vi

?

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

Edge[0][j],

j

=

1,2,

…,

n-1;//n為圖中頂點個數(shù)②求出最短路徑的長度：dist[k]?

min

{dist[i]},

i?

V-S

;S?

S∪{k};③修改：dist[i]?

min{dist[i],

dist[k]+Edge[