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

幾種圖的存儲結(jié)構(gòu)的比較2021/6/271圖的幾種主要存儲結(jié)構(gòu)鄰接矩陣鄰接表十字鏈表鄰接多重表2021/6/272

無向圖的鄰接矩陣

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

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

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

2021/6/273有向圖的鄰接矩陣2021/6/274網(wǎng)的鄰接矩陣2021/6/275鄰接矩陣實(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條邊)2021/6/276無向圖的鄰接表

數(shù)據(jù)域

指針域鄰接點(diǎn)域

實(shí)現(xiàn)方法：鏈表

優(yōu)點(diǎn)：1.節(jié)省空間

2容易求得頂點(diǎn)的度2021/6/277有向圖的鄰接表2021/6/278網(wǎng)的鄰接表2021/6/279鄰接表實(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)2021/6/2710十字鏈表

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

思路：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結(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ù)元素）2021/6/2711弧結(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)為弧尾的第一條弧結(jié)點(diǎn)2021/6/2712十字鏈表實(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)2021/6/2713鄰接多重表這是無向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，當(dāng)對邊操作時(shí)建議采用此種結(jié)構(gòu)存儲。（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ù)元素）2021/6/2714邊結(jié)點(diǎn)mark：標(biāo)志域，標(biāo)記該邊是否被搜索過。ivex，jvex:邊依附的兩個(gè)頂點(diǎn)位置ilink:指向下一條依附頂點(diǎn)i的邊位置Jlink：指向下一條依附頂點(diǎn)j的邊位置info:邊信息頂點(diǎn)結(jié)點(diǎn)data:存儲頂點(diǎn)信息firstedge:依附頂點(diǎn)的第一條邊結(jié)點(diǎn)2021/6/2715鄰接多重表實(shí)現(xiàn)方式：鏈表優(yōu)點(diǎn)：1.節(jié)省空間

2.易判斷兩點(diǎn)間