數(shù)據(jù)結(jié)構(gòu)李秀坤圖集相關(guān)算法

1、第4結(jié)構(gòu)及其應(yīng)用算法圖論1707年出生在的巴塞爾城，歲開始發(fā)表 看到的，直到76歲。幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以的名字，從初等幾何的線，多面體變換公式，四函數(shù)，微分方定理，幾何的次方程的解法到數(shù)論中的程的方程，級數(shù)論的常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的公式等等。據(jù)統(tǒng)計(jì)他那不倦的一生，共寫下了886本書籍和，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、學(xué)等占3%。 1733年，年僅26歲的了彼得堡擔(dān)任學(xué)院物理數(shù)學(xué)所，直到1766年，重回彼得堡，沒有多久，完全失明。在數(shù)學(xué)上的建樹很多，對著名的哥研究。七橋的解答開創(chuàng)了圖論的2013/4/15哈工大計(jì)算

2、機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-2第4結(jié)構(gòu)及其應(yīng)用算法哥七橋從某個(gè)陸地區(qū)域出發(fā)，是否回到出發(fā)地?一條能夠經(jīng)過每座橋一次且僅一次，最后2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-3第4結(jié)構(gòu)及其應(yīng)用算法學(xué)習(xí)目標(biāo)圖結(jié)構(gòu)是一種非線性結(jié)構(gòu)，反映了數(shù)據(jù)對象之間的任意 計(jì)算機(jī)科學(xué)、數(shù)學(xué)和工程中有著非常廣泛的應(yīng)用。，在了解圖的定義及相關(guān)的術(shù)語，掌握圖的邏輯結(jié)構(gòu)及其特點(diǎn) ；了解圖的掌握圖的遍歷，重點(diǎn)掌握圖的鄰接矩陣和鄰接表，重點(diǎn)掌握圖的遍歷算法的實(shí)現(xiàn)；結(jié)構(gòu)；了解圖的應(yīng)用，重點(diǎn)掌握最小生算法、最短路徑算法、拓?fù)渑判蚝蛷剿惴ǖ幕舅枷?、算法原理和?shí)現(xiàn)過程。2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

3、Slide 4-4第4結(jié)構(gòu)及其應(yīng)用算法主要內(nèi)容圖的基本概念4.14.24.34.44.54.64.7圖的結(jié)構(gòu)圖的遍歷最小生算法最短路徑算法拓?fù)渑判蛩惴◤剿惴ū菊滦〗Y(jié)2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-5第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義定義1 圖(Graph)圖是由頂點(diǎn)（vertex）的有窮非空集合和頂點(diǎn)之間 合組成的一種數(shù)據(jù)結(jié)構(gòu)，通常表示為：G = (V，E)（edge）的集其中：G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中頂點(diǎn)之間 的集合。頂點(diǎn)表示數(shù)據(jù)對象；示數(shù)據(jù)對象之間的。v1v2v1v2v3v3v4v5v4v52013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Sl

4、ide 4-6第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)定義1 圖無：若頂點(diǎn)vi和vj之間的vv21沒有方向，則稱這條，表示為(vi,vj)。為無v3如果圖的任意兩個(gè)頂點(diǎn)之間的是無，則稱該圖為無。v4v5有：若頂點(diǎn)vi和vj之間的有方向，則稱這條vv(弧)，表示為。12為有如果圖的任意兩個(gè)頂點(diǎn)之間的是有v3，則稱該圖為有。v4v52013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-7第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)無向完全圖：在無無向完全圖。有向完全圖：在有，如果任意兩個(gè)頂點(diǎn)之間都，則稱該圖為，如果任意兩個(gè)頂點(diǎn)之間都方向相反的兩條弧，則稱該圖為有向完全圖。v1

