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