數(shù)據(jù)結(jié)構(gòu)——圖PPT學(xué)習(xí)教案

1、會計學(xué)1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)圖圖第1頁/共76頁圖的定義及相關(guān)術(shù)語圖的定義及相關(guān)術(shù)語(1) 圖的定義：圖的定義：圖圖G由兩個集合由兩個集合V(G)和和E(G)所所組成組成，記作，記作G=(V,E)。其中，。其中，V(G)是圖中是圖中頂點的非空有限集合，頂點的非空有限集合，E(G)是圖中邊的有是圖中邊的有限集合。限集合。 (2) 有向圖有向圖。如果圖中每條邊都是頂點的有序。如果圖中每條邊都是頂點的有序?qū)?，即每條邊都用箭頭表明了方向，則此對，即每條邊都用箭頭表明了方向，則此圖為有向圖。有向圖中的圖為有向圖。有向圖中的邊也稱為弧邊也稱為弧，用，用尖括號尖括號括起一對頂點表示。括起一對頂點表示。第2頁/共

2、76頁有向圖示例有向圖示例1324G1第3頁/共76頁第4頁/共76頁(V2, V1)表示同一條邊。表示同一條邊。第5頁/共76頁圖圖3-23 無向圖示例無向圖示例1234G2第6頁/共76頁第7頁/共76頁132112132132G3G3的子圖 圖與子圖圖與子圖 第8頁/共76頁ABECF1597211132有向網(wǎng)有向網(wǎng)第9頁/共76頁14235915251030無向網(wǎng)無向網(wǎng)第10頁/共76頁(6)完全圖完全圖。假設(shè)圖中有假設(shè)圖中有 n 個頂點，個頂點，e 條條邊，則含有邊，則含有 e=n(n-1)/2 條邊的無向圖稱條邊的無向圖稱作作完全圖完全圖；含有含有 e=n(n-1) 條弧的有向圖條

3、弧的有向圖稱作稱作有向完全圖。有向完全圖。(7) 稠密圖與稀疏圖稠密圖與稀疏圖。若圖的邊或弧的數(shù)若圖的邊或弧的數(shù)目接近于相應(yīng)完全圖的邊或弧的數(shù)目，目接近于相應(yīng)完全圖的邊或弧的數(shù)目，則稱之為則稱之為稠密圖稠密圖，否則稱為，否則稱為稀疏圖。稀疏圖。 第11頁/共76頁ABECF第12頁/共76頁(9) 簡單路徑簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路：序列中頂點不重復(fù)出現(xiàn)的路徑。徑。(10) 簡單回路簡單回路：序列中第一個頂點和最后一：序列中第一個頂點和最后一個頂點相同的簡單路徑。個頂點相同的簡單路徑。(11) 連通圖：連通圖：在無向圖中，若每一對頂點之在無向圖中，若每一對頂點之間都有路徑，則稱此圖為間

4、都有路徑，則稱此圖為連通圖連通圖。(12) 連通分量：連通分量：若無向圖為非連通圖，則圖若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的中各個極大連通子圖稱作此圖的連通分量連通分量。第13頁/共76頁連通圖連通圖BACDFEBACDFE非連通圖非連通圖第14頁/共76頁(13) 強連通圖：強連通圖：在有向圖中，若每一對頂點在有向圖中，若每一對頂點u和和v之間都存在之間都存在v到到u及及u到到v的路徑，則稱此的路徑，則稱此圖為圖為強連通圖強連通圖。(14) 強連通分量：強連通分量：各個強連通子圖稱作該各個強連通子圖稱作該有有向圖向圖的的強連通分量強連通分量。第15頁/共76頁強連通圖強連通圖

