iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 15
1
Software Development

擁抱「資料結構」的「演算法」系列 第 15

擁抱「資料結構」的「演算法」(15) - 圖形表示法

前言

對圖形有基本的認識之後,我們要來了解圖形是如何被儲存的,就像二元樹會以陣列或串列儲存,那圖形會以什麼方式儲存呢,讓我們一起來看看吧


圖形表示法

圖形表示法有四種,以下會逐一介紹

  • 相鄰矩陣 (Adjacency Matrix)
  • 相鄰串列 (Adjacency List)
  • 相鄰多元串列 (Adjacency Multilist)
  • 索引表 (Index Table)

相鄰矩陣 (Adjacency Matrix)

定義:
有一圖形,有n 個頂點,則可利用 n * n2 維陣列來表示,如下圖頂點有 4 個,則可以用 4 * 4 的二維矩陣表示,逐一觀察每個頂點與其它頂點有沒有,並套用下列規則填滿矩陣中的值
https://ithelp.ithome.com.tw/upload/images/20200929/20129841d3Wsb27IBc.png

陣列的值與圖形的關係:

  • 陣列中 [ 1, 2 ] 的值 = 1,則代表圖形中的頂點 1頂點 2之間有一條邊
  • 陣列中 [ 3, 2 ] 的值 = 0,則代表圖形中的頂點 3頂點 2之間沒有邊

步驟:

  1. 頂點 1 與頂點 2、頂點 3 、頂點 4 之間都有邊,則將矩陣中的 [ 1, 2 ], [ 1, 3 ], [ 1, 4 ] 填 1
  2. 頂點 2 與頂點 1、頂點 4 之間都有邊,則將矩陣中的 [2, 1 ], [ 2, 4 ] 填 1
  3. 頂點 3 與頂點 1、頂點 4 之間都有邊,則將矩陣中的 [ 3, 1 ], [ 3, 4 ] 填 1
  4. 頂點 4 與頂點 1、頂點 2、頂點 3 之間都有邊,則將矩陣中的 [ 4, 1 ], [ 4, 2 ], [ 4, 3 ] 填 1
  5. 其它位置填 0, 表示沒有邊存在

特性:

  • 無向圖的矩陣是對稱的,即 [ 1, 2 ] = [ 2, 1 ],對角線皆為 0,有向圖不一定
  • 無向圖的矩陣是對稱的,所以只要保存矩陣的上三角下三角即可,故可僅需 n ( n - 1 ) / 2 的空間

分支度:

  • 有向圖:某一頂點 i 的分支度就是第 i 列元素和,例如:頂點 1 的分支度 = 0 + 1 + 1 + 1 = 3
  • 無向圖:
    • 出分支度:第 i 列的元素和,如下圖的頂點3出分支度就是第 3 列的元素和 = 1 + 1 = 2
    • 入分支度:第 i 行的元素和,如下圖的頂點3入分支度就是第 3 行的元素和 = 1 + 0 + 0 = 1 ,另外下圖的矩陣不是對稱矩陣

https://ithelp.ithome.com.tw/upload/images/20200929/20129841i40nazlxAX.png

相鄰串列 (Adjacency List)

顧名思義,這個表示法就是以串列來儲存圖形,與相鄰陣列不同的是,串列只處理有邊的部分,沒有邊的部分不處理

定義:
有一圖形,每個頂點都有自己的串列,串列中的每一個節點用來儲存相鄰的頂點,每個節點包含兩個欄位:頂點與指向相鄰頂點的指標

https://ithelp.ithome.com.tw/upload/images/20200929/201298415c5bt3V6wL.png

步驟:

  1. 上圖無向圖中有 4 個頂點,需準備 4 個串列
  2. V1 串列,第一個節點為頂點 1 ,其中與頂點 2、頂點 3 、頂點 4 之間都有邊,則在串列後方新增頂點 2、頂點 3 、頂點 4 的節點
  3. V2 串列,第一個節點為頂點 2 與頂點 1、頂點 4 之間都有邊,則在串列後方新增頂點 1、頂點 4 的節點
  4. V3 串列,第一個節點為頂點 3 與頂點 1、頂點 4 之間都有邊,則在串列後方新增頂點 1、頂點 4 的節點
  5. V4 串列,第一個節點為頂點 4 與頂點 1、頂點 2、頂點 3 之間都有邊,則在串列後方新增頂點 1、頂點 2、頂點 3 的節點
  6. 記得補上節點與節點之間指標,指向下一個節點

