精品數(shù)據(jù)結(jié)構(gòu)圖.PPT

1、 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第七章第七章(上上)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 7.2.1 7.2.1 數(shù)組表示法數(shù)組表示法 7.2.2 7.2.2 鄰接表鄰接表7.3 7.3 圖的遍歷圖的遍歷 7.3.1 7.3.1 深度優(yōu)先搜索深度優(yōu)先搜索 7.3.2 7.3.2 廣度優(yōu)先搜索廣度優(yōu)先搜索7.4 7.4 圖的連通性問題圖的連通性問題 7.4.3 7.4.3 最小生成樹最小生成樹7.5 7.5 有向無環(huán)圖及其應(yīng)用有向無環(huán)圖及其應(yīng)用 7.5.1 7.5.1 拓撲排序拓撲排序7.6 7.6 最短路徑最短路徑 7.6.1 7.6.1

2、 從某個源點到其余各頂點的最短路徑從某個源點到其余各頂點的最短路徑 7.6.2 7.6.2 每一對頂點之間的最短路徑每一對頂點之間的最短路徑數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm圖的類型定義參見圖的類型定義參見p156p156是一種多對多的結(jié)構(gòu)關(guān)系，每個元素是一種多對多的結(jié)構(gòu)關(guān)系，每個元素可以有零個或多個直接前趨；零個或多個直接后可以有零個或多個直接前趨；零個或多個直接后繼。圖是由頂點集合繼。圖是由頂點集合(vertex)(vertex)及頂點間的關(guān)系集及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：合組成的一種數(shù)據(jù)結(jié)構(gòu)： graphgraph( v, r ) ( v, r ) 其中其中 v = v | v v = v

3、 | v 某個數(shù)據(jù)對象某個數(shù)據(jù)對象 是頂點的有窮非空集合；是頂點的有窮非空集合； r =vr=(v, w) | v, w r =vr=(v, w) | v, w v v 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm在有向圖中，頂點對在有向圖中，頂點對是是有序的。在無向圖中，頂點對有序的。在無向圖中，頂點對(x, y)(x, y)是無序的。是無序的。5367214有向圖有向圖v=1,2,3,4,5,6,7v=1,2,3,4,5,6,7vr=,vr=,有向邊又可稱為有向邊又可稱為, vi,vj, 中中vivi稱為稱為或初始點，或初始點，vjvj稱為稱為或終端點。或終端點。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm無向圖無向圖5367214

