數(shù)據(jù)結(jié)構(gòu)與算法-圖

7圖2/107主要內(nèi)容圖的基本概念圖的抽象數(shù)據(jù)類型圖的存儲(chǔ)結(jié)構(gòu)圖的周游最短路徑問(wèn)題最小生成樹3/107圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。線性表:

線性結(jié)構(gòu)樹:

層次結(jié)構(gòu)圖:

結(jié)點(diǎn)之間的關(guān)系可以是任意的，即圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。

ABCDE圖的基本概念4/107圖G是由兩個(gè)集合頂點(diǎn)集V(G)和邊集E(G)組成的，記作G=(V(G)，E(G))，簡(jiǎn)稱G=(V，E)。ABCDEABCDEABCDEV(vertex)是頂點(diǎn)的有窮非空集合

E(edge)是兩個(gè)頂點(diǎn)之間的關(guān)系，即邊的有窮集合

圖的定義和基本術(shù)語(yǔ)5/107無(wú)向圖:邊是頂點(diǎn)的無(wú)序?qū)?，即邊沒(méi)有方向性。v1v2v3v5v4V={v1,v2,v3,v4,v5}E={(v1,v2)

,(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}(v1,v2)表示頂點(diǎn)

v1和v2之間的邊，(v1,v2)=(v2,v1)。無(wú)向圖6/107有向圖:其邊是頂點(diǎn)的有序?qū)?，即邊有方向性。v1v2v4v3V={v1,v2,v3,v4}E={<v1,v2>

,<v1,v3>,<v3,v4>,<v4,v1>}通常邊稱為弧，<v1,v2>表示頂點(diǎn)v1到v2的弧。稱v1為弧尾，稱v2為弧頭。<v1,v2>≠<v2,v1>有向圖7/107有時(shí)對(duì)圖的邊或弧賦予相關(guān)的數(shù)值，這種與圖的邊或弧相關(guān)的數(shù)值叫做權(quán)。

ABCDE53821497這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離?？梢员硎緩囊粋€(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的耗費(fèi)。帶權(quán)圖8/107性質(zhì):若用n表示圖中頂點(diǎn)數(shù)目，用e表示邊或弧的數(shù)目，若在圖中不存在頂點(diǎn)到自身的邊或弧，則對(duì)于無(wú)向圖，0≤e≤n(n-1)12對(duì)于有向圖，0≤e≤n(n-1)證明:0≤e

顯然成立對(duì)有向圖來(lái)說(shuō)，每個(gè)頂點(diǎn)至多可發(fā)出n-1條弧，共n個(gè)頂點(diǎn)，故至多有n(n-1)

條弧，即e≤n(n-1)；對(duì)無(wú)向圖來(lái)說(shuō)，由于邊無(wú)方向，則任一兩個(gè)頂點(diǎn)v1和v2，都有(v1,v2)=(v2,v1)，故至多有n(n-1)

條邊；12基本性質(zhì)9/107有

n(n-1)條邊的無(wú)向圖稱為完全圖。

12v1v2v4v3有

n(n-1)條弧的有向圖稱為有向完全圖。

v1v2v3有很少條邊或弧的圖稱為稀疏圖。

反之稱為稠密圖。

完全圖、稀疏圖、稠密圖10/107假設(shè)有兩個(gè)圖G=(V,E)和G’=(V’,E’)，如果V’

V，且E’

E，則稱G’為G的子圖。v1v2v4v3求子圖v1v1v3v1v4v3v1v2v4v3v1v2v4v3子圖11/107v1v2v3v5v4子圖有v1v2v3v5v1v2v5v4v1v2v3v5v4子圖12/107對(duì)于無(wú)向圖

G=(V,E)，如果邊

(v,v’)∈E，則稱頂點(diǎn)

v和

v’互為鄰接點(diǎn)，即

v和

v’

相鄰接。

邊

(v,v’)依附于頂點(diǎn)

v和

v’，或者說(shuō)

(v,v’)

與頂點(diǎn)

v

和

v’

相關(guān)聯(lián)。

對(duì)于有向圖G=(V,E)，如果弧<v,v’>∈E，則稱頂點(diǎn)v鄰接到頂點(diǎn)v’，頂點(diǎn)v’鄰接到頂點(diǎn)v。vv’vv’弧<v,v’>和頂點(diǎn)v,v’相關(guān)聯(lián)。鄰接與關(guān)聯(lián)13/107對(duì)于無(wú)向圖，頂點(diǎn)

v的度是和

v相關(guān)聯(lián)的邊的數(shù)目，記做TD(v)。

v1v2v3v5v4頂點(diǎn)v3的度為3對(duì)于有向圖，頂點(diǎn)

v的度

TD(V)分為兩部分——出度、入度。

以頂點(diǎn)

v為頭的弧的數(shù)目稱為

v的入度，記為ID(v)

；以頂點(diǎn)

v為尾的弧的數(shù)目稱為

v的出度，記為OD(v)；

頂點(diǎn)

v的度為TD(v)=ID(v)+OD(v)。

頂點(diǎn)的度14/107v1v2v4v3頂點(diǎn)v1

的出度為2頂點(diǎn)v1

的入度為1頂點(diǎn)v1

的度為3性質(zhì):對(duì)于一個(gè)圖(無(wú)向圖、有向圖)，如果頂點(diǎn)vi

的度為TD(vi)，那么具有n

個(gè)頂點(diǎn)、e

條邊或弧的圖，必滿足如下關(guān)系e=TD(vi)12∑i=1n無(wú)向圖、有向圖的邊或弧均計(jì)算兩遍。頂點(diǎn)的度15/107圖（無(wú)向圖、有向圖）G中若存在一條有窮非空序列w=v0

e1

v1e2

v2…

ek

vk

，其中vi

和ei

分別為頂點(diǎn)和邊（或弧），則稱w

是從頂點(diǎn)v0

到vk

的一條路徑。頂點(diǎn)v0和vk

分別稱為路徑w

的起點(diǎn)和終點(diǎn)。路徑的長(zhǎng)度是路徑上的邊的數(shù)目。w的長(zhǎng)度為k起點(diǎn)和終點(diǎn)相同的路徑稱為回路(環(huán))。圖的其它術(shù)語(yǔ)v0v1v2vk-1vk...e1e2ek16/107若路徑w的頂點(diǎn)

v0,v1,,vk

，除v0

和vk可以相同之外，其他頂點(diǎn)互不相同，則稱w為簡(jiǎn)單路徑。如果構(gòu)成回路的路徑是簡(jiǎn)單路徑，稱此回路為簡(jiǎn)單回路。不帶回路的圖稱為無(wú)環(huán)圖。不帶回路的有向圖稱為有向無(wú)環(huán)圖?！瓐D的其它術(shù)語(yǔ)v0v1v2vk-1vk...e1e2ekv0v1v2vk-1vk...e1e2ek17/107無(wú)向圖G，如果從頂點(diǎn)

v

到頂點(diǎn)

v’

有路徑，則稱

v

和

v’

是連通的。

如果對(duì)于無(wú)向圖

G中任意兩個(gè)頂點(diǎn)

vi,vj

∈V,vi和

vj

都是連通的，則稱

G是連通圖。

v1v2v3v5v4是否為連通圖連通、連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量18/107連通分量指的是無(wú)向圖中的最大連通子圖。

ABCLHDEFGH非連通圖連通分量為ABCLHDEFGH連通、連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量19/107有向圖G，如果從頂點(diǎn)

v

到頂點(diǎn)

v’

有路徑

或

從頂點(diǎn)

v’

到頂點(diǎn)

v

有路徑，則稱

v

和

v’

是連通的。

在有向圖

G

中，如果對(duì)于每一對(duì)

vi,vj

∈V，vi≠vj

，從

vi到

vj

和

從vj

到

vi都存在路徑，則稱

G是強(qiáng)連通圖。

v1v2v4v3是否為強(qiáng)連通圖連通、連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量20/107有向圖中的最大強(qiáng)連通子圖稱作有向圖的強(qiáng)連通分量。

v1v2v4v3非強(qiáng)連通圖強(qiáng)連通分量v2v1v4v3連通、連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量21/107網(wǎng)絡(luò)、自由樹網(wǎng)絡(luò)帶權(quán)的連通圖。自由樹（freetree）不帶有簡(jiǎn)單回路的無(wú)向圖，它是連通的，并且具有|V|-1條邊。22/107圖的抽象數(shù)據(jù)類型classGraph{//圖的ADTpublic:

int

VerticesNum();//返回圖的頂點(diǎn)個(gè)數(shù)

int

EdgesNum();//返回圖的邊數(shù)

//返回與頂點(diǎn)oneVertex相關(guān)聯(lián)的第一條邊

EdgeFirstEdge(int

oneVertex);

//返回與邊PreEdge有相同關(guān)聯(lián)頂點(diǎn)oneVertex的下一條邊

EdgeNextEdge(Edge

preEdge);23/107圖的抽象數(shù)據(jù)類型（續(xù)）//添加一條邊

bool

setEdge(int

fromVertex,int

toVertex,intweight);//刪一條邊

bool

delEdge(int

fromVertex,int

toVertex);//如果oneEdge是邊則返回TRUE，否則返回FALSE

bool

IsEdge(Edge

oneEdge);//返回邊oneEdge的始點(diǎn)

int

FromVertex(Edge

oneEdge);//返回邊oneEdge的終點(diǎn)

int

ToVertex(Edge

oneEdge);//返回邊oneEdge的權(quán)

int

Weight(Edge

oneEdge); };24/107順序存儲(chǔ)鄰接矩陣鏈?zhǔn)酱鎯?chǔ)鄰接表鄰接多重表如何表達(dá)頂點(diǎn)之間存在的聯(lián)系？多重鏈表，如何設(shè)計(jì)結(jié)點(diǎn)結(jié)構(gòu)？圖的存儲(chǔ)結(jié)構(gòu)25/107習(xí)慣性約定為每一個(gè)頂點(diǎn)設(shè)定一個(gè)序號(hào)，表示“頂點(diǎn)在圖中的位置”。1235426/107設(shè)圖G=(V，E)具有n(n≥1)個(gè)頂點(diǎn)v1,v2,…,vn