5、v2v1v2v3v4v4v3含有n個(gè)頂點(diǎn)的無向完全圖有多少條？含有n個(gè)頂點(diǎn)的有向完全圖有多少條??？2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-8第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)鄰接、依附定義1 圖，對于任意兩個(gè)頂點(diǎn)vi和頂點(diǎn)vj，在無若v1v2(vi，vj)，則稱頂點(diǎn)vi和頂點(diǎn)vj相鄰，互為鄰接點(diǎn)，同時(shí)稱 (vi，vj)依附于頂點(diǎn)vi和頂點(diǎn)vj。如：v2的鄰接點(diǎn)： v1 , v3 ,v5v3v4v1v5v2在有若，對于任意兩個(gè)頂點(diǎn)v 和頂點(diǎn)v ，ij有，則稱頂點(diǎn)vi鄰接到頂點(diǎn)vj，頂點(diǎn)vj鄰接于頂點(diǎn)vi，同時(shí)稱弧 依附于頂點(diǎn)vi和頂點(diǎn)vj 。如：v1鄰接到v2

6、 ， v1 鄰接于v4v3v4v52013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-9第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)定義2 度(Dgree)v1v2v2v1v3v3v5v5v4v4頂點(diǎn)的度：在無為D (v)。頂點(diǎn)的入度：在有數(shù)目，記為ID (v)；頂點(diǎn)的出度：在有數(shù)目，記為OD (v)。，頂點(diǎn)v的度是指依附于該頂點(diǎn)的，通常記，頂點(diǎn)v的入度是指以該頂點(diǎn)為弧頭的弧的，頂點(diǎn)v的出度是指以該頂點(diǎn)為弧尾的弧的， D (v)= ID (v) + OD (v)在有2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-10第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)定

7、義2 度(Dgree)v1v2v2v1v3v3v5在具有n個(gè)頂點(diǎn)、e條？v5v4v4G中，各頂點(diǎn)的度之和與的無之和的nD ( vi ) =2ei=1在具有n個(gè)頂點(diǎn)、e條G中，各頂點(diǎn)的入度之和與各頂點(diǎn)的的有出度之和的？與之和的？nni=1= OD ( vi ) = eID ( vi )i=12013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-11第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)定義3 路徑（Path）和路徑長度、簡單簡單回路G=( V, E ) 中，若一個(gè)頂點(diǎn)序列vp ,vi1 , vi2 , vim ,vq ，在無使得（vp ,vi1）,（vi1 ,vi2）, ,（v

8、im ,vq）E(G)，則稱頂點(diǎn)vp路到vq有一條路徑。G =( V, E )中，若一個(gè)頂點(diǎn)序列vp ,vi1 ,vi2 , vim ,vq ，使在有得有, ,E(G)，則稱頂點(diǎn)vp路到vq有一條有向路徑。非帶帶的路徑長度是指此路徑上的條數(shù)。的路徑長度是指路徑上各的權(quán)之和。簡單路徑：若路徑上各頂點(diǎn) v1,v2,.,vm 均互不相同, 則稱這樣的路徑為簡單路徑。簡單回路：若路徑上第一個(gè)頂點(diǎn) v1與最后一個(gè)頂點(diǎn)vm重合, 則稱這樣的簡單路徑為簡單回路或環(huán)。2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-12第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)定義4 圖的連通性連通圖與連通

9、分量頂點(diǎn)的連通性：在無vi與vj是連通的。連通圖：如果一個(gè)無通圖。, 若從頂點(diǎn)vi到頂點(diǎn)vj (ij)有路徑, 則稱頂點(diǎn)任意一對頂點(diǎn)都是連通的, 則稱此圖是連連通分量：非連通圖的極大連通子圖叫做連通分量。v1v2v1v1v1v4v32013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-13第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)定義4 圖的連通性強(qiáng)連通圖與強(qiáng)連通分量頂點(diǎn)的強(qiáng)連通性：在有, 若對于每一對頂點(diǎn)vi和vj (ij), 都一條從vi到vj和從vj到vi的有向路徑,則稱頂點(diǎn)vi與vj是強(qiáng)連通的。任意一對頂點(diǎn)都是強(qiáng)連通的, 則稱此有強(qiáng)連通圖：如果一個(gè)有是強(qiáng)連通圖。強(qiáng)連通分量

