[理學(xué)]數(shù)據(jù)結(jié)構(gòu)第7章(編輯修改稿)
2025-02-15 14:46 本頁面
【文章內(nèi)容簡介】 存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖 G中的每個頂點(diǎn) vi，該方法將所有鄰接于 vi的頂點(diǎn) vj鏈成一個單鏈表，這個單鏈表就稱為頂點(diǎn) vi的鄰接表。再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。 27 在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)，如圖 710所示。 頂點(diǎn)域 邊表頭指針 鄰接點(diǎn)域 指針域 vertex link adjvex next 頂點(diǎn)表 邊表 圖 710 鄰接表表示的結(jié)點(diǎn)結(jié)構(gòu) adjvex data next 鄰接點(diǎn)域 指針域 邊上信息 網(wǎng)的邊表結(jié)構(gòu) 鄰接鏈表 28 鄰接鏈表 圖 711給出無向圖對應(yīng)的鄰接表表示。 4123132 4 ^4 ^1 4 ^12 3 ^41230 圖 711a 圖的鄰接表表示 123 429 鄰接鏈表 圖 711給出無向圖對應(yīng)的鄰接表表示。 1233 ^3 ^21 ^1230 圖 711b 圖的鄰接表表示 12330 鄰接鏈表 鄰接鏈表存儲圖具有如下特點(diǎn)： (1) 無向圖中，第 i個鏈表中的表結(jié)點(diǎn)數(shù)是頂點(diǎn) vi的度；有向圖中，第 i個鏈表中的表結(jié)點(diǎn)數(shù)是頂點(diǎn) vi的出度。 (2) 若無向圖有 n個頂點(diǎn)、 e條邊，則鄰接鏈表需 n個存儲單元和 2e個表結(jié)點(diǎn)。有向圖存儲 n個頂點(diǎn) e條邊，需要 n個存儲單元和 e個表結(jié)點(diǎn)。對于邊很少的圖，用鄰接鏈表比用鄰接矩陣要節(jié)省存儲單元。 (3) 在鄰接鏈表中，要確定兩個頂點(diǎn) vi和 vj之間是否有邊或弧相連，需要遍歷第 i個或第 j個單鏈表，不像鄰接矩陣那樣能方便地對頂點(diǎn)進(jìn)行隨機(jī)訪問。 31 圖 的 遍 歷 圖的遍歷是對具有圖狀結(jié)構(gòu)的數(shù)據(jù)線性化的過程。從圖中任一頂點(diǎn)出發(fā)，訪問輸出圖中各個頂點(diǎn)，并且使每個頂點(diǎn)僅被訪問一次，這樣得到頂點(diǎn)的一個線性序列，這一過程叫做圖的遍歷。 圖的遍歷是個很重要的算法，圖的連通性和拓?fù)渑判虻人惴ǘ际且詧D的遍歷算法為基礎(chǔ)的。 下面分別介紹圖的兩種遍歷方法：深度優(yōu)先搜索和廣度優(yōu)先搜索，這兩種方法既適用于無向圖也適用于有向圖。 32 深度優(yōu)先搜索 深度優(yōu)先搜索 (Depth First Search， DFS)遍歷類似于二叉樹的先序遍歷，其基本思想是： 初始時將圖中所有頂點(diǎn)標(biāo)記為未被訪問過，從圖中某個頂點(diǎn) v出發(fā)，訪問輸出該頂點(diǎn)，并將其標(biāo)記為已訪問，然后任選一個與 v鄰接且未被訪問的頂點(diǎn)w訪問輸出并標(biāo)記，再從與 w鄰接且未被訪問的頂點(diǎn) z出發(fā)，進(jìn)行深度優(yōu)先搜索，重復(fù)這一過程，若到達(dá)某頂點(diǎn)不存在未被訪問過的鄰接頂點(diǎn)時，則一直退回到最近被訪問過的且存在未被訪問過鄰接頂點(diǎn)的那個頂點(diǎn)再進(jìn)行深度優(yōu)先搜索，直至所有與 v有路徑相通的頂點(diǎn)都被訪問到，若此時圖中仍有未被訪問的頂點(diǎn)，則另選一個未被訪問的頂點(diǎn)，開始再做深度優(yōu)先搜索 33 深度優(yōu)先搜索 對于圖 712所示的有向圖其對應(yīng)的鄰接鏈表如圖 713所示 12343 ^2 ^1 ^123047657654 3 1 ^7 6 ^42 ^6 4 ^1234567得到的線性序列為 1,2,4,3,5,7,6 34 深度優(yōu)先搜索 深度優(yōu)先生成樹或森林：由圖中的全部頂點(diǎn)和深度優(yōu)先搜索所經(jīng)過的邊即構(gòu)成了深度優(yōu)先生成樹或森林。 對圖 生成森林如圖 。 123456735 廣度優(yōu)先搜索 廣度優(yōu)先搜索 (Breadth First Search， BFS)類似于二叉樹的層次遍歷。 其基本思想是： 初始時將圖中所有頂點(diǎn)標(biāo)記為未被訪問過，從圖中某個頂點(diǎn) v出發(fā)，訪問輸出該頂點(diǎn)，并將該頂點(diǎn)標(biāo)記為已訪問，然后依次訪問輸出與 v鄰接的未被訪問的所有頂點(diǎn)，并標(biāo)記為已訪問，再分別從這些鄰接點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索，直至圖中所有已被訪問的頂點(diǎn)的鄰接頂點(diǎn)都被訪問到。若此時圖中仍有未被訪問的頂點(diǎn)，則另選一個未被訪問的頂點(diǎn)，開始再做廣度優(yōu)先搜索。 36 廣度優(yōu)先搜索 下面仍以圖 ，說明廣度優(yōu)先搜索的過程，其存儲結(jié)構(gòu)為圖 。 12343 ^2 ^1 ^123047657654 3 1 ^7 6 ^42 ^6 4 ^1234567得到的線性序列為 1,2,4,3,5,7,6 37 廣度優(yōu)先搜索 對圖 生成森林如圖 。 1234567123456738 V1 V5 V2 V4 V8 V3 V6 V7 v1 → v2 → v4 → v8 → v5 → v3 → v6 → v7 v1→v 2→v 3→v 4→v 5→v 6→v 7 →v 8 39 最小生成樹 最小生成樹就是指在一個連通網(wǎng)的所有生成樹中，所有邊的代價之和最小的那棵生成樹。代價在
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1