5、ABECFABECF非強連通圖非強連通圖第16頁/共76頁某頂點為弧頭的弧的數(shù)目，稱為此某頂點為弧頭的弧的數(shù)目，稱為此頂點的頂點的入度入度，記作，記作ID(V)；以某頂點；以某頂點為弧尾的弧的數(shù)目稱為此頂點的為弧尾的弧的數(shù)目稱為此頂點的出出度度，記作，記作OD(V)。該頂點的度則是。該頂點的度則是此頂點的入度與出度之和。此頂點的入度與出度之和。第17頁/共76頁ACDFETD(B) = 3，TD(A) = 2 BABECFID(B) = 2，OD(B) = 1TD(B)=ID(B)+OD(B) =3第18頁/共76頁建立和銷毀圖結(jié)構(gòu)建立和銷毀圖結(jié)構(gòu)插入或刪除頂點插入或刪除頂點對鄰接點的操作對鄰

6、接點的操作訪問頂點訪問頂點遍歷圖遍歷圖插入和刪除弧插入和刪除弧基本操作基本操作第19頁/共76頁第20頁/共76頁圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)一、圖的數(shù)組一、圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示二、圖的鄰接表存儲表示二、圖的鄰接表存儲表示*三、有向圖的十字鏈表存儲表示三、有向圖的十字鏈表存儲表示 *四、無向圖的鄰接多重表存儲表示四、無向圖的鄰接多重表存儲表示第21頁/共76頁根據(jù)圖的定義可知，一個圖的邏輯結(jié)構(gòu)分兩部根據(jù)圖的定義可知，一個圖的邏輯結(jié)構(gòu)分兩部分，一部分是組成圖的分，一部分是組成圖的頂點的集合頂點的集合；另一部分；另一部分是頂點之間的聯(lián)系，即是頂點之間的聯(lián)系，即邊或弧的集合邊或弧

7、的集合?？捎靡粋€一維數(shù)組存放圖中所有頂點的信息；可用一個一維數(shù)組存放圖中所有頂點的信息；用一個二維數(shù)組來存放數(shù)據(jù)元素之間的關(guān)系的用一個二維數(shù)組來存放數(shù)據(jù)元素之間的關(guān)系的信息信息(即邊或弧的集合即邊或弧的集合E)。這個二維數(shù)組稱之為。這個二維數(shù)組稱之為鄰接矩陣。鄰接矩陣。鄰接矩陣是表示頂點之間的鄰接關(guān)系的矩陣鄰接矩陣是表示頂點之間的鄰接關(guān)系的矩陣。設(shè)設(shè)G =(V，E)是有是有n(n1)個頂點的圖，則個頂點的圖，則G的鄰的鄰接矩陣接矩陣A是一個是一個nn階矩陣。階矩陣。第22頁/共76頁Aij=0 若(Vi,Vj)或E(G)1 若(Vi,Vj)或E(G)一、圖的數(shù)組一、圖的數(shù)組( (鄰接矩陣鄰接矩

8、陣) )存儲表示存儲表示定義定義:矩陣的元素為矩陣的元素為BADFEC010010100011000101001001110000011100ABCDEFABCDEF第23頁/共76頁有向圖的鄰接矩陣有向圖的鄰接矩陣ABDCE0101000100000010010011000ABCDE第24頁/共76頁第25頁/共76頁兩個點的鄰接關(guān)系。兩個點的鄰接關(guān)系。第26頁/共76頁ijijijW (V, V) V, VE(G)Ai, j 反之若若或或其中其中Wij是邊是邊(Vi, Vj)或弧或弧上的權(quán)值。上的權(quán)值。第27頁/共76頁所示。所示。二、圖的鄰接表存儲表示二、圖的鄰接表存儲表示第28頁/共7

9、6頁鄰接表中表結(jié)點的結(jié)點結(jié)構(gòu)鄰接表中表結(jié)點的結(jié)點結(jié)構(gòu)頂點頂點Vi的鄰接點在圖中的位置的鄰接點在圖中的位置指向頂點指向頂點Vi的下一鄰接點的指針的下一鄰接點的指針adjvexdatanextarc權(quán)值權(quán)值第29頁/共76頁鄰接表中頭結(jié)點的結(jié)點結(jié)構(gòu)鄰接表中頭結(jié)點的結(jié)點結(jié)構(gòu) vexdatafirstarc指向頂點指向頂點Vi的第一個鄰接點的指針的第一個鄰接點的指針存儲存儲Vi的名字或有關(guān)信息的名字或有關(guān)信息第30頁/共76頁nn大可能值大可能值*/第31頁/共76頁nint vexdata;nARCNODE *firstarc;n adjlistVTXUNM;第32頁/共76頁BACDFE0 A 1