10、:連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量v1v2v3v5v42013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-14第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)圖的操作設(shè)圖G=(V,E)，圖上定義的基本操作如下：NewNode ( G )：建立一個(gè)新頂點(diǎn)，V=Vv DelNone ( G, v )：刪除頂點(diǎn)v以及與之相關(guān)聯(lián)的所有SetSucc ( G, v1, v2 ):增加一條，E = E(v1,v2) ,V=VDelSucc ( G, v1, v2 )：刪除（v1,v2）,V不變Succ ( G, v1, v2 )：求出v的所有直接后繼結(jié)點(diǎn)Pred ( G, v)：求出v的所有

11、直接前導(dǎo)結(jié)點(diǎn)IsEdge ( G, v1, v2 )：（v1,v2）EFirstAdjVex( G , v ): 頂點(diǎn)v 的第一個(gè)鄰接頂點(diǎn)NextAdjVex( G, v, w)：頂點(diǎn)v 的某個(gè)鄰接點(diǎn)w的下一個(gè)鄰接頂點(diǎn)。2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-15第4結(jié)構(gòu)及其應(yīng)用算法4.1 基本定義(cont.)不同邏輯結(jié)構(gòu)之間的比較ABEFCDAv1v2BCv3v4v5DEF(1:1)；性結(jié)構(gòu)中，數(shù)據(jù)元間僅具有線性在結(jié)構(gòu)中，結(jié)點(diǎn)之間具有層次(1:m)；(m:n)。在圖型結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能有2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-16第4結(jié)構(gòu)

