數(shù)據(jù)結構與算法-圖的遍歷與連通性

1圖的遍歷與連通性從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷

(GraphTraversal)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數(shù)組visited[]。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第1頁。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第2頁。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第3頁。4DFS

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

后,由

v

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

w1;再從w1出發(fā),訪問與w1鄰接但還沒有訪問過的頂點w2;然后再從w2出發(fā),進行類似的訪問,…如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發(fā),進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復上述過程,直到連通圖中所有頂點都被訪問過為止。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第4頁。5圖的深度優(yōu)先搜索算法template<classT,classE>voidDFS(Graph<T,E>&G,constT&v){//從頂點v出發(fā)對圖G進行深度優(yōu)先遍歷的主過程

inti,loc,n=G.NumberOfVertices();//頂點個數(shù)

bool*visited=newbool[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}數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第5頁。6template<classT,classE>voidDFS(Graph<T,E>&G,intv,boolvisited[]){cout<<G.getValue(v)<<'';//訪問頂點v

visited[v]=true; //作訪問標記

intw=G.getFirstNeighbor(v);//第一個鄰接頂點

while(w>=0){ //若鄰接頂點w存在

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

//若w未訪問過,遞歸訪問頂點w

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

}}數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第6頁。7廣度優(yōu)先搜索BFS

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

//圖中頂點個數(shù)圖的廣度優(yōu)先搜索算法數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第9頁。10

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

//頂點進隊列,實現(xiàn)分層訪問

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

Q.DeQueue(loc);

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

while(w>=0){ //若鄰接頂點w存在

if(!visited[w]){ //若未訪問過數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第10頁。11cout<<G.getValue(w)<<'';//訪問

visited[w]=true;

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

}

w=G.getNextNeighbor(loc,w);

//找頂點loc的下一個鄰接頂點

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

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

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

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

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

//掃描所有頂點

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

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

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

} 數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第14頁。15delete[]visited;}例：以深度優(yōu)先搜索方法從頂點出發(fā)遍歷圖,建立深度優(yōu)先生成森林。A有向圖深度優(yōu)先生成森林ABCDEFGABDECFG數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第15頁。16最小生成樹

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

個頂點的連通網(wǎng)絡的生成樹有n

個頂點、n-1條邊。構造最小生成樹：假設有一個網(wǎng)絡，用以表示n

個城市之間架設通信線路，邊上的權值代表架設通信線路的成本。如何架設才能使線路架設的成本達到最小？數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第16頁。17構造最小生成樹的準則必須使用且僅使用該網(wǎng)絡中的n-1條邊來聯(lián)結網(wǎng)絡中的n

個頂點；不能使用產(chǎn)生回路的邊；各邊上的權值的總和達到最小。北京天津南京上海廣州西安成都昆明武漢34764158312419253822221931394450數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第17頁。18北京天津南京上海廣州西安成都昆明武漢76241922221931北京天津南京上海廣州西安成都昆明武漢34764158312419253822221931394450數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第18頁。19克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的基本思想： 設有一個有n個頂點的連通網(wǎng)絡N={V,E},最初先構造一個只有n個頂點,沒有邊的非連通圖T={V,},圖中每個頂點自成一個連通分量。當在E中選到一條具有最小權值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權值最小的邊。如此重復下去,直到所有頂點在同一個連通分量上為止。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第19頁。20Kruskal算法的偽代碼描述

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

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

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;數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第20頁。21算法的框架利用最小堆(MinHeap)和并查集(DisjointSets)來實現(xiàn)克魯斯卡爾算法。首先,利用最小堆來存放E中的所有的邊,堆中每個結點的格式為在構造最小生成樹過程中,利用并查集的運算檢查依附一條邊的兩頂點tail、head

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

tailheadcost