10、 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3 示例：無向圖的鄰接表示例：無向圖的鄰接表第33頁/共76頁有向圖的鄰接表有向圖的鄰接表ABDCE在有向圖的鄰接表中不在有向圖的鄰接表中不易找到指向該頂點的弧易找到指向該頂點的弧，即難以確定某個頂點，即難以確定某個頂點的入度。的入度。1 3242 00 1 2 3 4 A B C D E1第34頁/共76頁ABECD有向圖的逆鄰接表有向圖的逆鄰接表在有向圖的逆鄰接表中，每個頂點鏈接的是指向該頂點的弧。在有向圖的逆鄰接表中，每個頂點鏈接的是指向該頂點的弧。A B C D E 303120 012344 第35頁/共

11、76頁231231437ABCABC734(a)(b)第36頁/共76頁第第i個單鏈表的結(jié)點個數(shù)就是此結(jié)個單鏈表的結(jié)點個數(shù)就是此結(jié)點的出度；對于無向圖，其鄰接點的出度；對于無向圖，其鄰接表中第表中第i個單鏈表的結(jié)點個數(shù)就是個單鏈表的結(jié)點個數(shù)就是此結(jié)點的度。此結(jié)點的度。第37頁/共76頁第38頁/共76頁圖的遍歷圖的遍歷從圖中某個頂點出發(fā)訪問圖中每個頂點從圖中某個頂點出發(fā)訪問圖中每個頂點一次且僅一次的過程。一次且僅一次的過程。圖的遍歷算法是求解圖的連通性問題、拓圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。撲排序和求關(guān)鍵路徑等算法的基礎(chǔ)。深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索

12、廣度優(yōu)先搜索第39頁/共76頁從圖中某個頂點從圖中某個頂點V0 出發(fā)，訪問此頂點，出發(fā)，訪問此頂點，然后然后依次從依次從V0的各個未被訪問的鄰接點的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖中的其余頂點出發(fā)深度優(yōu)先搜索遍歷圖中的其余頂點，直至圖中所有和直至圖中所有和V0有路徑相通的頂點都有路徑相通的頂點都被訪問到為止。被訪問到為止。一、深度優(yōu)先搜索遍歷圖一、深度優(yōu)先搜索遍歷圖連通圖連通圖的深度優(yōu)先搜索遍歷的深度優(yōu)先搜索遍歷(用棧用棧)第40頁/共76頁W1、W2和和W3 均為均為 V0 的鄰接點，的鄰接點，SG1、SG2 和和 SG3 分別為含分別為含頂點頂點W1、W2和和W3 的子圖。的子圖

13、。訪問頂點訪問頂點 V0 ：for (W1、W2、W3 ) 若若該鄰接點該鄰接點Wi未被訪問過未被訪問過， 則則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。V0w1SG1SG2SG3w2w3w2第41頁/共76頁算法分析算法分析1. 深度優(yōu)先搜索遍歷連通圖的過程類似深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；于樹的先根遍歷；解決的辦法：設(shè)立一個一維數(shù)組，用來解決的辦法：設(shè)立一個一維數(shù)組，用來記錄每個頂點是否被訪問過，即記錄每個頂點是否被訪問過，即 “訪問訪問標(biāo)志標(biāo)志 visitedw”。2. 如何判別如何判別V0的鄰接點是否被訪問？的鄰接點是否被訪問？第42頁/共76頁第4

