幾種圖的存儲結構的比較

幾種圖的存儲結構的比較第一頁，共十八頁，2022年，8月28日圖的幾種主要存儲結構鄰接矩陣鄰接表十字鏈表鄰接多重表第二頁，共十八頁，2022年，8月28日

無向圖的鄰接矩陣

實現方法：二維數組

優(yōu)點：1.易判斷兩點間的關系

2容易求得頂點的度

第三頁，共十八頁，2022年，8月28日有向圖的鄰接矩陣第四頁，共十八頁，2022年，8月28日網的鄰接矩陣第五頁，共十八頁，2022年，8月28日鄰接矩陣實現方法：二維數組優(yōu)點：1.易判斷兩點間的關系2容易求得頂點的度缺點：占用空間大（邊數比頂數小得多）時間復雜度：O(n+n2+e)(n個頂點e條邊)第六頁，共十八頁，2022年，8月28日無向圖的鄰接表

數據域

指針域鄰接點域實現方法：鏈表優(yōu)點：1.節(jié)省空間2容易求得頂點的度第七頁，共十八頁，2022年，8月28日有向圖的鄰接表第八頁，共十八頁，2022年，8月28日網的鄰接表第九頁，共十八頁，2022年，8月28日鄰接表實現方法：鏈表優(yōu)點：1.節(jié)省空間

2.易得到頂點的出度缺點：1.不易判斷兩點間的關系

2.不易得到頂點的入度時間復雜度：O(n+m)或O(n*m)第十頁，共十八頁，2022年，8月28日十字鏈表

它是有向圖的另一種鏈式存儲結構。

思路：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結合。(1)開設弧結點，設5個域（每段弧是一個數據元素）(2)開設頂點結點，設3個域（每個頂點也是一個數據元素）第十一頁，共十八頁，2022年，8月28日tailvexheadvexhlinktlinkinfo弧結點

頂點結點tailvex:弧尾頂點位置headvex:弧頭頂點位置hlink:弧頭相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息datafirstinfirstout

data:頂點信息firstin:

以頂點為弧頭的第一條弧結點firstout:

以頂點為弧尾的第一條弧結點第十二頁，共十八頁，2022年，8月28日十字鏈表實現方法：鏈表優(yōu)點：1.空間要求較小

2.易求得頂點的出度和入度缺點：結構較復雜時間復雜度：O(n+m)或O(n*m)第十三頁，共十八頁，2022年，8月28日鄰接多重表這是無向圖的另一種鏈式存儲結構，當對邊操作時建議采用此種結構存儲。（1）設立邊結點，6個域（每條邊是一個數據元素）（2）設立頂點結點，2個域（每個頂點也是一個數據元素）第十四頁，共十八頁，2022年，8月28日邊結點markivexilinkjvexjlinkinfomark：標志域，標記該邊是否被搜索過。ivex，jvex:邊依附的兩個頂點位置ilink:指向下一條依附頂點i的邊位置Jlink：指向下一條依附頂點j的邊位置info:邊信息頂點結點datafirstedgedata:存儲頂點信息firstedge:依附頂點的第一條邊結點第十五頁，共十八頁，2022年，8月28日鄰接多重表實現方式：鏈表優(yōu)點：1.節(jié)省空間

2.易判斷兩點間的關系缺點：結構較復雜時間復雜度：O(n+m)或O(n*m)第十六頁，共十八頁，2022年，8月28日名稱實現方法優(yōu)點缺點時間復雜度鄰接矩陣二維數組1.易判斷兩點間的關系2.容易求得頂點的度占用空間大O(n2+m*n)鄰接表鏈表1.節(jié)省空間2.易得到頂點的出度1.不易判斷兩點間的關系2.不易得到頂點的入度O(n+m)或O(n*m)十字鏈表鏈表1.空間要求較小2.易求得頂點的出度和入度結構較復雜O(n+m)或O(