非線性數(shù)據(jù)結(jié)構(gòu)--圖(編輯修改稿)
2024-08-28 14:45 本頁面
【文章內(nèi)容簡(jiǎn)介】 ? 5 ? 3 ? ? 2 ? ? ? ? ? ? ? 7 ? 4x4 G5的鄰接矩陣。 V1 V2 V3 V4 G5 2 3 5 7 16/32 二 . 鄰接表 ? 圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 1) 為每個(gè)頂點(diǎn)建立一個(gè)單鏈表 ， ? 2) 第 i個(gè)單鏈表中包含頂點(diǎn) Vi的所有鄰接頂點(diǎn) 。 17/32 二 . 鄰接表 ? 結(jié)點(diǎn)組成 ： ? 每個(gè)鏈表附設(shè)一個(gè)頭結(jié)點(diǎn) ， 結(jié)構(gòu)為： adjvex data nextarc 頂點(diǎn) Vi的鄰接點(diǎn) 與邊或弧有關(guān)的權(quán)值 指向 Vi的下一個(gè) 鄰接點(diǎn)的指針 Vexdata firstarc 指向 Vi單鏈表的第一個(gè)結(jié)點(diǎn) 存放 Vi信息 18/32 1. 無向圖的鄰接表 V1 V2 V3 V4 V2 頂點(diǎn) Vi的度恰好就是 第 i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。 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 圖的遍歷 ? 圖的遍歷 從指定頂點(diǎn)出發(fā)訪問圖中每一個(gè)頂點(diǎn) ， 使每個(gè)頂點(diǎn)都被訪問且只被訪問一次 ? 常用的遍歷方法： – 深度優(yōu)先遍歷法 – 廣度優(yōu)先遍歷法 21/32 一 . 深度優(yōu)先遍歷法 ? 算法： – 1) 訪問圖中某個(gè)指定頂點(diǎn) V0； – 2) 從 V0出發(fā) ， 訪問與 V0鄰接的頂點(diǎn) V1后 ，再?gòu)?V1出發(fā) ， 訪問與 V1鄰接且未被訪問過的頂點(diǎn) V2。 重復(fù)上述過程 ， 直到不存在未訪問過的鄰接點(diǎn)為止 。 – 3) 回退到尚未訪問過的頂點(diǎn) ,從該頂點(diǎn)出發(fā) ， 重復(fù) 1)、 2)， 直到全部被訪問過的鄰接點(diǎn)都被訪問為止 。 22/32 V1 V3 V2 V5 V4 V6 G6 深度優(yōu)先遍歷法舉例 遍歷過程 訪問頂點(diǎn) 所過邊 ?起點(diǎn) V1 V1 ?V1的第 1個(gè)鄰接點(diǎn) V3 V3 （ V1， V3） ?V3的第 1個(gè)鄰接點(diǎn) V1已訪問，取下 一個(gè)鄰接點(diǎn) V5 V5 （ V3， V5） ?V5的第 1個(gè)鄰接點(diǎn) V3已訪問，取下 一個(gè)鄰接點(diǎn) V2 V2 （ V5， V2） ?V2的兩個(gè)鄰接點(diǎn)均被訪問， 回退到 V5， V5的鄰接點(diǎn)均被訪問，
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1