和m條邊或弧e1,e2,…,em

，則G的鄰接矩陣是n×n階矩陣，記為A(G)。其每一個(gè)元素aij

定義為:鄰接矩陣存放n個(gè)頂點(diǎn)信息和n2

條邊或弧信息。aij

=01頂點(diǎn)vi與vj

不相鄰接頂點(diǎn)vi與vj

相鄰接v1v2v4v3例有向圖GA(G)=123412340110000000011000鄰接矩陣(adjacencymatrix)27/107v1v2v3v5v4例無(wú)向圖G0101010101010111010001100A(G)=1234512345優(yōu)點(diǎn):1.容易判斷任意兩個(gè)頂點(diǎn)之間是否有邊或弧。2.容易求取各個(gè)頂點(diǎn)的度。鄰接矩陣28/107無(wú)向圖，頂點(diǎn)vi的度是鄰接矩陣中第i

行或第

i列的元素之和。例G1中，v1

的度為2。v1v2v3v5v4例無(wú)向圖G0101010101010111010001100A(G)=1234512345鄰接矩陣29/107v1v2v4v3例有向圖GA(G)=123412340110000000011000有向圖，頂點(diǎn)vi

的出度是鄰接矩陣中第i

行的元素之和。頂點(diǎn)vi的入度是鄰接矩陣中第i

列的元素之和。例v1

的出度為2；入度為1。鄰接矩陣30/107無(wú)向圖的鄰接矩陣都是對(duì)稱矩陣。有向圖的鄰接矩陣一般不對(duì)稱。12341234011000000001100001010101010101110100011001234512345故無(wú)向圖可以采用壓縮存儲(chǔ)方式無(wú)向圖有向圖鄰接矩陣31/107v1v2v3v5v4v65487935651aij

=wij∞頂點(diǎn)vi與vj

相鄰接頂點(diǎn)vi與vj

不相鄰接∞5∞7∞∞∞∞4∞∞∞

8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞A=

123456123456

