[計算機軟件及應用]數(shù)據結構圖a-資料下載頁
2024-12-08 02:27本頁面
【正文】 ，如求頂點的入度、出度等。 Firstout Firstin data 頂點結點 info tlink hlink headvex tailvex 弧結點 0 v1 1 v2 2 v3 3 v4 0 1 2 3 0 1 0 ^ ^ 2 此無權圖未開第 4分量 空間復雜度和建表的時間復雜度都與鄰接表相同 。 v1, v2 v1, v3 v3, v1 v3, v4 v4, v1 v4, v2 31 這是 無向圖 的另一種存儲結構，當 對邊操作 時建議采用此種結構存儲。 設立 邊結點， 6個域 （每條邊是一個數(shù)據元素） 設立 頂點結點， 2個域 （每個頂點也是一個數(shù)據元素） mark ivex ilink jvex jlink info 邊結點 data : 存儲頂點信息 Firstedge : 依附頂點的第一條邊結點 data Firstedge 頂點結點 4. 鄰接多重表表示法 mark： 標志域 ivex， jvex : 邊依附的兩個頂點位置 ilink: 指向下一條依附頂點 i 的邊位置 jlink。 指向下一條依附頂點 j 的邊位置 info: 邊信息 n個頂點的集合怎樣儲存？ 仍用順序存儲結構 32 1 2 1 ^ 4 2 3 2 ^ 4 3 ^ 4 ^ v1 v2 v3 v5 v4 例：畫出無向圖的鄰接多重表 鄰接多重表優(yōu)點： 容易操作，如求頂點的度等。 0 v1 1 v2 2 v3 3 v4 4 v5 0 1 2 3 4 Firstedge data 頂點結點 mark info jlink jvex ilink ivex 邊結點 空間復雜度和建表的時間復雜度都與鄰接表相同。 0 1 ^… 0 3 此無權圖未開第 6分量 (v1,v2) (v1,v4) (v2,v3) (v2,v5) (v3,v4) (v3,v5) (v4,v5) 33 一、深度優(yōu)先搜索 二、廣度優(yōu)先搜索 圖的遍歷 遍歷定義： 從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做 圖的遍歷 ，它是 圖的 基本運算 。 遍歷實質： 找每個頂點的鄰接點的過程。 圖的特點： 圖中可能存在 回路 ，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點 。 解決思路： 可設置一個 輔助數(shù)組 visited [n ]，用來標記每個被訪問過的頂點。它的初始狀態(tài)為 0，在圖的遍歷過程中，一旦某一個頂點 i 被訪問，就立即改 visited [i]為 1，防止它被多次訪問。 圖常用的遍歷： 怎樣避免重復訪問？ 34 深度優(yōu)先搜索（遍歷）步驟： 詳細歸納： ?在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問 它的任一鄰接頂點 w1； ?再從 w1 出發(fā)，訪問 與 w1鄰接 但還 未被訪問 過的頂點 w2； ?然后再從 w2 出發(fā)，進行類似的訪問， … ?如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。 ?接著， 退回一步， 退到前一次剛訪問過的頂點 ，看是否還有其它未被訪問的鄰接頂點。 如果有， 則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問； 如果沒有，就 再退回一步 進行搜索 。重復上述過程，直到連通圖中所有頂點都被訪問過為止。 簡單歸納： ? 訪問起始點 v。 ? 若 v的第 1個鄰接點沒訪問過，深度遍歷此鄰接點； ? 若當前鄰接點已訪問過，再找 v的第 2個鄰接點重新遍歷。 35 一、深度優(yōu)先搜索 ( DFS ) 基本思想： —— 仿樹的先序遍歷過程 。 Depth_First Search v1 v1 v2 v3 v8 v7 v6 v4 v5 DFS 結果 例 1： → → → → → → → v2 v4 v8 v5 v3 v6 v7 例 2： v2 → v1 → v3 → v5 → DFS 結果 v4 → v6 起點 起點 遍歷步驟 應退回到 V8，因為 V2已有標記 應退回到 V3，因為 V2已有標記 36 討論 1： 計算機如何實現(xiàn) DFS？ 1 2 3 4 5 6 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0 5 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 DFS 結果 鄰接矩陣 A 輔助數(shù)組 visited [n ] 起點 —— 開輔助數(shù)組 visited [n ]！ 例： 1 1 11 11 11 11 11v2 → → → → → v1 v3 v5 v4 v6 請注意逐級回退是遞歸概念
教學課件相關推薦
鄂ICP備17016276號-1