特性:

  • 無向圖若有 n 個頂點,e 個邊,則需要 n 個首節點與 2*e 個節點,例如上圖有 4 個頂點,與 5 個邊,則需要 4 個首節點與 10 個節點( 2 * 5 )
  • 有向圖若有 n 個頂點,e 個邊,則需要 n 個首節點與 e 個節點,例如下圖有 3 個頂點,與 4 個邊,則需要 3 個首節點與 4 個節點

分支度:

  • 有向圖:任一頂點的分支度,就是相連串列上的節點數(排除首節點),如上圖頂點 1 的串列,除了首節點之外,有 3 個節點,分支度為 3
  • 無向圖:
    • 出分支度:任一頂點的分支度,就是相連串列上的節點數(排除首節點),如下圖頂點 3 的串列,除了首節點之外,有 2 個節點,分支度為 2
    • 入分支度:比較複雜,需重覆尋找比對串列之間節點的關係,可另外紀錄一組反鄰串列(Inverse Adjacency List)以方便查詢

https://ithelp.ithome.com.tw/upload/images/20200929/20129841DavudanrxU.png

相鄰多元串列 (Adjacency Multilist)

儲存無向圖型的一種方法,上述兩種都是針對頂點處理,這個方法為以為主

定義:
每個皆以一個節點表示,此節點包含:邊的標記邊的起點邊的終點兩個指標可指向其它節點

https://ithelp.ithome.com.tw/upload/images/20200929/20129841c5TUcJnx8V.png

步驟:

  1. 準備一個串列,每個節點用來儲存圖形中的每個頂點
  2. 盤點所有的邊,並將每一個邊起點終點儲存在各自的串列之中
  3. 第 1 步驟節點(存放頂點)指向第一個包含此頂點的
  4. 各邊的串列中,另含兩個指標,將指標分別指向另一個包含此起點的邊,與另一個包含此終點的邊,以上圖 M1 的邊為例,此邊的起點為 1 則指標指向 M2,因為 M2 邊包含頂點 1,而 M1 邊的終點為 2 ,則指標指向 M4,因為 M4 的邊含有 M 2
  5. 指標找不到可指向,則為空(null)

索引表 (Index Table)

使用兩個一維陣列依照順序儲存相鄰的頂點

https://ithelp.ithome.com.tw/upload/images/20200929/201298414v5xQ0dfIh.png

定義與步驟:

  • 使用一個陣列依照順序儲存相鄰的點,例如與頂點 1 相鄰的有頂點 2、3、4,則將頂點 2、3、4 依序存入陣列
  • 使用一個陣列,紀錄每個頂點,存放了幾個相鄰頂點,其中頂點存放在陣列中的起始位置在哪裡,例如頂點 1,有3各相鄰頂點,而存放第一個相鄰頂點 2 的位置,是在此陣列的第 1 個索引

今日小結

四種表示法,都離不開之前說過的陣列與串列,如果不熟悉的話,可以往前翻閱,另外四種表示法各有其優缺點,例如相鄰矩陣在路經很少的情況下容易浪費空間,但求分支度就非常方便,而相鄰串列法比較節省空間,但求分支度時比較麻煩,還是要根據程式需求去做選擇


今日謎題

小美的男友準備跟小美求婚,於是準備了神秘超大驚喜要給小美,請問你能協助小美發現這份驚喜的禮物是什麼嗎?

https://ithelp.ithome.com.tw/upload/images/20200930/20129841OKDSfRrQBH.png

昨日解謎

謎題說明:
V (所有頂點的集合): { W, B, C, D, E }
E (所有邊的集合): { ( W, B ), ( B, D ), ( D, E ), ( E, C ), ( C, W ) }

將頂點先圈起來,在將兩頂點之間的連線畫上去,就會發現五芒星的形狀,在仔細一看,兩邊交叉處都會經過一個字母,將五個字母集合起來,就會得到 GRAPH ,答案就是 GRAPH ,你答對了嗎
https://ithelp.ithome.com.tw/upload/images/20200929/20129841KNdOP9FGit.png


上一篇
擁抱「資料結構」的「演算法」(14) - 圖形 Graph
下一篇
擁抱「資料結構」的「演算法」(16) - 雜湊 Hash
系列文
擁抱「資料結構」的「演算法」30

尚未有邦友留言

立即登入留言