14、3頁/共76頁42123123124(a)(b)31451672843528563867387847856Vi5678連通圖連通圖G及其鄰接表及其鄰接表第44頁/共76頁V1V2V4V8V5V6V3V7。第45頁/共76頁第46頁/共76頁n第47頁/共76頁adjvex=0)ndfs(G,p-adjvex);第48頁/共76頁nf o r ( v = 1 ; v adjvex=0) 第58頁/共76頁n第59頁/共76頁若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作

15、起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。非連通圖的廣度優(yōu)先搜索遍歷需多次調(diào)用非連通圖的廣度優(yōu)先搜索遍歷需多次調(diào)用bfs算法。每調(diào)用一次算法。每調(diào)用一次bfs得到的頂點集合恰為圖中一個連通分量的頂點集合，這些頂點集合中的頂點加上所有依附于這些頂點的邊，便構(gòu)成了非連通圖的一個連通分量。得到的頂點集合恰為圖中一個連通分量的頂點集合，這些頂點集合中的頂點加上所有依附于這些頂點的邊，便構(gòu)成了非連通圖的一個連通分量。非連通圖的廣度優(yōu)先搜索遍歷非連通圖的廣度優(yōu)先搜索遍歷第60頁/共76頁第61頁/共76頁例如，下面的圖示分別為連通圖例如，下面的圖示分別為連通圖G的深度優(yōu)先生成樹和廣度優(yōu)先的深度

16、優(yōu)先生成樹和廣度優(yōu)先生成樹。生成樹。第62頁/共76頁42123123124(a)(b)31451672843528563867387847856Vi5678連通圖連通圖G及其鄰接表及其鄰接表第63頁/共76頁1423586714235867(a)(b)連通圖連通圖G從從V1出發(fā)的兩種生成樹出發(fā)的兩種生成樹(a) 深度優(yōu)先生成樹；深度優(yōu)先生成樹；(b) 廣度優(yōu)先生成廣度優(yōu)先生成樹樹第64頁/共76頁第65頁/共76頁我們當(dāng)然希望選擇一個總耗費最我們當(dāng)然希望選擇一個總耗費最小的生成樹，即最小代價生成樹。小的生成樹，即最小代價生成樹。第66頁/共76頁第67頁/共76頁125643125643(a

17、)(b)726664775346532連通網(wǎng)及其最小生成樹連通網(wǎng)及其最小生成樹(a) 無向連通網(wǎng)；無向連通網(wǎng)；(b) 最小生成樹最小生成樹第68頁/共76頁第69頁/共76頁 每一對頂點之間的最短路徑每一對頂點之間的最短路徑(略略)迪杰斯特拉算法是著名的求解最迪杰斯特拉算法是著名的求解最短路徑的算法。短路徑的算法。第70頁/共76頁 求求從源點到其余各點的最短路徑從源點到其余各點的最短路徑的的算法的基本思想算法的基本思想: 依最短路徑的長度遞增的次序求得各依最短路徑的長度遞增的次序求得各條路徑。條路徑。源點源點v1其中，從源點到頂其中，從源點到頂點點v的最短路徑是指的最短路徑是指從源點到從源點

18、到v的所有路的所有路徑中權(quán)值之和最小徑中權(quán)值之和最小的那條路徑。的那條路徑。v2第71頁/共76頁v1 :無無v0v2:10v0 v4 v3:50v0 v4:30v0 v4 v3 v5:60v0v1v2v3v4v51006030201050510第72頁/共76頁在這條路徑上，在這條路徑上，必定只含一條弧必定只含一條弧，并且這，并且這條弧的條弧的權(quán)值最小。權(quán)值最小。 下一條路徑長度次短的路徑為路徑為：路徑長度上第一條最短路徑為路徑為： 它只可能有兩種情況：或者是它只可能有兩種情況：或者是直接從源點直接從源點到該點到該點(只含一條弧只含一條弧)； 或者是或者是從源點經(jīng)過頂從源點經(jīng)過頂點點v1，再到達(dá)該頂點，再到達(dá)該頂點(由兩條弧組成由兩條弧組成)。第73頁/共76頁其余最短路徑的特點