3∞∞∞1∞帶權(quán)圖(網(wǎng))的鄰接矩陣32/107【代碼7.2】圖的基類classEdge{ //邊類public:

intfrom,to,weight;//from是邊的始點(diǎn),to是終點(diǎn),weight是邊的權(quán)

Edge(){ //缺省構(gòu)造函數(shù)

from=-1;to=-1;weight=0; }

Edge(int

f,int

t,intw){ //給定參數(shù)的構(gòu)造函數(shù)

from=f;to=t;weight=w; }};33/107【代碼7.2】圖的基類classGraph{public:

int

numVertex; //圖中頂點(diǎn)的個(gè)數(shù)

int

numEdge; //圖中邊的條數(shù)

int*Mark; //標(biāo)記圖的頂點(diǎn)是否被訪問(wèn)過(guò)

int*Indegree; //存放圖中頂點(diǎn)的入度

Graph(int

numVert){ //圖的構(gòu)造函數(shù)

numVertex=numVert;

numEdge=0;

Indegree=newint[numVertex]; Mark=newint[numVertex]; for(inti=0;i<numVertex;i++){

Mark[i]=UNVISITED;//標(biāo)志位設(shè)為UNVISITED

Indegree[i]=0; //入度設(shè)為0 } }34/107 ~Graph(){ //析構(gòu)函數(shù)

delete[]Mark; //釋放Mark數(shù)組

delete[]Indegree; //釋放Indegree數(shù)組

}

int

VerticesNum(){ //返回圖中頂點(diǎn)的個(gè)數(shù)

returnnumVertex; }

bool

IsEdge(Edge

oneEdge){//oneEdge是否是邊

if(oneEdge.weight>0&&

oneEdge.weight<INFINITY&&

oneEdge.to>=0) returntrue; elsereturnfalse; }};35/107[代碼7.3]用相鄰矩陣表示圖classGraphm:publicGraph{private:

int**matrix; //指向相鄰矩陣的指針 public:

Graphm(int

numVert):Graph(numVert){ //構(gòu)造函數(shù)

int

i,j;//i,j作為for循環(huán)中的計(jì)數(shù)器

matrix=(int**)newint*[numVertex]; //申請(qǐng)matrix數(shù)組行向量數(shù)組

for(i=0;i<numVertex;i++)//申請(qǐng)matrix數(shù)組行的存儲(chǔ)空間

matrix[i]=newint[numVertex]; for(i=0;i<numVertex;i++) //相鄰矩陣的所有元素都初始化為0 for(j=0;j<numVertex;j++)

matrix[i][j]=0;}36/107EdgeFirstEdge(int

oneVertex){ //返回頂點(diǎn)oneVertex的第一條邊

EdgemyEdge;

myEdge.from=oneVertex; //將頂點(diǎn)oneVertex作為邊的始點(diǎn)

//尋找第一個(gè)使得matrix[oneVertex][i]不為0的i值

for(inti=0;i<numVertex;i++){ if(matrix[oneVertex][i]!=0){

myEdge.to=i;

myEdge.weight=matrix[oneVertex][i]; break; //找到了頂點(diǎn)oneVertex的第一條邊

} } returnmyEdge; }37/107EdgeNextEdge(Edge

preEdge){//返回與邊有相同關(guān)聯(lián)頂點(diǎn)的下一條邊 EdgemyEdge; //myEdge的初始成員變量to為-1

myEdge.from=preEdge.from;//置邊的始點(diǎn)為與上一條邊preEdge相同

if(preEdge.to<numVertex){

//如果preEdge.to+1>=numVertex,那么就不存在下一條邊了

for(inti=preEdge.to+1;i<numVertex;i++){

//尋找下一個(gè)使得matrix[preEdge.from][i]不為0的i值，即下一條邊 if(matrix[preEdge.from][i]!=0){

myEdge.to=i;

myEdge.weight=matrix[preEdge.from][i]; break;//找到下一條邊，跳出循環(huán) } } }returnmyEdge;}38/1077.3.2鄰接表當(dāng)圖中的邊數(shù)較少時(shí)，相鄰矩陣就會(huì)出現(xiàn)大量的零元素，存儲(chǔ)這些零元素將耗費(fèi)大量的存儲(chǔ)空間。對(duì)于稀疏圖，可以采用鄰接表存儲(chǔ)法。鄰接表(adjacencylist)表示法是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，由一個(gè)順序存儲(chǔ)的頂點(diǎn)表和n個(gè)鏈接存儲(chǔ)的邊表組成。頂點(diǎn)表目有兩個(gè)域：頂點(diǎn)數(shù)據(jù)域和指向此頂點(diǎn)邊表指針域邊表把依附于同一個(gè)頂點(diǎn)vi的邊（即相鄰矩陣中同一行的非0元素）組織成一個(gè)單鏈表。邊表中的每一個(gè)表目都代表一條邊，由兩個(gè)主要的域組成：與頂點(diǎn)vi鄰接的另一頂點(diǎn)的序號(hào)指向邊表中下一個(gè)邊表目的指針39/1077.3.2鄰接表

假設(shè)（vi，vj）是無(wú)向圖中的一條邊，在頂點(diǎn)vi的邊表里存儲(chǔ)有邊（vi，vj）對(duì)應(yīng)的邊結(jié)點(diǎn)，在頂點(diǎn)vj的邊表里還需存放（vj，vi）對(duì)應(yīng)的邊結(jié)點(diǎn)。因此，對(duì)于無(wú)向圖，同一條邊在鄰接表中出現(xiàn)兩次。圖7.12無(wú)向圖G1的鄰接表表示需要多少存儲(chǔ)空間？n+2e40/1077.3.2鄰接表圖7.13有向圖G2的鄰接表和逆鄰接表表示41/1077.3.2鄰接表圖7.14帶權(quán)圖G4的鄰接表表示

42/1077.3.2鄰接表若圖中有n個(gè)頂點(diǎn)和e條邊，如果該圖是無(wú)向圖，則需要用到n個(gè)頂點(diǎn)結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)；若是有向圖時(shí)，不考慮逆鄰接表，只需要n個(gè)頂點(diǎn)結(jié)點(diǎn)和e個(gè)邊結(jié)點(diǎn)。當(dāng)邊數(shù)e很小時(shí)，可以節(jié)省大量的存儲(chǔ)空間。邊表中表目順序往往按照頂點(diǎn)編號(hào)從小到大排列。43/107[代碼7.4]用鄰接表存儲(chǔ)圖struct

listUnit{ //鄰接表表目中數(shù)據(jù)部分的結(jié)構(gòu)定義

intvertex;

//邊的終點(diǎn)

intweight; //邊的權(quán)};template<classElem>classLink{

//鏈表元素public: Elemelement; //表目的數(shù)據(jù) Link*next; //表目指針，指向下一個(gè)表目

Link(constElem&elemval,Link*nextval=NULL){//構(gòu)造函數(shù)

element=elemval;

next=nextval;

}

Link(Link*nextval=NULL){ //構(gòu)造函數(shù)

next=nextval;

}};44/107template<classElem>classLList{ //鏈表類public: Link<Elem>*head;

//head保存一個(gè)虛的頭結(jié)點(diǎn)，以方便操作

LList(){ //構(gòu)造函數(shù) head=newLink<Elem>(); }};45/107classGraphl:publicGraph{private:

LList<listUnit>*graList; //保存所有邊表的數(shù)組public:

Graphl(int

numVert):Graph(numVert){ //構(gòu)造函數(shù)

graList=newLList<listUnit>[numVertex];

//為邊表graList數(shù)組申請(qǐng)空間 } EdgeFirstEdge(int

oneVertex){//返回頂點(diǎn)oneVertex的第一條邊 EdgemyEdge;

//myEdge的初始成員變量to為-1

myEdge.from=oneVertex;//將頂點(diǎn)oneVertex作為邊myEdge的始點(diǎn)

Link<listUnit>*temp=graList[oneVertex].head; if(temp->next!=NULL){//頂點(diǎn)oneVertex邊表非空

myEdge.to=temp->next->element.vertex;

//邊表第一個(gè)表目的頂點(diǎn)

myEdge.weight=temp->next->element.weight; }

returnmyEdge;

//如果沒(méi)有找到第一條邊，myEdge.to=-1 }46/107EdgeNextEdge(Edge

preEdge){//返回與邊有相同關(guān)聯(lián)頂點(diǎn)的下一條邊

EdgemyEdge;

//myEdge的初始成員變量to為-1

myEdge.from=preEdge.from;//將邊的始點(diǎn)置為與上一條邊的相同

Link<listUnit>*temp=graList[preEdge.from].head;

//temp指向邊表頭一個(gè)

while(temp->next!=NULL&&

temp->next->element.vertex<=preEdge.to)

temp=temp->next;

//確定邊preEdge的位置

if(temp->next!=NULL){

//邊preEdge的下一條邊存在

myEdge.to=temp->next->element.vertex;

myEdge.weight=temp->next->element.weight;

}

returnmyEdge; }47/107voidsetEdge(int

from,int

to,intweight){ //為圖設(shè)定一條邊

Link<listUnit>*temp=graList[from].head; //temp指向邊表頭一個(gè)

while(temp->next!=NULL&&temp->next->element.vertex<to)

temp=temp->next;

//確定邊(from,to)在邊表中的位置

if(temp->next==NULL){ //邊(from,to)在邊表中不存在

temp->next=newLink<listUnit>; //在邊表最后加入這條新邊

temp->next->element.vertex=to;

temp->next->element.weight=weight;

numEdge++;

Indegree[to]++;

return;

}

if(temp->next->element.vertex==to){ //邊(from,to)在邊表中已存在

temp->next->element.weight=weight;

//只需要改變邊的權(quán)值

return;

}

if(temp->next->element.vertex>to){ //邊(from,to)在邊表中不存在

Link<listUnit>*other=temp->next;

temp->next=newLink<listUnit>;

temp->next->element.vertex=to;

temp->next->element.weight=weight;

temp->next->next=other; //連接邊表中其后的其他邊

numEdge++;

Indegree[to]++;

return;

}}48/107voiddelEdge(int

from,intto){ //刪掉圖的一條邊

Link<listUnit>*temp=graList[from].head;//temp指向邊表頭一個(gè)

while(temp->next!=NULL&&temp->next->element.vertex<to)

temp=temp->next; //確定邊(from,to)在邊表中的位置

if(temp->next==NULL)

return; //邊(from,to)在邊表中不存在，直接返回

if(temp->next->element.vertex>to)

return; //邊(from,to)在邊表中不存在，直接返回

if(temp->next->element.vertex==to){//邊(from,to)在邊表中存在

Link<listUnit>*other=temp->next->next;

deletetemp->next; //從邊表中將其刪掉

temp->next=other; //其他表目掛接

numEdge--; //邊數(shù)減1

Indegree[to]--; //終點(diǎn)的入度減1

return;

}}};49/1077.3.3十字鏈表十字鏈表（OrthogonalList）是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，可以看成是鄰接表和逆鄰接表的結(jié)合表中對(duì)應(yīng)于有向圖的每一條弧有一個(gè)表目，共有5個(gè)域：頭(headvex)和尾(tailvex)分別表示弧頭（終點(diǎn)）和弧尾（始點(diǎn)）頂點(diǎn)序號(hào)；tailnextarc鏈接指針指向下一條頂點(diǎn)以tailvex為弧尾的??；headnextarc指針指向下一條以頂點(diǎn)headvex為弧頭的??；此外還有一個(gè)表示弧權(quán)值等信息的info域頂點(diǎn)表目由3個(gè)域組成：data域存放頂點(diǎn)的相關(guān)信息；firstinarc鏈接指針指向第一條以該頂點(diǎn)為終點(diǎn)的??；firstoutarc鏈接指針指向第一條以該頂點(diǎn)為始點(diǎn)的弧。所有的頂點(diǎn)也可以放在順序存儲(chǔ)結(jié)構(gòu)中50/107十字鏈表圖7.15有向圖G2的十字鏈表示例51/107十字鏈表在十字鏈表中，很容易找到以vi為始點(diǎn)和終點(diǎn)的弧。從頂點(diǎn)結(jié)點(diǎn)vi的firstoutarc出發(fā)，由tailnextarc域鏈接起來(lái)的鏈表，正好是原來(lái)的鄰接表結(jié)構(gòu)。統(tǒng)計(jì)這個(gè)鏈表中的表目個(gè)數(shù)，可以得到頂點(diǎn)vi的出度。如果從頂點(diǎn)結(jié)點(diǎn)vi的firstinarc出發(fā)，由headnextarc域鏈接起來(lái)的鏈表，恰好是原來(lái)的逆鄰接表結(jié)構(gòu)。統(tǒng)計(jì)這個(gè)鏈表中的表目個(gè)數(shù)，可以求出頂點(diǎn)vi的入度。52/1077.4圖的周游圖的周游（graphtraversal）給出一個(gè)圖G和其中任意一個(gè)頂點(diǎn)V0，從V0出發(fā)系統(tǒng)地訪問(wèn)G中所有的頂點(diǎn)，每個(gè)頂點(diǎn)訪問(wèn)一次，這叫做圖的周游。深度優(yōu)先搜索廣度優(yōu)先搜索53/1077.4圖的周游7.4.1深度優(yōu)先周游7.4.2廣度優(yōu)先周游7.4.3拓?fù)渑判?4/1077.4.1深度優(yōu)先搜索深度優(yōu)先搜索（depth-firstsearch，簡(jiǎn)稱DFS）基本思想訪問(wèn)一個(gè)頂點(diǎn)V，然后訪問(wèn)該頂點(diǎn)鄰接到的未被訪問(wèn)過(guò)的頂點(diǎn)V’，再?gòu)腣’出發(fā)遞歸地按照深度優(yōu)先的方式周游，當(dāng)遇到一個(gè)所有鄰接于它的頂點(diǎn)都被訪問(wèn)過(guò)了的頂點(diǎn)U時(shí)，則回到已訪問(wèn)頂點(diǎn)序列中最后一個(gè)擁有未被訪問(wèn)的相鄰頂點(diǎn)的頂點(diǎn)W，再?gòu)腤出發(fā)遞歸地按照深度優(yōu)先的方式周游，最后，當(dāng)任何已被訪問(wèn)過(guò)的頂點(diǎn)都沒(méi)有未被訪問(wèn)的相鄰頂點(diǎn)時(shí)，則周游結(jié)束。55/107深度優(yōu)先搜索是類似于樹的一種先序遍歷v1v2v3v5v4v6v7v8圖可分為三部分:基結(jié)點(diǎn)第一個(gè)鄰接結(jié)點(diǎn)導(dǎo)出的子圖其它鄰接頂點(diǎn)導(dǎo)出的子圖深度優(yōu)先搜索順序:v1v2v4v8v5v3v6v77.4.1深度優(yōu)先搜索深度優(yōu)先搜索樹（depth-firstsearchtree）56/1077.4.1深度優(yōu)先搜索（續(xù)）深度優(yōu)先搜索的順序是a，b，c，f，d，e，g57/1077.4.1深度優(yōu)先周游【算法7.5】

圖的深度優(yōu)先周游(DFS)算法voidDFS(Graph&G,intv){ //深度優(yōu)先搜索的遞規(guī)實(shí)現(xiàn)

G.Mark[v]=VISITED; //將標(biāo)記位設(shè)置為VISITED

Visit(G,v); //訪問(wèn)頂點(diǎn)v for(Edgee=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e))if(G.Mark[G.ToVertex(e)]==UNVISITED)

DFS(G,G.ToVertex(e));}58/1077.4.1深度優(yōu)先周游周游圖的過(guò)程實(shí)質(zhì)上是搜索每個(gè)頂點(diǎn)的鄰接點(diǎn)的過(guò)程，時(shí)間主要耗費(fèi)在從該頂點(diǎn)出發(fā)搜索它的所有鄰接點(diǎn)上分析上述算法，對(duì)于具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖或有向圖，深度優(yōu)先周游算法對(duì)圖中每頂點(diǎn)至多調(diào)用一次DFS函數(shù)用相鄰矩陣表示圖時(shí)，共需檢查n2個(gè)矩陣元素，所需時(shí)間為O(n2)用鄰接表表示圖時(shí)，找鄰接點(diǎn)需將鄰接表中所有邊結(jié)點(diǎn)檢查一遍，需要時(shí)間O(e)，對(duì)應(yīng)的深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為O(n+e)59/1077.4.2廣度優(yōu)先搜索廣度優(yōu)先搜索（breadth-firstsearch，簡(jiǎn)稱BFS）它的基本思想是訪問(wèn)頂點(diǎn)V0，然后訪問(wèn)V0鄰接到的所有未被訪問(wèn)過(guò)的頂點(diǎn)V01，V02，…V0i，再依次訪問(wèn)V01，V02，…V0i鄰接到的所有未被訪問(wèn)的頂點(diǎn)，如此進(jìn)行下去，直到訪問(wèn)遍所有的頂點(diǎn)。60/107深度優(yōu)先搜索類似于樹的層次遍歷，廣度優(yōu)先搜索順序:

v1v2v3v4v5v6v7v8v1v2v3v5v4v6v7v8只有父輩結(jié)點(diǎn)被訪問(wèn)后才會(huì)訪問(wèn)子孫結(jié)點(diǎn)！把圖人為的分層，按層遍歷。廣度優(yōu)先搜索廣度優(yōu)先搜索樹（breadth-firstsearchtree）61/107v1v2v3v5v4v6v7v8廣度優(yōu)先搜索順序:v1v2v3v4v6v5v7v8v1v2v3v4v5v6v7v8廣度優(yōu)先搜索62/1077.4.2廣度優(yōu)先搜索（續(xù)）廣度優(yōu)先搜索的順序是a，b，d，e，f，c，g63/1077.4.2廣度優(yōu)先搜索（續(xù)）//廣度優(yōu)先搜索算法的實(shí)現(xiàn)voidBFS(Graph&G,intV){

//初始化廣度優(yōu)先周游要用到的隊(duì)列

usingstd::queue;

queue<int>Q;//訪問(wèn)頂點(diǎn)V，并標(biāo)記其標(biāo)志位，V入隊(duì)

G.Mark[V]=VISITED;

Visit(G,V);

Q.push(V);

while(!Q.empty())//如果隊(duì)列仍然有元素64/1077.4.2廣度優(yōu)先搜索（續(xù)）{

intV=Q.front();//頂部元素

Q.pop();//出隊(duì)

//將與該點(diǎn)相鄰的每一個(gè)未訪問(wèn)結(jié)點(diǎn)都入隊(duì)

for(Edgee=G.FirstEdge(V);

G.IsEdge(e);e=G.NextEdge(e)){

if(G.Mark[G.ToVertex(e)]==UNVISITED)65/1077.4.2廣度優(yōu)先搜索（續(xù)）

{

G.Mark[G.ToVertex(e)]=VISITED;

Visit(G,G.ToVertex(e));

//入隊(duì)

Q.push(G.ToVertex(e));} }}}66/1077.4.2廣度優(yōu)先搜索（續(xù)）廣度優(yōu)先搜索算法的時(shí)間復(fù)雜度與深度優(yōu)先搜索算法的時(shí)間復(fù)雜度相同67/107練習(xí)對(duì)于入圖所示的有向圖，試寫出：（1）從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；（2）從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；1234568/1077.4.3拓?fù)渑判蛞粋€(gè)無(wú)環(huán)的有向圖稱為有向無(wú)環(huán)圖(directedacyclicgraph，簡(jiǎn)稱DAG)將一個(gè)有向無(wú)環(huán)圖中所有頂點(diǎn)在不違反先決條件關(guān)系的前提下排成線性序列的過(guò)程稱為拓?fù)渑判?topologicalsorting)拓?fù)渑判蚩梢越鉀Q先決條件問(wèn)題，即以某種線性順序來(lái)組織多項(xiàng)任務(wù)，以便能夠在滿足先決條件的情況下逐個(gè)完成各項(xiàng)任務(wù)69/1077.4.3拓?fù)渑判蛲負(fù)湫蛄杏邢驘o(wú)環(huán)圖常用來(lái)描述一個(gè)過(guò)程或一個(gè)系統(tǒng)的進(jìn)行過(guò)程。對(duì)于有向無(wú)環(huán)圖G=<V，E>，如果頂點(diǎn)序列滿足：如果有向無(wú)環(huán)圖G中存在頂點(diǎn)vi到vj的一條路徑，那么在序列中頂點(diǎn)vi必在頂點(diǎn)vj之前，頂點(diǎn)集合V的這種線性序列稱作一個(gè)拓?fù)湫蛄?topologicalorder)70/1077.4.3拓?fù)渑判颍ɡm(xù)）課程編號(hào)課程名稱先決條件C1C2C3C4C5程序語(yǔ)言基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)微機(jī)原理編譯原理C6操作系統(tǒng)C1C1,C2C3C3,C4表示課程之間優(yōu)先關(guān)系的有向圖C1C2C3C5C4C6拓?fù)渑判蚩梢詾?C1C2C3C5C4C6C4C1C2C3C5C671/1077.4.3拓?fù)渑判颍ɡm(xù)）任何無(wú)環(huán)有向圖，其頂點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣?，其拓?fù)渑判虻姆椒ㄊ牵海?）從圖中選擇一個(gè)入度為0的頂點(diǎn)且輸出之。（2）從圖中刪掉此頂點(diǎn)及其所有的出邊。（3）回到第（1）步繼續(xù)執(zhí)行。72/1077.4.3拓?fù)渑判虿粩嘀貜?fù)上述兩個(gè)步驟，會(huì)出現(xiàn)兩種情形：要么有向圖中頂點(diǎn)全部被輸出，要么當(dāng)前圖中不存在沒(méi)有前驅(qū)的頂點(diǎn)。當(dāng)圖中的頂點(diǎn)全部輸出時(shí)，就完成了有向無(wú)環(huán)圖的拓?fù)渑判?；?dāng)圖中還有頂點(diǎn)沒(méi)有輸出時(shí)，說(shuō)明有向圖中含有環(huán)?？梢?jiàn)拓?fù)渑判蚩梢詸z查有向圖是否存在環(huán)。73/107例，v1v2v4v3v6v5拓?fù)渑判騰1v6v4v3v2v574/107v1v2v4v3v6v5例，拓?fù)渑判騰1v3v2存在環(huán)75/1077.4.3拓?fù)渑判颍ɡm(xù)）//隊(duì)列方式實(shí)現(xiàn)的拓?fù)渑判騰oidTopsortbyQueue(Graph&G){

