Docker
Network
RxJS
Nginx
TypeScript
Data Structure And Algorithm
JavaScript
PostgreSQL
React
Git資料結構筆記-圖 (Graph)
圖 (Graph)的資料結構時常運用在 1. 社群網站 (Facebook, Instagram...) 2. 地圖系統 (Google map)，路徑計算等方面。
從維基百科的描述中對於圖 (Graph) 的解釋為: 「 A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph.」
上面的解釋包含了許多的專有名詞，所以這裡針對專有名詞做紀錄:
- Vertex : 就是圖的節點 (node)。
- Edge : vertex 與 Vertex 之間的連結。
- Directed 與 Undirected : 對於 Directed Graph 而言，兩個 vertex 之間僅能進行單向溝通 ( v1 -> v2 )，對於 Undirected Graph 而言，兩個 vertex 之間可以雙向溝通 ( v1 -> v2 也可以 v2 -> v1 )。
- Weighted與 Unweighted : 若 Edge 上有儲存資訊，則稱為 Weighted Graph ，若無則稱為 Unweighted Graph 。
Directed Graph 的應用
如 Instagram ，在 A 追蹤 B ，但 B 沒有追蹤 A 的情況下 (即 A --> B )，因此 A 可以觀察到 B 所發出的貼文、動態，然而在 B 則無法觀察到 A 所發的貼文。
Undirected Graph 的應用
如 Facebook ， A 與 B 互相是好友，也因此兩人所發出的貼文都可以互相被看到 ( A - B )。另外在 Weighted Graph 的應用上如 Google Map ，倘若我要確認 A 點與 B 點之間的距離，負責 A 與 B 的連結 (Edge) 就會儲存著兩者的距離。
如何實現 圖 (Graph)
可以透過 1. Adjacency Matrix (鄰接矩陣) 或是 2. Adjacency List (鄰接表) 兩種方法。假設有一 Graph 共有 6 個 vertex ( A - F )，它們互相的關係可以透過下方兩種範例的呈現。
Adjacency Matrix
Adjacency Matrix 是以矩陣來表示各 vertex 之間的關係，對於鬆散的圖結構 (Sparse Graph) 而言會佔據較多的記憶體，也因此在遍歷所有 Edges 時，會花上較多的時間，但在搜尋特定的 Edge 時後，它的時間複雜度為 O (1)。
Adjacency List
Adjacency List 是透過列表方式表示各 vertex 的關係，對於鬆散的圖結構而言，因為佔據較少的記憶體，在遍歷所有 Edges 時所花的時間較少，但是在搜尋特定的 Edge 時，它的時間複雜度為 O ( V + E )，其中 V 與 E 分別為 Vertex 與 Edge 的數量。
JavaScript 實現 圖 (Graph)
由於在現實生活上，透過 Graph 來描述現實生活上各種情況時，通常有很大機率傾向較鬆散的結構 (Sparse Graph ，也就是 Vertex 多，但 Edge 較少) ，也因此在這裡透過 Adjacency List 方式來實現。
新增 Vertex 以及 Edge
移除 Vertex 以及 Edge
圖遍歷 (Graph Traversal)
圖的遍歷可以透過 1. Breadth First Search或是 2. Depth First Search 來實現。
圖 (Graph) 的時間複雜度
| Opertaion | Adjacency List | Adjacency Matrix |
|---|---|---|
| Add Vertex | O(1) | O(V^2) |
| Add Edge | O(1) | O(1) |
| Remove Vertex | O(V+E) | O(V^2) |
| Remove Edge | O(E) | O(1) |
| Query | O(V+E) | O(1) |
| Storage | O(V+E) | O(V^2) |