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

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

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

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

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

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

E(edge)是兩個頂點之間的關系，即邊的有窮集合

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

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

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

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

ABCDE53821497這些權(quán)可以表示從一個頂點到另一個頂點的距離。可以表示從一個頂點到另一個頂點的耗費。帶權(quán)圖8/107性質(zhì):若用n表示圖中頂點數(shù)目，用e表示邊或弧的數(shù)目，若在圖中不存在頂點到自身的邊或弧，則對于無向圖，0≤e≤n(n-1)12對于有向圖，0≤e≤n(n-1)證明:0≤e

顯然成立對有向圖來說，每個頂點至多可發(fā)出n-1條弧，共n個頂點，故至多有n(n-1)

條弧，即e≤n(n-1)；對無向圖來說，由于邊無方向，則任一兩個頂點v1和v2，都有(v1,v2)=(v2,v1)，故至多有n(n-1)

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

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

12v1v2v4v3有

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

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

反之稱為稠密圖。

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

V，且E’

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

G=(V,E)，如果邊

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

v和

v’互為鄰接點，即

v和

v’

相鄰接。

邊

(v,v’)依附于頂點

v和

v’，或者說

(v,v’)

與頂點

v

和

v’

相關聯(lián)。

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

v的度是和

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

v1v2v3v5v4頂點v3的度為3對于有向圖，頂點

v的度

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

以頂點

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

v的入度，記為ID(v)

；以頂點

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

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

頂點

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

頂點的度14/107v1v2v4v3頂點v1

的出度為2頂點v1

的入度為1頂點v1

的度為3性質(zhì):對于一個圖(無向圖、有向圖)，如果頂點vi

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

個頂點、e

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

e1

v1e2

v2…

ek

vk

，其中vi

和ei

分別為頂點和邊（或弧），則稱w

是從頂點v0

到vk

的一條路徑。頂點v0和vk

分別稱為路徑w

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

v0,v1,,vk

，除v0

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

v

到頂點

v’

有路徑，則稱

v

和

v’

是連通的。

如果對于無向圖

G中任意兩個頂點

vi,vj

∈V,vi和

vj

都是連通的，則稱

G是連通圖。

v1v2v3v5v4是否為連通圖連通、連通圖、連通分量、強連通圖、強連通分量18/107連通分量指的是無向圖中的最大連通子圖。

ABCLHDEFGH非連通圖連通分量為ABCLHDEFGH連通、連通圖、連通分量、強連通圖、強連通分量19/107有向圖G，如果從頂點

v

到頂點

v’

有路徑

或

從頂點

v’

到頂點

v

有路徑，則稱

v

和

v’

是連通的。

在有向圖

G

中，如果對于每一對

vi,vj

∈V，vi≠vj

，從

vi到

vj

和

從vj

到

vi都存在路徑，則稱

G是強連通圖。

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

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

int

VerticesNum();//返回圖的頂點個數(shù)

int

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

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

EdgeFirstEdge(int

oneVertex);

//返回與邊PreEdge有相同關聯(liá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的始點

int

FromVertex(Edge

oneEdge);//返回邊oneEdge的終點

int