for(inti=0;i<G.VerticesNum();i++)

G.Mark[i]=UNVISITED;//初始化標(biāo)記數(shù)組

usingstd::queue;

queue<int>Q;//初始化隊(duì)列

for(i=0;i<G.VerticesNum();i++){

if(G.Indegree[i]==0)

Q.push(i);//圖中入度為0的頂點(diǎn)入隊(duì)

}

while(!Q.empty()){//如果隊(duì)列中還有圖的頂點(diǎn)

76/1077.4.3拓?fù)渑判颍ɡm(xù)）

intV=Q.front();//頂部元素

Q.pop();//一個(gè)頂點(diǎn)出隊(duì)

Visit(G,V);//訪問(wèn)該頂點(diǎn)

G.Mark[V]=VISITED; //邊e的終點(diǎn)的入度值減1

for(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e)){

G.Indegree[G.ToVertex(e)]--;

if(G.Indegree[G.ToVertex(e)]==0)

Q.push(G.ToVertex(e));//入度為0的頂點(diǎn)入隊(duì)

}}77/1077.4.3拓?fù)渑判颍ɡm(xù)）

for(i=0;i<G.VerticesNum();i++){

if(G.Mark[i]==UNVISITED){ Print(“圖有環(huán)”);//圖有環(huán)

break;}}}78/1077.4.3拓?fù)渑判驅(qū)τ谟衝個(gè)頂點(diǎn)和e條邊的圖，若其存儲(chǔ)結(jié)構(gòu)用鄰接表表示，實(shí)現(xiàn)拓?fù)渑判蜷_(kāi)始時(shí)建立入度為0的頂點(diǎn)隊(duì)列需要檢查所有頂點(diǎn)一次，需要時(shí)間O(n)，然后排序中每個(gè)頂點(diǎn)輸出一次，更新頂點(diǎn)的入度需要檢查每條邊總計(jì)e次，故執(zhí)行時(shí)間為O(n+e)。79/1077.5最短路徑7.5.1單源最短路徑7.5.2每對(duì)頂點(diǎn)之間的最短路徑80/1077.5.1單源最短路徑給定一個(gè)帶權(quán)圖G=<V，E>，其中每條邊（vi，vj）上的權(quán)W[vi，vj]是一個(gè)非負(fù)實(shí)數(shù)。另外，給定V中的一個(gè)頂點(diǎn)s充當(dāng)源點(diǎn)?，F(xiàn)在要計(jì)算從源點(diǎn)s到所有其他各頂點(diǎn)的最短路徑，這個(gè)問(wèn)題通常稱為單源最短路徑(single-sourceshortestpaths)問(wèn)題。圖7.19單源最短路徑的示例81/1077.5.1單源最短路徑解決單源最短路徑問(wèn)題的一個(gè)常用算法是Dijkstra算法，它是由E.W.Dijkstra提出的一種按路徑長(zhǎng)度遞增的次序產(chǎn)生到各頂點(diǎn)最短路徑的貪心算法。E.W.Dijkstra[Dijkstra中的j不發(fā)音,

d??kstra]：1930年5月11日出身于theNetherlandsRotterdam.1972年獲得圖靈獎(jiǎng)（對(duì)開(kāi)發(fā)ALGOL做出了重要貢獻(xiàn)）提出不要使用goto語(yǔ)句去世于2002年8月6日于Nuenen,theNetherlands.82/107EDSGERWYBEDIJKSTRA