數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第21頁。22隨著各邊逐步加入到最小生成樹的邊集合中,各連通分量也在逐步合并,直到形成一個連通分量為止。10504613228102514242216181250461325046132原圖(a)(b)構造最小生成樹的過程數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第22頁。231012504613228102514242216181250461325046132101412原圖(c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第23頁。24在求解最小生成樹時，可以用鄰接矩陣存儲圖，也可以用鄰接表存儲圖。算法中使用圖的抽象基類的操作，無需考慮圖及其操作的具體實現(xiàn)。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第24頁。25出堆順序

(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)數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第25頁。26普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡N={V,E}中的某一頂點u0

出發(fā),選擇與它關聯(lián)的具有最小權值的邊(u0,v),將其頂點加入到生成樹頂點集合U中。 以后每一步從一個頂點在集合U中,而另一個頂點不在集合U中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續(xù)下去,直到網(wǎng)絡中的所有頂點都加入到生成樹頂點集合U中為止。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第26頁。27普里姆(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;數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第27頁。28252510504613228102514242216185046132504613210原圖(a)

(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第28頁。29例子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}數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第29頁。305046132281025142422161812H={(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}數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第30頁。315046132281025142422161812H={(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}5046132281025142422161812H={(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}數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第31頁。325046132281025142422161812H={(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)數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第32頁。33Prim算法適用于邊稠密的網(wǎng)絡。Kruskal算法不僅適合于邊稠密的情形，也適合于邊稀疏的情形。注意：當各邊有相同權值時，由于選擇的隨意性，產(chǎn)生的生成樹可能不唯一。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第33頁。34最短路徑(ShortestPath)最短路徑問題：在圖中，從某一頂點（稱為源點）到另一頂點（稱為終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值總和達到最小。問題解法

邊上權值非負情形的單源最短路徑問題

—Dijkstra算法

(僅講此算法)

邊上權值為任意值的單源最短路徑問題

—Bellman和Ford算法

(不講)所有頂點之間的最短路徑

—Floyd算法

(不講)數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第34頁。35邊上權值非負情形的

單源最短路徑問題問題的提法：給定一個帶權有向圖D與源點v，求從v到D中其他頂點的最短路徑。限定各邊上的權值大于或等于0。為求得這些最短路徑,Dijkstra提出按路徑長度的遞增次序,逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第35頁。艾茲格·W·迪杰斯特拉EdsgerWybeDijkstra，生于1930年5月11日，卒于2002年8月6日，荷蘭人。計算機科學家，畢業(yè)并就職于荷蘭Leiden大學，早年鉆研物理及數(shù)學，而后轉為計算科學。曾在1972年獲得過素有計算機科學界的諾貝爾獎之稱的圖靈獎。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第36頁。37Dijkstra逐步求解的過程源點終點最短路徑路徑長度v0

v1

v2

v3

v4

10432101003050206010(v0,v1)—(v0,v3)(v0,v4)1030100,60,90(v0,v1,v2)(v0,v3,v4)(v0,v3,v2),50,60(v0,v3,v2,v4)數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第37頁。38引入輔助數(shù)組dist。它的每一個分量dist[i]表示當前找到的從源點v0到終點

vi的最短路徑的長度。初始狀態(tài)：若從v0到頂點vi有邊,則dist[i]為該邊的權值；若從v0到頂點vi無邊,則dist[i]為。假設S是已求得的最短路徑的終點的集合，則可證明：下一條最短路徑必然是從v0出發(fā)，中間只經(jīng)過S中的頂點便可到達的那些頂點vx(vxV-S)的路徑中的一條。每次求得一條最短路徑后,其終點vk加入集合S，然后對所有的vi

V-S，修改其dist[i]值。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第38頁。39Dijkstra算法可描述如下：①

初始化：S{v0};

dist[j]Edge[0][j],

j=1,2,…,n-1;//n為圖中頂點個數(shù)②

求出最短路徑的長度：

dist[k]min{dist[i]},iV-S;

SS∪{k};③

修改：

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

對于每一個

iV-S

;④

判斷：若

S=V,則算法結束，否則轉②。數(shù)據(jù)結構與算法-圖的遍歷與連通性全文共43頁，當前為第39頁。40計算從單個頂點到其他各頂點

最短路徑的算法voidShortestPath(Graph<T,E>&G,Tv,

Edist[],intpath[]){//Graph是一個帶權有向圖。dist[j],0≤j<n,是當前//求到的從頂點v到頂點j的最短路徑長度,path[j],//0≤j<n,存放求到的最短路徑。

intn=G.NumberOfVertices();bool*S=newbool[n]; //最短路徑頂點集

inti,j,k;Ew,min;for(