第3章-數據結構-資料下載頁
2025-08-05 19:42本頁面
【正文】 Vi與 Vj之間有一條邊 (Vi, Vj)，則稱 Vi與 Vj鄰接，稱邊 (Vi, Vj)依附于頂點 Vi, Vj；依附于頂點邊的個數稱為 度 ? 在有向圖中，進入該頂點的有向邊的個數為入度，由該頂點引出的有向邊的個數為出度， 度 =入度 +出度 44 167。 圖 V2 V1 V3 V4 V={V1,V2,V3,V4} E={(V1,V2), (V2,V3), (V1,V4), (V2,V4) (V3,V4)} V2 V1 V3 V4 V={V1,V2,V3,V4} E={(V1,V2), (V1,V4), (V2,V3) , (V3,V2) (V4,V3)} 度為 3 度為 2 出度為 1 入度為 2 度為 3 45 167。 圖 二、存儲 ? 相鄰矩陣表示法 ? 若 G是一個具有 n個節(jié)點的有向圖，則 G的相鄰矩陣為： A[i, j] = 1 若 (Vi,Vj)或 (Vj,Vi)是圖 G的邊 0 若 (Vi,Vj)或 (Vj,Vi)不是圖 G的邊 { V2 V1 V3 V4 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 V2 V1 V3 V4 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 46 167。 圖 ? 鄰接表表示法 ? 節(jié)點表 + 邊表 ? 節(jié)點表：數據域 + 指針域（指向此節(jié)點的邊表） ? 邊表：每個表目對應一條邊，包括與此邊相關聯的另一個節(jié)點序號 + 指向下一個表目的指針 V2 V1 V3 V4 V1 V2 V3 V4 2 4 ? 1 3 2 4 ? 4 ? 1 2 3 ? 47 167。 圖 V2 V1 V3 V4 V1 V2 V3 V4 2 4 ? 3 ? 2 ? 3 ? V1 ? V2 V3 V4 1 3 ? 2 4 ? 1 ? 出邊表 入邊表 48 167。 圖 三、圖的遍歷 ? 遍歷： 從圖中某一點出發(fā)訪問圖中其余頂點，或當給定的圖是連通圖，則從圖中任意一點出發(fā)順著某些邊可以訪問到該圖中的所有的頂點，且使每一個頂點僅被訪問一次。 ? 深度優(yōu)先搜索： ? 廣度優(yōu)先搜索： 49 167。 圖 三、圖的遍歷 ? 深度優(yōu)先搜索： 設從圖Ｇ＝（Ｖ，Ｅ）中某一頂點Ｖ ０ 出發(fā)，在訪問了任意一個和Ｖ ０ 鄰接的頂點Ｗ １ 后，出發(fā)訪問和Ｗ １ 鄰接且未被訪問過的任意頂點Ｗ ２ 。然后，從Ｗ ２ 出發(fā)進行如上的訪問。重復這種訪問，直到一個頂點的所有鄰接點都被訪問過為止，接著退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)，重復上述搜索過程，直到所有的被訪問過的頂點的鄰接點都已被訪問到為止。 1 2 3 4 5 6 7 8 Ｖ １ → Ｖ ２ → Ｖ ４ → Ｖ ８ → Ｖ ５ → Ｖ ６ → Ｖ ３ → Ｖ ７ 50 167。 圖 三、圖的遍歷 ?廣度優(yōu)先搜索 從圖Ｇ中某一頂點Ｖ 0出發(fā)，首先依次訪問Ｖ 0的鄰接的頂點Ｗ １ ，Ｗ ２ ， … ，Ｗ ｔ 。然后，再順序訪問Ｗ １ ，Ｗ ２ ， … ，Ｗ ｔ 的所有的鄰接點（已被訪問過的頂點除外），再從這些被訪問的點出發(fā)，逐次進行訪問，依次類推，直到所有頂點都被訪問到為止。 Ｖ １ → Ｖ ２ → Ｖ ３ → Ｖ ４ → Ｖ ５ → Ｖ ６ → Ｖ ７ → Ｖ ８ 1 2 3 4 5 6 7
教學課件相關推薦
鄂ICP備17016276號-1