幾種圖的存儲結構的比較_第1頁
幾種圖的存儲結構的比較_第2頁
幾種圖的存儲結構的比較_第3頁
幾種圖的存儲結構的比較_第4頁
幾種圖的存儲結構的比較_第5頁
已閱讀5頁，還剩13頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

幾種圖的存儲結構的比較2021/6/271圖的幾種主要存儲結構鄰接矩陣鄰接表十字鏈表鄰接多重表2021/6/272

無向圖的鄰接矩陣

實現方法：二維數組

優點：1.易判斷兩點間的關系

2容易求得頂點的度

2021/6/273有向圖的鄰接矩陣2021/6/274網的鄰接矩陣2021/6/275鄰接矩陣實現方法：二維數組優點：1.易判斷兩點間的關系2容易求得頂點的度缺點：占用空間大（邊數比頂數小得多）時間復雜度：O(n+n2+e)(n個頂點e條邊)2021/6/276無向圖的鄰接表

數據域

指針域鄰接點域

實現方法：鏈表

優點：1.節省空間

2容易求得頂點的度2021/6/277有向圖的鄰接表2021/6/278網的鄰接表2021/6/279鄰接表實現方法：鏈表優點：1.節省空間

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

2.不易得到頂點的入度時間復雜度：O(n+m)或O(n*m)2021/6/2710十字鏈表

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

思路：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結合。(1)開設弧結點，設5個域（每段弧是一個數據元素）(2)開設頂點結點，設3個域（每個頂點也是一個數據元素）2021/6/2711弧結點

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

data:頂點信息firstin:

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

以頂點為弧尾的第一條弧結點2021/6/2712十字鏈表實現方法：鏈表優點：1.空間要求較小

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

2.易判斷兩點間

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論