擁抱「資料結構」的「演算法」(15)

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

11月 30, 2020

前言

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

圖形表示法

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

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

相鄰矩陣 (Adjacency Matrix)

定義：
有一圖形，有n 個頂點，則可利用 n * n 的 2 維陣列來表示，如下圖頂點有 4 個，則可以用 4 * 4 的二維矩陣表示，逐一觀察每個頂點與其它頂點有沒有邊，並套用下列規則填滿矩陣中的值

陣列的值與圖形的關係：

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

步驟：

頂點 1 與頂點 2、頂點 3 、頂點 4 之間都有邊，則將矩陣中的 [ 1, 2 ], [ 1, 3 ], [ 1, 4 ] 填 1
頂點 2 與頂點 1、頂點 4 之間都有邊，則將矩陣中的 [2, 1 ], [ 2, 4 ] 填 1
頂點 3 與頂點 1、頂點 4 之間都有邊，則將矩陣中的 [ 3, 1 ], [ 3, 4 ] 填 1
頂點 4 與頂點 1、頂點 2、頂點 3 之間都有邊，則將矩陣中的 [ 4, 1 ], [ 4, 2 ], [ 4, 3 ] 填 1
其它位置填 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 ，另外下圖的矩陣不是對稱矩陣

相鄰串列 (Adjacency List)

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

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

步驟：

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

特性：

無向圖若有 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)以方便查詢

相鄰多元串列 (Adjacency Multilist)

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

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

步驟：

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

索引表 (Index Table)

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

定義與步驟：

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

今日小結

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

今日謎題

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

昨日解謎

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

將頂點先圈起來，在將兩頂點之間的連線畫上去，就會發現五芒星的形狀，在仔細一看，兩邊交叉處都會經過一個字母，將五個字母集合起來，就會得到 GRAPH ，答案就是 GRAPH ，你答對了嗎

搜尋此網誌

小菜一碟