iT邦幫忙

2022 iThome 鐵人賽

DAY 18
1
自我挑戰組

挑戰 blind 75: 以圖解方式練習解題系列 第 53

圖解 blind 75: Graph 資料結構解析

  • 分享至 

  • xImage
  •  

Graph 資料結構解析

Graph(圖) 是種用來表達資料間關係的資料結構。

Graph(圖) 所組成的要件有:

  1. 節點(vertex): 這是圖中存放資料的基礎單位。
  2. 邊(edge): 這是節點間相連的元件,代表兩個點具有關係,具有順序性的成為有向邊,而具有兩個方向的邊或者說無順序性的稱作無向邊。有些邊有時會帶有權重來代表走過的花費或者消耗,有權重的邊形成的圖稱作權重圖。

根據其節點間的關係是否是雙向,可以分成:

  1. 有向圖: 所有節點間連接的邊不一定是具有雙向關係。
  2. 無向圖: 所有節點間連接的邊一定是具有雙向關係。

如果再把邊加上權重,就變成權重圖。

Graph(圖) 在資料結構表示法有以下幾種:

  1. Adjacency List(鏈接表): 以一個表單來紀錄每個節點的有鏈接的點。
  2. Adjaceny Matrix(鏈接矩陣): 以一個矩陣來紀錄任意兩個個點鏈接的邊個數,以此來紀錄每個結點鏈接狀態。
  3. Incidencent Matrix(關聯矩陣): 用一個矩陣來紀錄每個邊其所屬的邊。

以下是一個有向圖分對應到三種表示法:

相關應用

Graph Database(圖形資料庫) 不同於關聯式資料庫是以外部關聯來紀錄不同類別資料表的關係,是用透過邊來紀錄資料間的關係,資料則是已資料節點的方式存儲。

neo4j 就是著名的圖性資料庫,用來分析圖形相關運算最為合適。比如:假設已經有多個旅遊點之間的旅行費用,要求算出從某一個旅遊點到另一個旅遊點的最小旅行費用,就可以使用找 DijkStra 這類演算法,找出最小花費路徑。

參考文獻

https://web.ntnu.edu.tw/~algo/Graph.html

https://zh.wikipedia.org/zh-tw/%E5%9B%BE_%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84


上一篇
圖解 blind 75: BackTracking - Word Search(2/2)
下一篇
圖解 blind 75: Graph - Pacific Atlantic Water Flow(1/3)
系列文
挑戰 blind 75: 以圖解方式練習解題93
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言