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

1、關(guān)于幾種圖的存儲(chǔ)結(jié)構(gòu)的比較第1頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四圖的幾種主要存儲(chǔ)結(jié)構(gòu)鄰接矩陣鄰接表十字鏈表鄰接多重表第2頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四 無(wú)向圖的鄰接矩陣 實(shí)現(xiàn)方法：二維數(shù)組 優(yōu)點(diǎn)：1.易判斷兩點(diǎn)間的關(guān)系 2容易求得頂點(diǎn)的度第3頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四有向圖的鄰接矩陣第4頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四網(wǎng)的鄰接矩陣第5頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四鄰接矩陣實(shí)現(xiàn)方法：二維數(shù)組優(yōu)點(diǎn)：1.易判斷兩點(diǎn)間的關(guān)系 2容易求得頂點(diǎn)的度缺點(diǎn)：占用空間大（邊數(shù)

2、比頂數(shù)小得多）時(shí)間復(fù)雜度：O(n+n2+e) (n個(gè)頂點(diǎn) e條邊)第6頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四 無(wú)向圖的鄰接表 數(shù)據(jù)域 指針域 鄰接點(diǎn)域 實(shí)現(xiàn)方法：鏈表 優(yōu)點(diǎn)：1.節(jié)省空間 2容易求得頂點(diǎn)的度第7頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四有向圖的鄰接表第8頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四網(wǎng)的鄰接表第9頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四鄰接表實(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)第10

3、頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四十字鏈表 它是有向圖的另一種鏈?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ù)元素）第11頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四弧結(jié)點(diǎn) 頂點(diǎn)結(jié)點(diǎn)tailvex: 弧尾頂點(diǎn)位置 headvex: 弧頭頂點(diǎn)位置hlink: 弧頭相同的下一弧位置tlink: 弧尾相同的下一弧位置info: 弧信息 data : 頂點(diǎn)信息firstin : 以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)firstout: 以頂點(diǎn)為弧尾的第一條

4、弧結(jié)點(diǎn)第12頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四十字鏈表實(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)第13頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四鄰接多重表這是無(wú)向圖的另一種鏈?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ù)元素）第14頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四邊結(jié)點(diǎn)mark：標(biāo)志域，標(biāo)記該邊是否被搜索過(guò)。ivex， jvex : 邊依附的兩個(gè)頂點(diǎn)位置 ilink: 指向下一條依附頂點(diǎn) i 的邊位置Jlink： 指向下一條依附頂點(diǎn) j 的邊位置info: 邊信息頂點(diǎn)結(jié)點(diǎn)data : 存儲(chǔ)頂點(diǎn)信息firstedge : 依附頂點(diǎn)的第一條邊結(jié)點(diǎn)第15頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四鄰接多重表實(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)第16頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四第17頁(yè)