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