"ComputerScienceisnomoreaboutcomputersthanastronomyisabouttelescopes."

83/107Dijkstra算法基本思想把圖的頂點(diǎn)集合化分成兩個(gè)集合S和V-S。第一個(gè)集合S表示最短距離已經(jīng)確定的頂點(diǎn)集，即一個(gè)頂點(diǎn)如果屬于集合S當(dāng)且僅當(dāng)從源點(diǎn)s到該頂點(diǎn)的最短路徑已知其余的頂點(diǎn)放在另一個(gè)集合V-S中。初始時(shí)，集合S只包含源點(diǎn)，即S={s}，這時(shí)只有源點(diǎn)到自己的最短距離是已知的。設(shè)v是V中的某個(gè)頂點(diǎn)，把從源點(diǎn)s到頂點(diǎn)v且中間只經(jīng)過(guò)集合S中頂點(diǎn)的路徑稱為從源點(diǎn)到v的特殊路徑，并用數(shù)組D來(lái)記錄當(dāng)前所找到的從源點(diǎn)s到每個(gè)頂點(diǎn)的最短特殊路徑長(zhǎng)度從尚未確定最短路徑長(zhǎng)度的集合V-S中取出一個(gè)最短特殊路徑長(zhǎng)度最小的頂點(diǎn)u，將u加入集合S，同時(shí)修改數(shù)組D中由s可達(dá)的最短路徑長(zhǎng)度84/107Dijkstra算法基本步驟D的初始狀態(tài)為：如果從源點(diǎn)s到頂點(diǎn)v有弧則D[v]記為弧的權(quán)值；否則將D[v]置為無(wú)窮大。每次從尚未確定最短路徑長(zhǎng)度的集合V-S中取出一個(gè)最短特殊路徑長(zhǎng)度最小的頂點(diǎn)u，將u加入集合S，同時(shí)修改數(shù)組D中由s可達(dá)的最短路徑長(zhǎng)度：若加進(jìn)u做中間頂點(diǎn)，使得vi的最短特殊路徑長(zhǎng)度變短，則修改vi的距離值（即當(dāng)D[u]+W[u,vi]<D[vi]時(shí)，令D[vi]=D[u]+W[u,vi]）。然后重復(fù)上述操作，一旦S包含了所有V中的頂點(diǎn)，D中各頂點(diǎn)的距離值就記錄了從源點(diǎn)s到該頂點(diǎn)的最短路徑長(zhǎng)度。85/107例，v5v0v1v4v3601005v21030201050帶權(quán)鄰接矩陣∞∞10