ToVertex(Edge

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

int

Weight(Edge

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

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

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

定義為:鄰接矩陣存放n個頂點信息和n2

條邊或弧信息。aij

=01頂點vi與vj

不相鄰接頂點vi與vj

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

行或第

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

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

的出度是鄰接矩陣中第i

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

列的元素之和。例v1

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

=wij∞頂點vi與vj

相鄰接頂點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是邊的始點,to是終點,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; //圖中頂點的個數(shù)

int

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

int*Mark; //標記圖的頂點是否被訪問過

int*Indegree; //存放圖中頂點的入度

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;//標志位設為UNVISITED

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

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

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

}

int

VerticesNum(){ //返回圖中頂點的個數(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)中的計數(shù)器

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

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

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){ //返回頂點oneVertex的第一條邊

EdgemyEdge;

myEdge.from=oneVertex; //將頂點oneVertex作為邊的始點

//尋找第一個使得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; //找到了頂點oneVertex的第一條邊

} } returnmyEdge; }37/107EdgeNextEdge(Edge

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

myEdge.from=preEdge.from;//置邊的始點為與上一條邊preEdge相同

if(preEdge.to<numVertex){

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

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

//尋找下一個使得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鄰接表當圖中的邊數(shù)較少時，相鄰矩陣就會出現(xiàn)大量的零元素，存儲這些零元素將耗費大量的存儲空間。對于稀疏圖，可以采用鄰接表存儲法。鄰接表(adjacencylist)表示法是一種鏈式存儲結(jié)構(gòu)，由一個順序存儲的頂點表和n個鏈接存儲的邊表組成。頂點表目有兩個域：頂點數(shù)據(jù)域和指向此頂點邊表指針域邊表把依附于同一個頂點vi的邊（即相鄰矩陣中同一行的非0元素）組織成一個單鏈表。邊表中的每一個表目都代表一條邊，由兩個主要的域組成：與頂點vi鄰接的另一頂點的序號指向邊表中下一個邊表目的指針39/1077.3.2鄰接表

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

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

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

intvertex;

//邊的終點

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

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

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保存一個虛的頭結(jié)點，以方便操作

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ù)組申請空間 } EdgeFirstEdge(int

oneVertex){//返回頂點oneVertex的第一條邊 EdgemyEdge;

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

myEdge.from=oneVertex;//將頂點oneVertex作為邊myEdge的始點

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

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

//邊表第一個表目的頂點

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

returnmyEdge;

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

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

EdgemyEdge;

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

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

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

//temp指向邊表頭一個

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){ //為圖設定一條邊

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

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指向邊表頭一個

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]--; //終點的入度減1

return;

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

G.Mark[v]=VISITED; //將標記位設置為VISITED

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

v1v2v3v4v5v6v7v8v1v2v3v5v4v6v7v8只有父輩結(jié)點被訪問后才會訪問子孫結(jié)點！把圖人為的分層，按層遍歷。廣度優(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)先搜索算法的實現(xiàn)voidBFS(Graph&G,intV){

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

usingstd::queue;

queue<int>Q;//訪問頂點V，并標記其標志位，V入隊

G.Mark[V]=VISITED;

Visit(G,V);

Q.push(V);

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

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

Q.pop();//出隊

//將與該點相鄰的每一個未訪問結(jié)點都入隊

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

//入隊

Q.push(G.ToVertex(e));} }}}66/1077.4.2廣度優(yōu)先搜索（續(xù)）廣度優(yōu)先搜索算法的時間復雜度與深度優(yōu)先搜索算法的時間復雜度相同67/107練習對于入圖所示的有向圖，試寫出：（1）從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；（2）從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；1234568/1077.4.3拓撲排序一個無環(huán)的有向圖稱為有向無環(huán)圖(directedacyclicgraph，簡稱DAG)將一個有向無環(huán)圖中所有頂點在不違反先決條件關系的前提下排成線性序列的過程稱為拓撲排序(topologicalsorting)拓撲排序可以解決先決條件問題，即以某種線性順序來組織多項任務，以便能夠在滿足先決條件的情況下逐個完成各項任務69/1077.4.3拓撲排序拓撲序列有向無環(huán)圖常用來描述一個過程或一個系統(tǒng)的進行過程。對于有向無環(huán)圖G=<V，E>，如果頂點序列滿足：如果有向無環(huán)圖G中存在頂點vi到vj的一條路徑，那么在序列中頂點vi必在頂點vj之前，頂點集合V的這種線性序列稱作一個拓撲序列(topologicalorder)70/1077.4.3拓撲排序（續(xù)）課程編號課程名稱先決條件C1C2C3C4C5程序語言基礎離散數(shù)學數(shù)據(jù)結(jié)構(gòu)微機原理編譯原理C6操作系統(tǒng)C1C1,C2C3C3,C4表示課程之間優(yōu)先關系的有向圖C1C2C3C5C4C6拓撲排序可以為:C1C2C3C5C4C6C4C1C2C3C5C671/1077.4.3拓撲排序（續(xù)）任何無環(huán)有向圖，其頂點都可以排在一個拓撲序列里，其拓撲排序的方法是：（1）從圖中選擇一個入度為0的頂點且輸出之。（2）從圖中刪掉此頂點及其所有的出邊。（3）回到第（1）步繼續(xù)執(zhí)行。72/1077.4.3拓撲排序不斷重復上述兩個步驟，會出現(xiàn)兩種情形：要么有向圖中頂點全部被輸出，要么當前圖中不存在沒有前驅(qū)的頂點。當圖中的頂點全部輸出時，就完成了有向無環(huán)圖的拓撲排序；當圖中還有頂點沒有輸出時，說明有向圖中含有環(huán)。可見拓撲排序可以檢查有向圖是否存在環(huán)。73/107例，v1v2v4v3v6v5拓撲排序v1v6v4v3v2v574/107v1v2v4v3v6v5例，拓撲排序v1v3v2存在環(huán)75/1077.4.3拓撲排序（續(xù)）//隊列方式實現(xiàn)的拓撲排序voidTopsortbyQueue(Graph&G){

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

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