12、及其應(yīng)用算法4.1 基本定義(cont.)不同邏輯結(jié)構(gòu)之間的比較ABEFCDAv1v2BCv3v4v5DEF性結(jié)構(gòu)中，元間的為前驅(qū)和后繼；為雙親和孩子； 為鄰接。在結(jié)構(gòu)中，結(jié)點(diǎn)之間的在圖型結(jié)構(gòu)中，頂點(diǎn)之間的2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-17第4結(jié)構(gòu)及其應(yīng)用算法4.2 圖的結(jié)構(gòu)圖(一維數(shù)組）?是m:n，即任何兩個(gè)頂點(diǎn)之間都可能是否可以采用順序結(jié)構(gòu)圖的特點(diǎn)：頂點(diǎn)之間的（），無法通過位置表示這種任意的邏輯，所以，圖無法采用順序結(jié)構(gòu)。如何圖？考慮圖的定義，圖是由頂點(diǎn)和組成的；-頂點(diǎn)之間的如何頂點(diǎn)、如何。v1v2v1v2v3v3v5v4v5v42013/4/15哈工大計(jì)算機(jī)

13、科學(xué)與技術(shù)學(xué)院Slide 4-18第4結(jié)構(gòu)及其應(yīng)用算法4.2 圖的結(jié)構(gòu)(cont.)鄰接矩陣 （Adjacency Matrix）表示（數(shù)組表示法）基本思想：用一個(gè)一維數(shù)組圖中頂點(diǎn)的信息，用一個(gè)二維數(shù)組（稱為鄰接矩陣）圖中各頂點(diǎn)之間的鄰接。假設(shè)圖G(V，E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)nn的方陣，定義為：10若 ( i , j ) E 或 E否則edge i j =v2v1v2v1v3v3v4v5v4v52013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-19第4結(jié)構(gòu)及其應(yīng)用算法4.2 圖的結(jié)構(gòu)(cont.)鄰接矩陣 （Adjacency Matrix）表示（數(shù)組表示法）無的鄰接矩陣：

14、vertex=v1v2v1v2v3v4v5v1 v2 v3 v4 v5v3edge =v5v4結(jié)構(gòu)特點(diǎn)：主對角線為 0 且一定是對稱矩陣；：1. 如何求頂點(diǎn)vi的度？2.如何頂點(diǎn) vi和 vj 之間是否？3.如何求頂點(diǎn) vi的所有鄰接點(diǎn)？2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-200101010101010111001110000v1v2v3v4v5第4結(jié)構(gòu)及其應(yīng)用算法4.2 圖的結(jié)構(gòu)(cont.)鄰接矩陣 （Adjacency Matrix）表示（數(shù)組表示法）有的鄰接矩陣：vertex=vv12v1v2v3v4v5v1 v2 v3 v4 v5v3v4v5edge =結(jié)構(gòu)特

15、點(diǎn)：有的鄰接矩陣一定不對稱嗎？：1.如何求頂點(diǎn)vi的出度？2. 如何頂點(diǎn) vi和 vj 之間是否有？3. 如何求鄰接于頂點(diǎn) vi的所有頂點(diǎn)？4. 如何求鄰接到頂點(diǎn) vi的所有頂點(diǎn)？2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-210100000100000111001100110v1v2v3v4v5第4結(jié)構(gòu)及其應(yīng)用算法4.2 圖的結(jié)構(gòu)(cont.)鄰接矩陣 （Adjacency Matrix）表示（數(shù)組表示法）結(jié)構(gòu)定義：typedef struct VertexData verlist NumVertices;/頂點(diǎn)表EdgeData edgeNumVerticesNumVert

16、ices;/鄰接矩陣, 可視為之間的int n, e; /圖的頂點(diǎn)數(shù)與 MTGraph;v100010v210001v301010v400101v500110v1 v2 v3 v4 v5v1v2edge=v3vertexvv452013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-22v1v2v3v4v5假設(shè)圖G有n個(gè)頂點(diǎn)e條 ，則該圖的需求為O(n+n2) = O(n2) ，與 的條數(shù)e無關(guān)。第4結(jié)構(gòu)及其應(yīng)用算法4.2 圖的結(jié)構(gòu)(cont.)結(jié)構(gòu)的建立算法實(shí)現(xiàn)的步驟：1.確定圖的頂點(diǎn)個(gè)數(shù)n和e；2.輸入頂點(diǎn)信息在一維數(shù)組vertex中；3. 初始化鄰接矩陣；4. 依次輸入每條在鄰接矩陣

17、edge中；4.1 輸入依附的兩個(gè)頂點(diǎn)的序號i, j；4.2 將鄰接矩陣的第i行第j列的元素值置為1；4.3 將鄰接矩陣的第j行第i列的元素值置為1。v100010v210001v301010v400101v500110v1 v2 v3 v4 v5v1v2edge=v3vertexvv452013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-23v1v2v3v4v5第4結(jié)構(gòu)及其應(yīng)用算法4.2 圖的結(jié)構(gòu)的建立算法的實(shí)現(xiàn)：結(jié)構(gòu)(cont.)void CreateMGragh (MTGragh *G) /建立圖的鄰接矩陣int i, j, k, w; cinGnGe; for (i=0; iG

18、n; i+)/1.輸入頂點(diǎn)數(shù)和/2.讀入頂點(diǎn)信息，建立頂點(diǎn)表Gvertlisti=getchar( ); for (i=0; iGn; i+)for (j=0;jGn;j+) Gedgeij=0;for (k=0; kijw;/ 輸入（i,j）上的wG edgeij=w; G edgeji=w; /時(shí)間復(fù)雜度：T = O( n+ n2 +e) 。當(dāng)e G.n G.e;for ( int i = 0; i G.vexlisti.vertex;/1.輸入頂點(diǎn)個(gè)數(shù)和/2.建立頂點(diǎn)表/2.1輸入頂點(diǎn)信息v2v3v4G.vexlisti.firstedge = NULL; /2.2置為空表輸入,建立fo

19、r ( i = 0; i tail head weight;/3.逐條/3.1輸入/3.2建立EdgeNode * p = new EdgeNode;結(jié)點(diǎn)結(jié)點(diǎn)padjvex = head;pcost = weight; /3.3設(shè)置pnext = G.vexlisttail.firstedge; G.vexlisttail.firstedge = p;p = new EdgeNode;/3.4鏈入第tail 號鏈表的前端padjvex = tail;pcost = weight;pnext = G.vexlisthead.firstedge; /鏈入第 head 號鏈表的前端G.vexlist

20、head.firstedge = p; /時(shí)間復(fù)雜度：O(2e+n)2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-34第4結(jié)構(gòu)及其應(yīng)用算法4.2 圖的結(jié)構(gòu)(cont.)結(jié)構(gòu)的比較鄰接矩陣和鄰接表圖的2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-35空間性能時(shí)間性能適用范圍唯一性鄰接矩陣O（n2）O（n2）稠密圖唯一？鄰接表O（n+e）O（n+e）稀疏圖不唯一？第4結(jié)構(gòu)及其應(yīng)用算法u 十字鏈表(有)十字鏈表是有的另一種鏈?zhǔn)浇Y(jié)構(gòu)。將有的鄰接表和逆鄰接表結(jié)合起來的結(jié)構(gòu)。在十字鏈表中有兩種結(jié)點(diǎn)：u 弧結(jié)點(diǎn)：每一條弧的信息，用鏈表在一起?；〗Y(jié)點(diǎn)結(jié)構(gòu):u 頂點(diǎn)結(jié)點(diǎn)：每一個(gè)頂點(diǎn)的

21、信息，使用一維數(shù)組來。頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu):2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-36datafirstinfirstoutivexjvexjlinkilinkinfo第4結(jié)構(gòu)及其應(yīng)用算法V1V2V3V4弧結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)01002V11V2220V33V42013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-3723323130第4結(jié)構(gòu)及其應(yīng)用算法BC 十字鏈表中既容易找到以vi為尾的弧，也容易找到以vi為頭的弧，因而容易求得頂點(diǎn) 的出度和入度。ADFE01012345BCDEF512013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-385332251404A第4結(jié)構(gòu)

22、及其應(yīng)用算法u 鄰接多重表(無)鄰接多重表是無的另一種鏈?zhǔn)奖硎窘Y(jié)構(gòu)。和十字鏈表類似。鄰接多重表中，每一條 用一個(gè)結(jié)點(diǎn)表示。在鄰接多重表中有兩種結(jié)點(diǎn)：結(jié)點(diǎn)：結(jié)點(diǎn)結(jié)構(gòu):每一條的信息，用鏈表在一起。uu 頂點(diǎn)結(jié)點(diǎn)：每一個(gè)頂點(diǎn)的信息，使用一維數(shù)組來。頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu):2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-39datafirstedgemarkivexilinkjvexjlinkinfo第4結(jié)構(gòu)及其應(yīng)用算法V1V2V3V4V5030123401V1V223V321V4V5412013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-4024第4結(jié)構(gòu)及其應(yīng)用算法BCAD01040FE1