∞

30100012345∞∞5

∞∞∞∞∞∞

50∞∞∞∞∞

∞∞10∞∞∞

20∞60∞∞∞

∞∞∞012345{v2}∞10∞30100v0v2v210∞6030100v0v4v430{v2,v4}∞50

90v0v4v3v350{v2,v4,v3}∞

60v0v4v3v5v560{v2,v4,v3,v5}∞

v1∞v1v2v3v4v5最短路徑新頂點(diǎn)S頂點(diǎn)路徑長(zhǎng)度每次修改都用的是最新加入集合S的頂點(diǎn)86/107推導(dǎo)最短路徑距離數(shù)組中還可以設(shè)立一個(gè)域來(lái)記錄從源點(diǎn)到頂點(diǎn)v的最短路徑上v前面經(jīng)過(guò)的一個(gè)頂點(diǎn)，這樣就可以推導(dǎo)出最短路徑。初始時(shí)，對(duì)所有的v≠s，均設(shè)置其前一個(gè)頂點(diǎn)為s在Dijkstra算法更新最短路徑長(zhǎng)度時(shí)，只要D[u]+W[u,v]<D[v]，就設(shè)置v的前一個(gè)頂點(diǎn)為u，否則不做修改。當(dāng)Dijkstra算法終止時(shí)就可以找到源點(diǎn)s到頂點(diǎn)v的最短路徑上每個(gè)頂點(diǎn)的前一個(gè)頂點(diǎn)，從而找到源點(diǎn)s到頂點(diǎn)v的最短路徑。87/107迭代步數(shù)sv0v1v2v3v4初始狀態(tài){v0}Length:0pre:0length:10pre:0length:∞pre:0length:30pre:0length:100pre:01{v0,v1}Length:0pre:0length:10pre:0length:60pre:1length:30pre:0length:100pre:02{v0,v1,v3}Length:0pre:0length:10pre:0length:50pre:3length:30pre:0length:90pre:33{v0,v1,v3,v2}length:0pre:0length:10pre:0length:50pre:3length:30pre:0length:60pre:24{v0,v1,v3,v2,v4}length:0pre:0length:10pre:0length:50pre:3length:30pre:0length:60pre:2Pre記錄從源點(diǎn)到頂點(diǎn)v的最短路徑上v前面經(jīng)過(guò)的一個(gè)頂點(diǎn)88/107單源最短路徑【代碼7.8】Dijkstra算法

