幾種圖的存儲(chǔ)結(jié)構(gòu)的比較

幾種圖的存儲(chǔ)結(jié)構(gòu)的比較第一頁，共十八頁，編輯于2023年，星期日?qǐng)D的幾種主要存儲(chǔ)結(jié)構(gòu)鄰接矩陣鄰接表十字鏈表鄰接多重表第二頁，共十八頁，編輯于2023年，星期日

無向圖的鄰接矩陣

實(shí)現(xiàn)方法：二維數(shù)組

優(yōu)點(diǎn)：1.易判斷兩點(diǎn)間的關(guān)系

2容易求得頂點(diǎn)的度

第三頁，共十八頁，編輯于2023年，星期日有向圖的鄰接矩陣第四頁，共十八頁，編輯于2023年，星期日網(wǎng)的鄰接矩陣第五頁，共十八頁，編輯于2023年，星期日鄰接矩陣實(shí)現(xiàn)方法：二維數(shù)組優(yōu)點(diǎn)：1.易判斷兩點(diǎn)間的關(guān)系2容易求得頂點(diǎn)的度缺點(diǎn)：占用空間大（邊數(shù)比頂數(shù)小得多）時(shí)間復(fù)雜度：O(n+n2+e)(n個(gè)頂點(diǎn)e條邊)第六頁，共十八頁，編輯于2023年，星期日無向圖的鄰接表

數(shù)據(jù)域

指針域鄰接點(diǎn)域?qū)崿F(xiàn)方法：鏈表優(yōu)點(diǎn)：1.節(jié)省空間2容易求得頂點(diǎn)的度第七頁，共十八頁，編輯于2023年，星期日有向圖的鄰接表第八頁，共十八頁，編輯于2023年，星期日網(wǎng)的鄰接表第九頁，共十八頁，編輯于2023年，星期日鄰接表實(shí)現(xiàn)方法：鏈表優(yōu)點(diǎn)：1.節(jié)省空間

2.易得到頂點(diǎn)的出度缺點(diǎn)：1.不易判斷兩點(diǎn)間的關(guān)系

2.不易得到頂點(diǎn)的入度時(shí)間復(fù)雜度：O(n+m)或O(n*m)第十頁，共十八頁，編輯于2023年，星期日十字鏈表

它是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。(1)開設(shè)弧結(jié)點(diǎn)，設(shè)5個(gè)域（每段弧是一個(gè)數(shù)據(jù)元素）(2)開設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）第十一頁，共十八頁，編輯于2023年，星期日tailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)

頂點(diǎn)結(jié)點(diǎn)tailvex:弧尾頂點(diǎn)位置headvex:弧頭頂點(diǎn)位置hlink:弧頭相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息datafirstinfirstout

data:頂點(diǎn)信息firstin:

以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)firstout:

以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn)第十二頁，共十八頁，編輯于2023年，星期日十字鏈表實(shí)現(xiàn)方法：鏈表優(yōu)點(diǎn)：1.空間要求較小

2.易求得頂點(diǎn)的出度和入度缺點(diǎn)：結(jié)構(gòu)較復(fù)雜時(shí)間復(fù)雜度：O(n+m)或O(n*m)第十三頁，共十八頁，編輯于2023年，星期日鄰接多重表這是無向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，當(dāng)對(duì)邊操作時(shí)建議采用此種結(jié)構(gòu)存儲(chǔ)。（1）設(shè)立邊結(jié)點(diǎn)，6個(gè)域（每條邊是一個(gè)數(shù)據(jù)元素）（2）設(shè)立頂點(diǎn)結(jié)點(diǎn)，2個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）第十四頁，共十八頁，編輯于2023年，星期日邊結(jié)點(diǎn)markivexilinkjvexjlinkinfomark：標(biāo)志域，標(biāo)記該邊是否被搜索過。ivex，jvex:邊依附的兩個(gè)頂點(diǎn)位置ilink:指向下一條依附頂點(diǎn)i的邊位置Jlink：指向下一條依附頂點(diǎn)j的邊位置info:邊信息頂點(diǎn)結(jié)點(diǎn)datafirstedgedata:存儲(chǔ)頂點(diǎn)信息firstedge:依附頂點(diǎn)的第一條邊結(jié)點(diǎn)第十五頁，共十八頁，編輯于2023年，星期日鄰接多重表實(shí)現(xiàn)方式：鏈表優(yōu)點(diǎn)：1.節(jié)省空間

2.易判斷兩點(diǎn)間的關(guān)系缺點(diǎn)：結(jié)構(gòu)較復(fù)雜時(shí)間復(fù)雜度：O(n+m)或O(n*m)第十六頁，共十八頁，編輯于2023年，星期日名稱實(shí)現(xiàn)方法優(yōu)點(diǎn)缺點(diǎn)時(shí)間復(fù)雜度鄰接矩陣二維數(shù)組1.易判斷兩點(diǎn)間的關(guān)系2.容易求得頂點(diǎn)的度占用空間大O(n2+m*n)鄰接表鏈表1.節(jié)省空間2.易得到頂點(diǎn)的出度1.不易判斷兩點(diǎn)間的關(guān)系2.不易得到頂點(diǎn)的入度O(n+m)或O(n*m)十字鏈表鏈表1.空間要求較小2.易求得頂點(diǎn)的出度和入度結(jié)構(gòu)較復(fù)雜O(n+m)或O(n