23、4151C232523E4F52013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-41D35BA第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷）1986年圖靈獎(jiǎng)獲得者1939年生于西雅圖。美國學(xué)智能和工程院、人。1962和1964年和博士學(xué)位。先后在普獲斯坦福大學(xué)大學(xué)、斯坦福大學(xué)等工作，也曾任職于一些科學(xué)研究機(jī)構(gòu)如NSF和NRC。著作很多如算法設(shè)計(jì)與分析基礎(chǔ) 數(shù)據(jù)結(jié)構(gòu)與算法自理論、語言和計(jì)算導(dǎo)論形式語言及其與自的John Edward HopcroftRobert Endre Tarjan普大學(xué)計(jì)算機(jī)科學(xué)系教授，1948年4月30日生于加利福尼亞州。1969年本科畢業(yè)，進(jìn)入斯坦福大學(xué)研究生

24、院，1972年獲得博士學(xué)位。平面圖測試的高效算法 ；合并-搜索；“分?jǐn)偂彼惴ǖ母拍?；八字形樹；持久性?shù)據(jù)結(jié) 構(gòu)2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-42第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)圖的遍歷（圖的搜索）從圖中某一頂點(diǎn)出發(fā)，對圖中所有頂點(diǎn)一次且僅一次。：抽象操作，可以是對結(jié)點(diǎn)進(jìn)行的各種處理圖結(jié)構(gòu)的復(fù)雜性性表中，數(shù)據(jù)元素在表中的編號就是元素在序列中的位置，因而 其編號是唯一的；在樹結(jié)構(gòu)中，將結(jié)點(diǎn)按層序編號，由于樹具有層次性，因而其層序編 號也是唯一的；在圖結(jié)構(gòu)中，任何兩個(gè)頂點(diǎn)之間都可能后次序的，所以，頂點(diǎn)的編號不唯一。，頂點(diǎn)是沒有確定的先2013

