非線性數(shù)據(jù)結(jié)構(gòu)--圖-在線瀏覽
2024-09-11 14:45本頁面
【正文】 ,3,4,4,1} 1 3 2 4 G2 5/32 3. 邊和弧 ? 邊 : 無向圖中 頂點的偶對 ， 寫成 （ Vx， Vy）或 （ Vy， Vx） 。 ? 弧頭 : 弧的終點 ? 弧尾 : 弧的起點 弧 〈 Vx， Vy〉 弧尾 Vx 弧頭 Vy 6/32 4. 鄰接點 ? 頂點 : 圖中的結(jié)點 ? 鄰接點 : – 無向圖中 ， 若邊 (Ｖ x,Ｖ y)?E， 則Ｖ x、 Ｖ y互為鄰接點 。 Vx Vy Ｖ x、Ｖ y互為鄰接點 Vx Vy Ｖ y是Ｖ x的鄰接點 7/32 5. 頂點的度 ? 無向圖 :頂點的度 是連接該頂點的邊的條數(shù) 。 ? 有向圖 1)入度 :以某頂點為弧頭的弧的數(shù)目 。 2)出度 :以某頂點為弧尾的弧的數(shù)目 。 3)頂點的度 =入度 +出度 。 o o o o v1 v2 v3 v4 G1 1 3 4 2 G2 8/32 、長度 ? 路徑 圖中從頂點 Vx到頂點 Vy的頂點序列稱為從 Vx到 Vy的路徑 ,路徑可能是不唯一的 。 ? 長度 路徑上邊或弧的數(shù)目 。 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1 9/32 、權(quán) ? 權(quán) 若圖的邊或弧帶有與之相關(guān)的數(shù) ， 稱此數(shù)為該邊或弧的權(quán) 。 ? 網(wǎng) 帶權(quán)的圖稱為網(wǎng) 。 – 鄰接矩陣又分為 有向圖鄰接矩陣 和 無向圖鄰接矩陣 。 例 ， G1中 V2的度是 3。 例 ， G2中 ，V2的出度為 0， V1的入度為 1。 V1 V2 V3 V4 G5 2 3 5 7 16/32 二 . 鄰接表 ? 圖的鏈式存儲結(jié)構(gòu) ? 1) 為每個頂點建立一個單鏈表 ， ? 2) 第 i個單鏈表中包含頂點 Vi的所有鄰接頂點 。 o o o o v1 v2 v3 v4 G1 NULL V3 V2 NULL V2 NULL V2 V1 V1 V4 NULL V3 19/32 G2的鄰接表 1 2 3 4 NULL 2 3 1 NULL 1 3 2 4 G2 NULL 4 NULL 20/32 圖的遍歷 ? 圖的遍歷 從指定頂點出發(fā)訪問圖中每一個頂點 ， 使每個頂點都被訪問且只被訪問一次 ? 常用的遍歷方法： – 深度優(yōu)先遍歷法 – 廣度優(yōu)先遍歷法 21/32 一 . 深度優(yōu)先遍歷法 ? 算法： – 1) 訪問圖中某個指定頂點 V0； – 2) 從 V0出發(fā) ， 訪問與 V0鄰接的頂點 V1后 ，再從 V1出發(fā) ， 訪問與 V1鄰接且未被訪問過的頂點 V2。 – 3) 回退到尚未訪問過的頂點 ,從該頂點出發(fā) ， 重復 1)、 2)， 直到全部被訪問過的鄰接點都被訪問為止 。 23/32 二 . 廣度優(yōu)先遍歷算法 ? 先訪問第 1個頂點
數(shù)學相關(guān)推薦
鄂ICP備17016276號-1