usingstd::queue;

queue<int>Q;//初始化隊列

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

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

Q.push(i);//圖中入度為0的頂點入隊

}

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

76/1077.4.3拓撲排序（續(xù)）

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

Q.pop();//一個頂點出隊

Visit(G,V);//訪問該頂點

G.Mark[V]=VISITED; //邊e的終點的入度值減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的頂點入隊

}}77/1077.4.3拓撲排序（續(xù)）

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

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

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

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

"ComputerScienceisnomoreaboutcomputersthanastronomyisabouttelescopes."

83/107Dijkstra算法基本思想把圖的頂點集合化分成兩個集合S和V-S。第一個集合S表示最短距離已經(jīng)確定的頂點集，即一個頂點如果屬于集合S當且僅當從源點s到該頂點的最短路徑已知其余的頂點放在另一個集合V-S中。初始時，集合S只包含源點，即S={s}，這時只有源點到自己的最短距離是已知的。設v是V中的某個頂點，把從源點s到頂點v且中間只經(jīng)過集合S中頂點的路徑稱為從源點到v的特殊路徑，并用數(shù)組D來記錄當前所找到的從源點s到每個頂點的最短特殊路徑長度從尚未確定最短路徑長度的集合V-S中取出一個最短特殊路徑長度最小的頂點u，將u加入集合S，同時修改數(shù)組D中由s可達的最短路徑長度84/107Dijkstra算法基本步驟D的初始狀態(tài)為：如果從源點s到頂點v有弧則D[v]記為弧的權(quán)值；否則將D[v]置為無窮大。每次從尚未確定最短路徑長度的集合V-S中取出一個最短特殊路徑長度最小的頂點u，將u加入集合S，同時修改數(shù)組D中由s可達的最短路徑長度：若加進u做中間頂點，使得vi的最短特殊路徑長度變短，則修改vi的距離值（即當D[u]+W[u,vi]<D[vi]時，令D[vi]=D[u]+W[u,vi]）。然后重復上述操作，一旦S包含了所有V中的頂點，D中各頂點的距離值就記錄了從源點s到該頂點的最短路徑長度。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最短路徑新頂點S頂點路徑長度每次修改都用的是最新加入集合S的頂點86/107推導最短路徑距離數(shù)組中還可以設立一個域來記錄從源點到頂點v的最短路徑上v前面經(jīng)過的一個頂點，這樣就可以推導出最短路徑。初始時，對所有的v≠s，均設置其前一個頂點為s在Dijkstra算法更新最短路徑長度時，只要D[u]+W[u,v]<D[v]，就設置v的前一個頂點為u，否則不做修改。當Dijkstra算法終止時就可以找到源點s到頂點v的最短路徑上每個頂點的前一個頂點，從而找到源點s到頂點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記錄從源點到頂點v的最短路徑上v前面經(jīng)過的一個頂點88/107單源最短路徑【代碼7.8】Dijkstra算法

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

intindex; //頂點的索引值，僅Dijkstra算法用到

intlength; //當前最短路徑長度

intpre; //路徑最后經(jīng)過的頂點};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;//源點到自身的路徑長度設置為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路徑長度最小的頂點

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

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

break;

intv=d.index;

G.Mark[v]=VISITED; //將該頂點的標記位設置為VISITED

//加入v以后需要刷新D中v的鄰接點的最短路徑長度

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

B

C

D

E1018

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

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

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

adj(k)[i，j]=adj(k-1)[i，j]另一種是中間經(jīng)過頂點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每對頂點間的最短路徑100/107每對頂點間的最短路徑//Floyd算法voidFloyd(Graph&G,Dist**&D){

int

i,j,v;//i,j,v作為計數(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每對頂點間的最短路徑

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每對頂點間的最短路徑//如果兩個頂點間的最短路徑經(jīng)過頂點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每對頂點間的最短路徑

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