25、/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-43第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)圖的遍歷要解決的關(guān)鍵在圖中，如何選取遍歷的起始頂點(diǎn)？ 解決辦法：從編號小的頂點(diǎn)開始。從某個(gè)起點(diǎn)始可能到達(dá)不了所有其它頂點(diǎn)，怎么辦？解決辦法：多次調(diào)用從某頂點(diǎn)出發(fā)遍歷圖的算法。圖中可能回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)“相通”，在完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些又回到了曾經(jīng)？過的頂點(diǎn)。如何避免某些頂點(diǎn)可能會(huì)被重復(fù)解決辦法：附設(shè)標(biāo)志數(shù)組visitedn 。在圖中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)這樣的頂點(diǎn)過后，如何選取下一個(gè)要的頂點(diǎn)？解決辦法：深度優(yōu)先搜索（Depth First S

26、earch）和廣度優(yōu)先搜索（Breadth First Search）。2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-44第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)深度優(yōu)先遍歷類似于樹結(jié)構(gòu)的先序遍歷設(shè)圖G的初態(tài)是所有頂點(diǎn)都“未過（False）”，在G中任選一個(gè)頂點(diǎn) v 為初始出發(fā)點(diǎn)(源點(diǎn))，則深度優(yōu)先搜索可定義為:出發(fā)點(diǎn) v，并將其標(biāo)記為“過 （True） ”;首先然后，從 v 出發(fā)，依次與 v 相鄰的頂點(diǎn) w ；若 w“未過（False）”，則以 w 為新的出發(fā)點(diǎn)遞歸地進(jìn)行深度優(yōu)先搜索， 直到圖中所有與源點(diǎn) v 有路徑相通的頂點(diǎn)（亦稱從源點(diǎn)可到達(dá)的頂點(diǎn)）均被為

27、止；若此時(shí)圖中仍有未被過的頂點(diǎn)，則另選一個(gè)“未過”的頂點(diǎn)作為新的搜索起點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被 過為止。2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-45第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)深度優(yōu)先遍歷示例深度優(yōu)先遍歷序列?入棧序列?出棧序列?v1v1v2v3v2v3v4v5v6v7v4v5v6v7棧生成森林v8v3v8遍歷序列：v1v6v2v5v8v4v72013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-46v578v64v23v1第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)深度優(yōu)先遍歷特點(diǎn)：是遞歸的定義，是盡可能

28、對縱深方向上進(jìn)行搜索，故稱先深或深 度優(yōu)先搜索。先深或深度優(yōu)先編號。搜索過程中，根據(jù)優(yōu)先編號。先深序列或DFS序列：順序給頂點(diǎn)進(jìn)行的編號，稱為先深或深度先深搜索過程中，根據(jù)或DFS序列。生成森林（樹）：順序得到的頂點(diǎn)序列，稱為先深序列有原圖的所有頂點(diǎn)和搜索過程中所經(jīng)過的先深搜索結(jié)果不唯一即圖的DFS序列、先深編號和生成森林不唯一。的子圖。2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-47第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)深度優(yōu)先遍歷主算法：bool visitedNumVertices; /標(biāo)記數(shù)組是全局變量int dfnNumVertices; /頂點(diǎn)