4、v=1,2,3,4,5,6,7v=1,2,3,4,5,6,7vr=(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),vr=(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(6,7),(5,6),(1,5),(1,7) (6,7),(5,6),(1,5),(1,7) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm 若無向圖中存在邊若無向圖中存在邊(v, u)(v, u)，則稱頂點，則稱頂點v v和和u u互為鄰接點；邊互為鄰接點；邊(v, u)(v, u)依附于頂點依附于頂點v v和和u u；或者說邊；或者說邊(v, u)(v, u)和頂點和頂點v v和和u u相相關(guān)聯(lián)。關(guān)

5、聯(lián)。 在無向圖中：在無向圖中：頂點頂點v v的度的度 = = 與與v v相關(guān)聯(lián)的邊的數(shù)目相關(guān)聯(lián)的邊的數(shù)目 在有向圖中：在有向圖中： 頂點頂點v v的出度的出度= =以以v v為狐尾的有向邊數(shù)為狐尾的有向邊數(shù) 頂點頂點v v的入度的入度= =以以v v為狐頭的有向邊數(shù)為狐頭的有向邊數(shù) 頂點頂點v v的度的度= v= v的出度的出度+v+v的入度的入度 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v1v1 v2v2 v3v3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm 無向圖無向圖g =g =（v v，ee）中的頂點序列）中的頂點序列v v1 1,v,v2 2, , ,v ,vk k, ,若若(v(vi

6、 i,v,vi+1i+1) ) e( i=1,2,e( i=1,2,k-1), v =vk-1), v =v1 1, u =v, u =vk k, , 則則稱該序列是從頂點稱該序列是從頂點v v到頂點到頂點u u的路徑。的路徑。若若v=uv=u，則稱該序列為回路。則稱該序列為回路。在圖在圖g1g1中，中，v0,v1,v2,v3 v0,v1,v2,v3 是是v0v0到到v3v3的路徑。的路徑。 v0,v1,v2,v3,v0v0,v1,v2,v3,v0是回路。是回路。 v0v0 v4v4 v3v3 v1v1 v2v2例：例：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm有向圖有向圖g2g2 v0v0 v1v1 v2v2

7、v3v3在圖在圖g2g2中，中，v0,v2,v3 v0,v2,v3 是是v0v0到到v3v3的路徑。的路徑。v0,v2,v3,v0v0,v2,v3,v0是回路。是回路。有向圖有向圖g =g =（v v，ee）中的頂點序列）中的頂點序列v v1 1,v,v2 2, , ,v ,vk k, , 若若 e (i=1,2,e (i=1,2,k-1), v =vk-1), v =v1 1, u =v, u =vk k, , 則則稱該序列是從頂點稱該序列是從頂點v v到頂點到頂點u u的路徑。的路徑。若若v=uv=u，則稱該序列為回路。則稱該序列為回路。例：例：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm 在一條路徑中在一條路

8、徑中, ,若除起點和終點外若除起點和終點外, ,所有頂點各不所有頂點各不相同相同, ,則稱該路徑為簡單路徑。則稱該路徑為簡單路徑。 由簡單路徑組成的回路稱為簡單回路。由簡單路徑組成的回路稱為簡單回路。 在圖在圖g1g1中，中，v0,v1,v2,v3 v0,v1,v2,v3 是簡單路徑。是簡單路徑。 v0,v1,v2,v4,v1v0,v1,v2,v4,v1不是簡單路徑。不是簡單路徑。在圖在圖g2g2中，中， v0,v2,v3,v0v0,v2,v3,v0是簡單回路。是簡單回路。無向圖無向圖g1g1有向圖有向圖g2g2 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v1v1 v2v2

9、v3v3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm 非連通圖非連通圖 連通圖連通圖 強連通圖強連通圖 非強連通圖非強連通圖 v0v0 v1v1 v2v2 v3v3 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v1v1 v2v2 v3v3 v0v0 v2v2 v3v3 v1v1 v5v5 v4v4在無（有）向圖在無（有）向圖g=( v, e )g=( v, e )中，若對任何兩個頂中，若對任何兩個頂點點 v v、u u 都存在從都存在從v v 到到 u u 的路徑，則稱的路徑，則稱g g是連通圖是連通圖（強連通圖）。（強連通圖）。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm(a)(a)(b)(b)(c)(c) v0v0

10、v4v4 v3v3 v1v1 v2v2 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v4v4 v3v3 v1v1 v2v2設(shè)有兩個圖設(shè)有兩個圖g=g=（v v，ee）、）、g1=g1=（v1v1，e1e1），），若若v1v1 v v，e1 e1 e e，則稱，則稱 g1g1是是g g的子圖。的子圖。例例:(b):(b)、(c) (c) 是是 (a) (a) 的子圖的子圖某些圖的邊具有與它相關(guān)的數(shù)某些圖的邊具有與它相關(guān)的數(shù), , 稱之為權(quán)。稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm非連通圖非連通圖 v0v0 v2v2 v3v3 v1v1 v5v5 v

11、4v4無向圖無向圖g g 的極大連通子圖稱為的極大連通子圖稱為g g的連通分量。的連通分量。極大連通子圖意思是：該子圖是極大連通子圖意思是：該子圖是 g g 連通子圖，將連通子圖，將g g 的任何不在該子圖中的頂點加入，子圖不再連通。的任何不在該子圖中的頂點加入，子圖不再連通。 v0v0 v2v2 v3v3 v1v1 v5v5 v4v4連通分量連通分量數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm有向圖有向圖g g 的極大強連通子圖稱為的極大強連通子圖稱為g g的強連通分量。的強連通分量。極大強連通子圖意思是：該子圖是極大強連通子圖意思是：該子圖是g g的強連通子圖的強連通子圖，將，將d d的任何不在該子圖中的頂點加

12、入，子圖不再的任何不在該子圖中的頂點加入，子圖不再是強連通的。是強連通的。強連通分量強連通分量 v0v0 v1v1 v2v2 v3v3 v0v0 v2v2 v3v3 v1v1圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個頂點到另一個頂點的距離或耗費。一個頂點到另一個頂點的距離或耗費。帶權(quán)帶權(quán)的圖稱為的圖稱為。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm：該子圖是：該子圖是g g 的連通子圖，在該子的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。圖中刪除任何一條邊，子圖不再連通。包含無向圖包含無向圖g g 所有頂點的極小連通子圖稱為所有頂點的極小連通子圖稱為g g 的的生成樹。對

13、非連通圖，則稱由各個連通分量的生生成樹。對非連通圖，則稱由各個連通分量的生成樹的集合為非連通圖的生成森林。成樹的集合為非連通圖的生成森林。 連通圖連通圖 g1g1g1g1的生成樹的生成樹 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v4v4 v3v3 v1v1 v2v2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm，其它或若0ev,v)v,(v1,jijijia例：例：g124130001100000000110表示頂點間相聯(lián)關(guān)系的矩陣。表示頂點間相聯(lián)關(guān)系的矩陣。定義：設(shè)定義：設(shè)g=(v,e)g=(v,e)是有是有n n 1 1個頂點的圖，個頂點的圖，

14、g g的鄰接的鄰接矩陣矩陣a a是具有以下性質(zhì)的是具有以下性質(zhì)的n n階方陣階方陣：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm例：例：15324g20011000101110101010101010，其它或若ev,v)v,(v,jijiijjia網(wǎng)的鄰接矩網(wǎng)的鄰接矩陣可定義為：陣可定義為：6183624127845375例：例：1452375318642數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjm 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)tjmadjvex nextarcvexdata firstarc實現(xiàn)：為圖中每個頂點建立一個單鏈表，第實現(xiàn)：為圖中每個頂點建立一個單鏈表，第i i個單個單鏈表中的結(jié)點表示依附于頂點鏈表中的結(jié)點表示依附于頂點v vi i的邊（有向圖中指的邊（有向圖中指以以v vi i為尾的?。槲驳幕。?。例：例：g1bdac1234acdbvexdatafirstarc 3 2 4 1