classDist{ //Dist類，Dijkstra和Floyd算法用于保存最短路徑信息public:

intindex; //頂點(diǎn)的索引值，僅Dijkstra算法用到

intlength; //當(dāng)前最短路徑長(zhǎng)度

intpre; //路徑最后經(jīng)過(guò)的頂點(diǎn)};89/107單源最短路徑//Dijkstra算法voidDijkstra(Graph&G,ints,Dist*&D){D=newDist[G.VerticesNum()];//初始化Mark數(shù)組、D數(shù)組

for(inti=0;i<G.VerticesNum();i++){

G.Mark[i]=UNVISITED;

D[i].index=i;

D[i].length=INFINITY;

D[i].pre=s;}

D[s].length=0;//源點(diǎn)到自身的路徑長(zhǎng)度設(shè)置為0

MinHeap<Dist>H(G.EdgesNum());//最小堆用于找出最短路徑

H.insert(D[s]);90/107單源最短路徑

for(i=0;i<G.VerticesNum();i++){

boolFOUND=falseDistd;

while(!H.isEmpty){d=H.removeMin()//獲得到s路徑長(zhǎng)度最小的頂點(diǎn)

if(G.Mark[d.index]==UNVISITED){//如果未訪問(wèn)過(guò)則跳出循環(huán)

FOUND=true;break;}}if(!FOUND)//若沒(méi)有符合條件的最短路徑則跳出本次循環(huán)

break;

intv=d.index;

G.Mark[v]=VISITED; //將該頂點(diǎn)的標(biāo)記位設(shè)置為VISITED

//加入v以后需要刷新D中v的鄰接點(diǎn)的最短路徑長(zhǎng)度

for(Edgee=G.FirstEdge(v);

G.IsEdge(e);e=G.NextEdge(e)){91/107單源最短路徑

if(D[G.ToVertex(e)].length>(D[v].length+G.Weight(e))){

D[G.ToVertex(e)].length=D[v].length+G.Weight(e);

D[G.ToVertex(e)].pre=v;H.Insert(D[G.ToVertex(e)]);}}}92/107算法復(fù)雜度對(duì)于n個(gè)頂點(diǎn)e條邊的圖，圖中的任何一條邊都可能在最短路徑中出現(xiàn)，因此最短路徑算法對(duì)每條邊至少都要檢查一次代碼7.8采用最小堆來(lái)選擇權(quán)值最小的邊，那么每次改變最短特殊路徑長(zhǎng)度時(shí)需要對(duì)堆進(jìn)行一次重排，此時(shí)的時(shí)間復(fù)雜度為O((n+e)loge)，適合于稀疏圖如果像算法7.10介紹的Prim算法那樣，通過(guò)直接比較D數(shù)組元素，確定代價(jià)最小的邊就需要總時(shí)間O(n2)；取出最短特殊路徑長(zhǎng)度最小的頂點(diǎn)后，修改最短特殊路徑長(zhǎng)度共需要時(shí)間O(e)，因此共需要花費(fèi)O(n2)的時(shí)間，這種方法適合于稠密圖93/107算法正確性這種算法為什么得到的就是最短路徑呢？事實(shí)上，如果存在一條從源點(diǎn)到u且長(zhǎng)度比D[u]更短的路徑，假設(shè)這條路徑經(jīng)過(guò)第二個(gè)集合的某些頂點(diǎn)（不妨設(shè)為x）才到達(dá)u。在這條路徑上分別用d(s，x)，d(x，u)和d(s，u)表示源點(diǎn)s到頂點(diǎn)x、頂點(diǎn)x到頂點(diǎn)u和源點(diǎn)s到頂點(diǎn)u的距離，那么有d(s，u)=d(s，x)+d(x，u)<D[u]，且D[x]≤d(s，x)。由邊的權(quán)值的非負(fù)性，推得D[x]<D[u]。這與u是第二個(gè)集合中距離值最小的頂點(diǎn)矛盾，所以每次加入第一個(gè)集合的u的距離值就是從s到u的最短路徑長(zhǎng)度。94/107練習(xí)以下圖為例，按Dijkstra算法計(jì)算得到的從頂點(diǎn)A到其他各個(gè)頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度。A

B

C

D

E1018

5522295/1077.5.2每對(duì)頂點(diǎn)之間的最短路徑找出從任意頂點(diǎn)vi到頂點(diǎn)vj的最短路徑，這個(gè)問(wèn)題通常稱為帶權(quán)圖的所有頂點(diǎn)對(duì)之間的最短路徑(all-pairsshortestpaths)問(wèn)題。解決這一問(wèn)題可以每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次，這樣就可以求得所有的頂點(diǎn)對(duì)之間的最短路徑及其最短路徑長(zhǎng)度，其時(shí)間復(fù)雜度為O(n3)。96/1077.5.2每對(duì)頂點(diǎn)之間的最短路徑Floyd算法是典型的動(dòng)態(tài)規(guī)劃法，自底向上分別求解子問(wèn)題的解，然后由這些子問(wèn)題的解得到原問(wèn)題的解。這個(gè)算法的時(shí)間復(fù)雜度也是O(n3)，但形式上比較簡(jiǎn)單。RobertW.Floyd:1936年6月8日生于紐約，“自學(xué)成才”斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授1978年圖靈獎(jiǎng)獲得者97/107Floyd算法Floyd算法算法思想：假設(shè)用相鄰矩陣adj表示圖Floyd算法遞歸地產(chǎn)生一個(gè)矩陣序列adj(0)，adj(1)，…，adj(k)

，…，adj(n)adj(k)[i，j]等于從頂點(diǎn)Vi到頂點(diǎn)Vj中間頂點(diǎn)序號(hào)不大于k的最短路徑長(zhǎng)度

98/107Floyd算法假設(shè)已求得矩陣adj(k-1)，那么從頂點(diǎn)Vi到頂點(diǎn)Vj中間頂點(diǎn)的序號(hào)不大于k的最短路徑有兩種情況：一種是中間不經(jīng)過(guò)頂點(diǎn)Vk，那么就有

adj(k)[i，j]=adj(k-1)[i，j]另一種是中間經(jīng)過(guò)頂點(diǎn)Vk，那么adj(k)[i，j]<adj(k-1)[i，j]，且adj(k)[i，j]=adj(k-1)[i，k]+adj(k-1)[k，j]ViVjVkShortestPathusingintermediatevertices{V1,...Vk-1}Shortestpathusingintermediatevertices

{V1,...Vk

}99/107每對(duì)頂點(diǎn)間的最短路徑100/107每對(duì)頂點(diǎn)間的最短路徑//Floyd算法voidFloyd(Graph&G,Dist**&D){

int

i,j,v;//i,j,v作為計(jì)數(shù)器

D=new Dist*[G.VerticesNum()];

for(i=0;;i<G.VerticesNum();i++){

D[i]=newDist[G.VerticesNum()];} //初始化D數(shù)組

for(i=0;i<G.VerticesNum();i++)

for(j=0;j<G.VerticesNum();j++)101/107每對(duì)頂點(diǎn)間的最短路徑

if(i==j){

D[i][j].length=0;

D[i][j].pre=i;}else{

D[i][j]=INFINITY;

D[i][j].pre=-1;}

for(v=0;v<G.VerticesNum();v++)

for(Edgee=G.FirstEdge(v);

G.IsEdge(e);e=G.NextEdge(e)){

D[v][G.ToVertex(e)].length=G.Weight(e);

D[v][G.ToVertex(e)].pre=v;}102/107每對(duì)頂點(diǎn)間的最短路徑//如果兩個(gè)頂點(diǎn)間的最短路徑經(jīng)過(guò)頂點(diǎn)v，則有//D[i][j].length>(D[i][v].length+D[v][j].length

for(v=0;v<G.VerticesNum();v++)

for(i=0;i<G.VerticesNum();i++)

for(j=0;j<G.VerticesNum();j++)

if(D[i][j].length>(D[i][v].length

+D[v][j].length)){

D[i][j].length=D[i][v].length

+D[v][j].length;

D[i][j].pre=D[v][j].pre;}}103/107每對(duì)頂點(diǎn)間的最短路徑

