數(shù)據(jù)結(jié)構(gòu)(Java版)圖1(圖基礎(chǔ)及圖遍歷)課件

1、圖主要內(nèi)容圖的基本概念圖的存儲圖的連通性圖的生成樹圖遍歷 實(shí)踐項目：圖遍歷演示程序圖的應(yīng)用公交網(wǎng)絡(luò)系統(tǒng)最短路徑查詢物流系統(tǒng)運(yùn)輸系統(tǒng)基本概念圖 ： 圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph( V, E ) 其中 V = x | x 某個數(shù)據(jù)對象 是頂點(diǎn)的有窮非空集合； E = (x, y) | x, y V 或 E = | x, y V & Path (x, y) 是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。Path (x, y)表示從 x 到 y 的一條單向通路, 它是有方向的。有向圖和無向圖00001111222265433 無向圖：圖的每條邊

2、都沒有方向，即邊的2個頂點(diǎn)沒有次序關(guān)系（1，0），（0，1）是同一條邊 有向圖：圖的每條邊都是有方向的，即邊的2個頂點(diǎn)有次序關(guān)系。，是2條邊帶權(quán)圖（也稱網(wǎng)）權(quán)：圖的邊上的具有特定含義的數(shù)值稱為權(quán)。帶權(quán)圖：圖的每條邊都帶有一個權(quán)，這樣的圖稱為帶權(quán)圖，也稱網(wǎng)。BACD95234BAC523子圖鄰接頂點(diǎn) 如果 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點(diǎn)。子圖 設(shè)有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 EE, 則稱 圖G 是 圖G 的子圖。0123子圖0130123023頂點(diǎn)的度和路徑、路徑長度0123與頂點(diǎn)關(guān)聯(lián)的邊數(shù)。頂點(diǎn)0的度為201的路徑和路徑長

3、度：0-3-2-1，路徑長度為30-1，路徑長度為10-3-2-1-0-1，路徑長度為5BACD9523入度為2出度為1連通圖與 連通分量在無向圖中，如果任意2個頂點(diǎn)之間都有路徑，則稱該無向圖是連通圖。無向圖的極大連通子圖稱為連通分量。 強(qiáng)連通圖與強(qiáng)連通分量 在有向圖中，如果任意2個頂點(diǎn)之間都存在可到達(dá)的路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極大連通子圖稱為該有向圖的強(qiáng)連通分量。生成樹一個n個頂點(diǎn)的連通圖的生成樹是一個極小連通子圖，它含有圖中所有的頂點(diǎn)，但具有足以構(gòu)成一棵樹的n-1條邊。圖的存儲鄰接矩陣鄰接表鄰接矩陣 (Adjacency Matrix）在圖的鄰接矩陣表示中，有一個記錄各個頂點(diǎn)

4、信息的頂點(diǎn)表，還有一個表示各個頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖 A = (V, E)是一個有 n 個頂點(diǎn)的圖, 圖的鄰接矩陣是一個二維數(shù)組 A.edgenn，定義：無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123012鄰接表 (Adjacency List)1.無向圖的鄰接表 同一個頂點(diǎn)發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn)), 結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo) adjvex 和指針 nextarc。ABCDdata firstarcABCD0123adjvex nextarc130210adjvex nextarc2.有向圖的鄰接表和逆鄰接表ABCdata firs

5、tarcABC012鄰接表 (出邊表)ABC012逆鄰接表 (入邊表)102011adjvex nextarcadjvex nextarcadjvex nextarcdata firstarcBACD69528ABCD01231 53 62 83 21 9(出邊表)(頂點(diǎn)表)Adjvex info nextarcdata firstarc3.網(wǎng)絡(luò) (帶權(quán)圖) 的鄰接表圖的遍歷從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一 些邊訪遍圖中所有的頂點(diǎn)，且使每個頂點(diǎn)僅被訪問一次，就叫做圖的遍歷 ( Graph Traversal )。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個頂點(diǎn)之后可能

6、會沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。圖的遍歷的分類:深度優(yōu)先搜索遍歷 DFS (Depth First Search)廣度優(yōu)先搜索 遍歷 BFS (Breadth First Search)深度優(yōu)先搜索遍歷 - DFSACDEGBFIHACDEGBFIH123456789123456789前進(jìn)回退深度優(yōu)先搜索過程 深度優(yōu)先生成樹 DFS 在訪問圖中某一起始頂點(diǎn) v 后, 由 v 出發(fā), 訪問它的任一鄰接頂點(diǎn) w1; 再從 w1 出發(fā),訪問與 w1鄰 接但還沒有訪問過的頂點(diǎn) w2; 然后再從 w2 出發(fā), 進(jìn)行類似的訪問, 如此進(jìn)行下去, 直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。接著

7、, 退回一步, 退到前一次剛訪問過的頂點(diǎn), 看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有, 則訪問此頂點(diǎn), 之后再從此頂點(diǎn)出發(fā), 進(jìn)行與前述類似的訪問; 如果沒有, 就再退回一步進(jìn)行搜索。重復(fù)上述過程, 直到連通圖中所有頂點(diǎn)都被訪問過為止。深度優(yōu)先搜索遍歷( DFS)基本思想廣度優(yōu)先搜索 遍歷(BFS)ACDEGBFIHACDEGBFH123456789123456789 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹IBFS在訪問了起始頂點(diǎn) v 之后, 由 v 出發(fā), 依次訪問 v 的各個未被訪問過的鄰接頂點(diǎn) w1, w2, , wt, 然后再順序訪問 w1, w2, , wt 的所有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點(diǎn)， 如此做下去，直到圖中所有頂點(diǎn)都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程, 每向前走一步可能訪問一批頂點(diǎn), 不像深度優(yōu)先搜索那樣有往回退的情況。因此, 廣度優(yōu)先搜索不是一個遞歸的過程。廣度優(yōu)先搜索遍歷(BFS)基本思想實(shí)踐項目設(shè)計步驟定義圖形結(jié)點(diǎn) GraphNode.java定義操作 GraphADT.java定義圖形結(jié)構(gòu) Graph.java使用圖形結(jié)構(gòu) GraphUser.java圖遍歷演示程序 UML圖主程序運(yùn)行界面