非線性數(shù)據(jù)結(jié)構(gòu)--圖-文庫吧資料
2024-08-14 14:45本頁面
【正文】 V5 （ V3， V5） ?V5的第 1個鄰接點 V3已訪問，取下 一個鄰接點 V2 V2 （ V5， V2） ?V2的兩個鄰接點均被訪問， 回退到 V5， V5的鄰接點均被訪問， 回退到 V3， V3的鄰接點均被訪問 ， 回退到 V1， V1的另一個鄰接點 V4 未被訪問 V4 （ V1， V4） ?V4的第一個鄰接點 V1已被訪問， 另一個鄰接點 V6未被訪問 V6 （ V4， V6） ?V6的鄰接點被訪問，回退到 V4 ?V4的鄰接點均被訪問 ?回退到 V1，返回到出發(fā)點，遍歷結(jié)束。 重復(fù)上述過程 ， 直到不存在未訪問過的鄰接點為止 。 17/32 二 . 鄰接表 ? 結(jié)點組成 ： ? 每個鏈表附設(shè)一個頭結(jié)點 ， 結(jié)構(gòu)為： adjvex data nextarc 頂點 Vi的鄰接點 與邊或弧有關(guān)的權(quán)值 指向 Vi的下一個 鄰接點的指針 Vexdata firstarc 指向 Vi單鏈表的第一個結(jié)點 存放 Vi信息 18/32 1. 無向圖的鄰接表 V1 V2 V3 V4 V2 頂點 Vi的度恰好就是 第 i個單鏈表中的結(jié)點數(shù)。 G1 A= = 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 3 2 4 G2 15/32 ? 定義： Wij （ Vi,Vj） 或 〈 Vi,Vj〉 ? E A[i][j] = ? （ Vi,Vj） 或 〈 Vi,Vj〉 ? E = V1 V2 V3 V4 A== ? 5 ? 3 ? ? 2 ? ? ? ? ? ? ? 7 ? 4x4 G5的鄰接矩陣。 – 有向圖 – 第 i行的元素之和為頂點 Vi的出度；第 j列的元素之和為頂點 Vj的入度 。 12/32 ? 定義 設(shè)圖 G=(V,E)是有 n(n?1)個頂點的圖，則 G的鄰接矩陣是具有下述性質(zhì)的對稱陣： 1 (Vi， Vj） ? E A[i][j]=A[j][i] = 0 (Vi， Vj） ? E G1的鄰接矩陣為： = 1 2 3 4 A= = 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 4x4 o o o o v1 v2 v3 v4 G1 13/32 ? 定義 設(shè)圖 G=（ V， E） 是有 n（ n ? 1） 個頂點的圖
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1