iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 7
0
自我挑戰組

學習資料結構30天系列 第 7

[Data Structure][Graph] - Representation

前言

昨天大致介紹圖形的定義,今天就來介紹幾個圖形的資料結構!

圖(Graph),是一種用來描述點與點之間關係的資料結構,也可以說是記錄關聯性的結構

圖形的表示法

圖形的資料結構非常多,書中介紹了常用的兩種: 鄰接矩陣 Adjacency matrix鄰接串列 Adjacency list

  • 鄰接矩陣 Adjacency matrix

    • 含有n個頂點的圖形,其Adjacency matrix的大小就會是 n列 x n行。
    • matrix中的元素只會是0或1
    1. 以下圖(無向圖)作為例子 =>
      https://ithelp.ithome.com.tw/upload/images/20181022/20112438QVYaD0PQxd.jpg
      -> Adjacency matrix =
      https://ithelp.ithome.com.tw/upload/images/20181021/20112438G0KK5oBQrJ.jpg
      • 從矩陣的1,可以看出兩個頂點是有連線的。
      • 因為頂點不可能自成迴路,所以主對角線上的元素都會是0。
      • 無向圖的Adjacency matrix一定會是對稱矩陣。
      • 將每一列的數值相加就是該頂點的分支度。
        例如 : 第0列數值相加為 0+1+1+1 = 3,所以A點分支度為3。
    2. 以下圖(有向圖)作為例子 =>
      https://ithelp.ithome.com.tw/upload/images/20181022/20112438dsgbLwEBHE.jpg
      -> Adjacency matrix =
      https://ithelp.ithome.com.tw/upload/images/20181021/20112438qBtJLnQCly.jpg
      • 矩陣中,第0列有1個非零數,表示A點出分支度為1。
      • 矩陣中,第0行有2個非零數,表示A點入分支度為2。
      • 有向圖的Adjacency matrix不一定為對稱矩陣。
  • 鄰接串列 Adjacency list

    • 利用串列的方式將相鄰的頂點串起來。
    • 可以節省記憶體空間。
    • 同樣以下圖(無向圖)為例
      https://ithelp.ithome.com.tw/upload/images/20181022/20112438tKIV3Zzuv0.jpg
    • Adjacency list ->
      https://ithelp.ithome.com.tw/upload/images/20181022/20112438HLutsTjusB.jpg
    • 同樣以下圖(有向圖)為例
      https://ithelp.ithome.com.tw/upload/images/20181022/20112438REwZahJnrW.jpg
    • Adjacency list ->
    • https://ithelp.ithome.com.tw/upload/images/20181022/20112438PH0i06YiWF.jpg

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


上一篇
[Data Structure][Graph] - Theory
下一篇
[Data Structure][Graph] - Traversal - BFS
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言