29、的先深編號void DFSTraverse (AdjGraph G)/主算法/ 先深搜索一鄰接表表示的圖G；而以鄰接矩陣表示G時(shí)，算法完全相同int i , count = 1;for ( int i = 0; i G.n; i+ )visited i =False;/標(biāo)志數(shù)組初始化for ( int i = 0; i G.n; i+ ) if ( ! visitedi )DFSX ( G, i ); /從頂點(diǎn)i 出發(fā)的一次搜索，BFSX(G, i )2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-48第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)從一個(gè)頂點(diǎn)出發(fā)的一次

30、深度優(yōu)先遍歷算法：實(shí)現(xiàn)步驟：1.頂點(diǎn)v; visitedv=1;2. w=頂點(diǎn)v的第一個(gè)鄰接點(diǎn)；3. while (w)3.1 if (w未被) 從頂點(diǎn)w出發(fā)遞歸執(zhí)行該算法;3.2 w=頂點(diǎn)v的下一個(gè)鄰接點(diǎn);2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-49第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)從一個(gè)頂點(diǎn)出發(fā)的一次深度優(yōu)先遍歷算法：void DFS1 (AdjGraph* G, int i)/以vi為出發(fā)點(diǎn)時(shí)對鄰接表表示的圖G進(jìn)行先深搜索EdgeNode *p; coutadjvexif( !visited padjvex )/若vj尚未DFS1(G, pa

31、djvex); p=pnext;/則以vj為出發(fā)點(diǎn)先深搜索 /DFS12013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-50第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)從一個(gè)頂點(diǎn)出發(fā)的一次深度優(yōu)先遍歷算法：void DFS1 (AdjGraph* G, int i)/以vi為出發(fā)點(diǎn)時(shí)對鄰接表表示的圖G進(jìn)行先深搜索EdgeNode *p; coutGvexlisti.vertex; visitedi=True; dfni=count+; p=Gvexlisti.firstedge; while( p ) if( !visited padjvex ) DFS1(G, pa

32、djvex);p=pnext;v1v0v2v3adjvexv4nextvertexfirstedge012 /DFS134頂點(diǎn)表2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-513v0v1v2v3v4第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)從一個(gè)頂點(diǎn)出發(fā)的一次深度優(yōu)先遍歷算法：void DFS2(MTGraph *G, int i)v001010v110101v201011v310100v401100/以vi為出發(fā)點(diǎn)對鄰接矩陣表示的圖G進(jìn)行深度優(yōu)先搜索v0int j; coutGvexlisti; visiti=True; dfni=count;count +

33、;v1 v/定點(diǎn)vi/標(biāo)記vi已2v3 v4/對vi進(jìn)行編號/下一個(gè)頂點(diǎn)的編號for( j=0; jGn; j+ ) /依次搜索vi的鄰接點(diǎn)if ( (Gedgeij = 1)&！visitedj ) /若vj尚未DFS2( G, j );/DFS2v1v0v2v3v42013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-52第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)廣度優(yōu)先遍歷類似于樹結(jié)構(gòu)的層序遍歷設(shè)圖G的初態(tài)是所有頂點(diǎn)都“未過（False）”，在G中任選一個(gè)頂點(diǎn)v 為源點(diǎn)，則廣度優(yōu)先搜索可定義為:首先出發(fā)點(diǎn)v，并將其標(biāo)記為“過（True）”;所有與v 相鄰的頂點(diǎn)w1，w2wt；接著依次然后依次與w1，w2 wt相鄰的的頂點(diǎn);依次類推，直至圖中所有與源點(diǎn)v有路相通的頂點(diǎn)都已 為止；此時(shí)，從v 開始的搜索結(jié)束，若G是連通的，則遍歷完成；否過則在G中另選一個(gè)尚未的頂點(diǎn)作為新源點(diǎn)，繼續(xù)上述搜索過程，直到G中的所有頂點(diǎn)均已為止。2013/4/15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Slide 4-53第4結(jié)構(gòu)及其應(yīng)用算法4.3 圖的搜索（遍歷） (cont.)廣度優(yōu)先遍歷示例廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?v1v0v4v3v2遍歷序列：v0v6v6v