注：其中Dist類型與Dijkstra算法用到的Dist類型一致。因?yàn)镕loyd算法的時(shí)間復(fù)雜度主要在于三重for循環(huán)，所以很明顯，其復(fù)雜度是O(n×n×n).104/1077.6最小生成樹最小生成樹的概念連通圖的最小生成樹生成樹應(yīng)用舉例最小生成樹的構(gòu)造算法Prim算法Kruskal算法105/107生成樹的概念連通圖的生成樹復(fù)習(xí)：圖的所有頂點(diǎn)加上周游過(guò)程中經(jīng)過(guò)的邊所構(gòu)成的子圖稱作圖的生成樹一般說(shuō)，一個(gè)連通無(wú)向圖的生成樹不一定是唯一的（除非這個(gè)圖本身就是樹）對(duì)于n個(gè)結(jié)點(diǎn)的圖，其生成樹中必定有n-1條邊106/107性質(zhì):一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有且僅有n-1條邊。1.如果一棵生成樹有n個(gè)頂點(diǎn)和小于n-1條邊，則為非連通圖。2.如果一棵支撐樹有n個(gè)頂點(diǎn)和多于n-1條邊，則一定有環(huán)。構(gòu)成一棵n頂點(diǎn)支撐樹需要n-1條邊，少于n