# Graph
> A graph data structure consists of a finite (and possibly mutable) set of vertices (also called 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.
>
> 簡單來說，就是集結了多個 Nodes(節點) 和他們彼此之間的 Connections(關聯) 的資料結構
## About Graphs
### 使用情境
- Social Networks
- Ex. 好友之間的關係，可以進而做出適當的推薦
- Ex. 其他人也看了…、你可能也喜歡 …、你可能也認識 …、常常一起購買 …
- Location Mapping
- Ex. Google Map、Directions、Locations…
- Routing Algorithms
- Ex. Request 回來的 Response 會分成多個小封包散步在網路上回來
- Visual Hierarchy
- File System Optimizations
### 組成
- Vertex：也就是我們平常說的 Node，以 Graphs 來說就是裡面的點
- Edge：是 Node 與 Node 之間的關聯，也就是 Graphs 中兩點之間的連線
### 分類
#### Directive vs Undirective Graph ( Edges 有無方向性 )
> Directive Graph - Edges 只會有一個方向 ( Ex. Instagram 的追蹤機制 )
> Undirective Graph - Edges 沒有限制方向性，雙向都通 ( Ex. 好友關係 )
#### Weighted Graph vs Unweighted Graph ( Edges 有無 value )
> Weighted Graph - Edges 之間有 value ( Ex. 地圖上的 Edges 會有距離、時間等數值 )
> Unweighted Graph - Edges 之間沒有 value
## Graph Data Structures
### Adjacency Matrix
> 用矩陣的方式來儲存節點以及它們之間是否相連，也就是記錄 Vertex 之間是否有 Edge。
例如下方例子中的 [A, B] 間相連，在表格中的 1 可能會以 boolean true 表示
### Adjacency List
> 用陣列儲存節點(Vertex)間的關聯
> ・當節點是的值是數字，可用陣列的 index 來記錄值，並在陣列中儲存與它相連的節點號碼
> ・當節點的值不是數字如字母，可以使用 Hash Table 來儲存 Graph 的資料
### BigO 比較
> `|V|` = Number of Vertices / `|E|` = Number of Edges
| Operation | 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\|) |
:::info
在 JavaScript 中實作 Adjacency Matrix 的 Add 和 Remove Vertex 看起來會是 O(|V|)，而之所以圖表為 O(|V^2|)，是因為在某些情況下不能直接動態修改原資料結構，需要重新建立新的 Matrix，而重新建立的動作之時間複雜度為 O(|V^2|)。
:::
- Adjacency List 👑
✅ Edges 較稀疏時，需較少的儲存空間 (`Storage`)
✅ Iterate 所有 Edges 的速度較快 (`Add | Remove Vertex`)
👎🏻 ~~查找特定 Edge 的速度較慢~~ (`Query`)
- Adjacency Matrix
👎🏻 ~~Edges 較稀疏時，需較大的儲存空間~~ (`Storage`)
👎🏻 ~~Iterate 所有 Edges 的速度較慢~~ (`Add | Remove Vertex`)
✅ 查找特定 Edge 的速度較快 (`Query`)
- 結論
- 在現實世界中，大部分的情境下，並非所有的 Vertex 之間都會有關聯，也就是關聯較為稀疏，因此較常使用 Adjacency List 進行實作
- 如果 Vertex 之間幾乎都有關聯，也就是關聯非常密集，那就可以考慮使用 Adjacency Matrix
## Graph Implementation (Adjacency List)
> 以下範例先忽略錯誤處理
```typescript!=
type Vertex = string; // 可以自己依需求擴充
interface AdjacencyList {
[vertex: Vertex]: Vertex[];
}
class Graph {
adjacencyList: AdjacencyList;
constructor(initalList?: AdjacencyList) {
this.adjacencyList = initalList ?? {};
}
}
```
### Add Vertex
> 在 adjacencyList 中，建立一個以 vertex 名稱為 key，value 為一空陣列，接著會在陣列中放入與它有連結的 vertex value
```typescript=
addVertex(vertex: Vertex) {
if (this.adjacencyList[vertex]) return;
this.adjacencyList[vertex] = [];
}
```
### Add Edge
> 接收兩個 Vertex，從 `adjacencyList` 中找到各自的 value，並將彼此加入 value 陣列中，也就是建立兩者之間的關聯
```typescript=
addEdge(vertex1: Vertex, vertex2: Vertex) {
// add edges between vertex1 and vertex2
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
```
### Remove Edge
> 接收兩個 Vertex，從 `adjacencyList` 中找到各自的 value，並將彼此從 value 陣列中移除，也就是移除兩者之間的關聯
```typescript=
removeEdge(vertex1: Vertex, vertex2: Vertex) {
// remove edges between vertex1 and vertex2
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
(v) => v !== vertex2,
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
(v) => v !== vertex1,
);
}
```
### Remove Vertex
> 接收一個 Vertex，從 `adjacencyList` 中找到對應的 value，透過他移除所有和其他 Vertex 的關聯後，將自己從 `adjacencyList` 中移除
```typescript=
removeVertex(vertex: Vertex) {
// Remove edges until array value is empty
while (this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop() as Vertex;
this.removeEdge(vertex, adjacentVertex);
}
// Remove vertex
delete this.adjacencyList[vertex];
}
```
## Graph Traversal
- 包括 Visiting / Updating / Checking 當中的每一個 Node
- 常見的使用情境
- 點對點的網路連線
- 爬蟲
- 尋找最 [ 接近 ] 的推薦 ( 最多相關聯、相似 )
- 最短路徑 - GPS 導航、迷宮、AI ( 最快贏得比賽的方式
- 常見的 Graph Traversal 方式
- Depth First Graph Traversal
- Breadth First Graph Traversal
### Depth First Graph Traversal (DFS)
> 從「起點」開始往「下一個節點」、再到「（下一個節點的）下一個節點」，找完後再回頭從「起點」往「(另一個) 下一個節點」直到找完為止，換句話說就是先往 Children (縱向) 再往 Siblings (橫向)，而找過的不能再找
#### DFS - Recursive
:::info
Pseudo code
```=
DFS(vertex):
如果 vertex 為空，return (base case)
在 result list 加入 vertex
標記 vertex 為 visited
for 每一個 vertex 相鄰的 vertex:
若相鄰的 vertex 未被標記為 visited，遞迴呼叫 DFS(相鄰 vertex)
```
:::
:::spoiler Code Implementation
```typescript=
// 接收起始點作為參數
depthFirstRecursive(start: Vertex) {
// 建立一個陣列紀錄走過的 Vertex，作為最後回傳的結果
const result: Vertex[] = [];
// 建立一個物件來紀錄已經走過的 Vertex
const visited: Record<Vertex, boolean> = {};
const dfs = (vertex: Vertex) => {
// Base Case
if (!vertex) return;
// 將其推進要回傳的 result 中
result.push(vertex);
// 將其紀錄為『已走過』
visited[vertex] = true;
this.adjacencyList[vertex].forEach((neighbor) => {
// 已經走過了則不再紀錄
if (visited[neighbor]) return;
// 若沒有，則繼續往下紀錄
dfs(neighbor);
});
};
dfs(start);
return result;
}
```
:::
:::spoiler Test Result
```typescript=
// Test Result
const graph = new Graph({
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "E"],
D: ["B", "E", "F"],
E: ["C", "D", "F"],
F: ["D", "E"],
});
console.log(graph.depthFirstRecursive("A"));
// ["A", "B", "D", "E", "C", "F"]
```
<img src="https://hackmd.io/_uploads/SyRnoojvC.png" width="300" />
:::
#### DFS - Iterative
:::info
Pseudo code
```=
DFS(vertex):
建立 S 為一個 stack
S.push(vertex)
while(S 不為空):
vertex = S.pop()
如果 vertex 未被標記為 visited:
將 vertex 加入 result list
標記 vertex 為 visited
for 每一個 vertex 的 neighbor，S.push(neighbor)
```
:::
:::spoiler Code Implementation
```typescript=
// 接收起始點作為參數
depthFirstIterative(start: Vertex) {
// 建立一個陣列紀錄走過的 Vertex，作為最後回傳的結果
const result: Vertex[] = [];
// 建立一個物件來紀錄已經走過的 Vertex
const visited: Record<Vertex, boolean> = {};
// 建立一個 Stack，並先將起始點先放到 Stack 當中
const stack: Vertex[] = [start];
// 將起始點紀錄為『已走過』
visited[start] = true;
// 當 Stack 中還有東西 :
while (stack.length > 0) {
// 從 Stack 中取出最後一個 Vertex
const curVertex = stack.pop()!; (Firt In Last Out)
// 將其推進要回傳的 result 中
result.push(curVertex);
// 將其沒被紀錄過的鄰居全部放到 Stack 裡面
this.adjacencyList[curVertex].forEach((neighbor) => {
// 已經走過了則不再紀錄
if (visited[neighbor]) return;
// 把沒被紀錄過的鄰居放到 Stack 裡面，讓 while loop 繼續跑
stack.push(neighbor);
// 已經推進 Stack 中的，紀錄為『已走過』
visited[neighbor] = true;
});
}
return result;
}
```
:::
:::spoiler Test Result
```typescript=
const graph = new Graph({
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "E"],
D: ["B", "E", "F"],
E: ["C", "D", "F"],
F: ["D", "E"],
});
console.log(graph.depthFirstIterative("A"));
// ["A", "C", "E", "F", "D", "B"]
```
<img src="https://hackmd.io/_uploads/ryYpioiwR.png" width="300"/>
:::
### Breadth First Graph Traversal
> 從「起點」、到「下一個節點」、回到「起點」、到「（起點的）下一個節點」，換句話說就是先往 Siblings (橫向) 再往 Children (縱向)，而找過的不能再找
> <img src="https://hackmd.io/_uploads/SJr2xyhwR.png" width="500"/>
:::spoiler Implementation
```typescript=
// 接收起始點作為參數
breathFirst(start: Vertex) {
// 建立一個陣列紀錄走過的 Vertex，作為最後回傳的結果
const result: Vertex[] = [];
// 建立一個物件來紀錄已經走過的 Vertex
const visited: Record<Vertex, boolean> = {};
// 建立一個 Queue，並將起始點先放到 Queue 當中
const queue: Vertex[] = [start];
// 將起始點紀錄為『已走過』
visited[start] = true;
// 當 Queue 中還有東西 :
while (queue.length > 0) {
// // 從 Queue 中取出第一個 Vertex (Firt In First Out)
let curVertex = queue.shift()!;
// 將其推進要回傳的 result 中
result.push(curVertex);
// Loop over each vertex in adjacency list for vertex you are visiting
this.adjacencyList[curVertex].forEach((neighbor) => {
// 已經走過了則不再紀錄
if (visited[neighbor]) return;
// 把沒被紀錄過的鄰居放到 Queue 裡面，讓 while loop 繼續跑
queue.push(neighbor);
// 已經推進 Queue 中的，紀錄為『已走過』
visited[neighbor] = true;
});
}
return result;
}
```
:::
:::spoiler Test Result
```typescript=
const graph = new Graph({
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "E"],
D: ["B", "E", "F"],
E: ["C", "D", "F"],
F: ["D", "E"],
});
console.log(graph.breathFirst("A"));
// ["A", "B", "C", "D", "E", "F"]
/* Walk Trough...
queue = [A]
result = []
queue = [B, C]
result = [A]
queue = [C, D]
result = [A, B]
queue = [D, E]
result = [A, B, C]
queue = [E, E, F]
result = [A, B, C, D]
queue = [E, F]
result = [A, B, C, D, E]
queue = [F]
result = [A, B, C, D, E]
queue = []
result = [A, B, C, D, E, F]
*/
```
<img src="https://hackmd.io/_uploads/SJ31Gg3vA.png" width="300"/>
:::
---
:::spoiler Adjacency Matrix Implementation
```typescript=
namespace Graph {
export interface Matrix {
[node: string]: { [node: string]: boolean };
}
export type Node = string;
}
class Graph {
matrix: Graph.Matrix = {};
constructor(nodes: Graph.Node[]) {
nodes.forEach((outerKey) => {
this.matrix[outerKey] = {};
nodes.forEach((innerKey) => {
this.matrix[outerKey][innerKey] = false;
});
});
}
addNode(node: Graph.Node) {
this.matrix[node] = {};
Object.keys(this.matrix).forEach((key) => {
this.matrix[node][key] = false;
if (key !== node) {
this.matrix[key][node] = false;
}
});
}
removeNode(node: Graph.Node) {
delete this.matrix[node];
Object.keys(this.matrix).forEach((key) => {
delete this.matrix[key][node];
});
}
addEdge(fromNode: Graph.Node, toNode: Graph.Node) {
this.matrix[fromNode][toNode] = true;
this.matrix[toNode][fromNode] = true;
}
removeEdge(fromNode: Graph.Node, toNode: Graph.Node) {
this.matrix[fromNode][toNode] = false;
this.matrix[toNode][fromNode] = false;
}
isEdge(fromNode: Graph.Node, toNode: Graph.Node) {
return this.matrix[fromNode][toNode];
}
}
```
:::
## Dijkstra's Algorithm
> 全名為 Dijkstra’s Shortest Path Algorithm，在 Graph 上找出兩個 Vertices 之間的最短路徑
- 常用情境
- GPS - 尋找最短路徑
- Network Routing - 幫資料找到最短路徑傳遞
- 生化 - 來建立病毒傳播給人類的狀況
- 機票 - 尋找到達目的地最便宜的方式
### Weighted Graph
> 點到點之間的距離，等同於 Weighted Graph 上的 Edges 存在數值
:::spoiler Implementation
```typescript=
interface AdjacencyList {
[node: string]: { node: string; weight: number }[];
}
class WeightGraph {
constructor(public adjacencyList: AdjacencyList) {
this.adjacencyList = adjacencyList ?? {};
}
addVertex(vertex: string) {
if (this.adjacencyList[vertex]) return;
this.adjacencyList[vertex] = [];
}
addEdge(v1: string, v2: string, weight: number) {
this.adjacencyList[v1].push({ node: v2, weight });
this.adjacencyList[v2].push({ node: v1, weight });
}
}
```
:::
### Demo
> 尋找 A → E 的最短距離
> <img src="https://hackmd.io/_uploads/rknQ0dzuA.png" width="300"/>
:::spoiler Walkthrough
> `visited` 紀錄拜訪過的避免重複拜訪 / `previous` 紀錄最短距離是從誰過來的
1. 一開始除了起點和起點的距離外，無法法上知道和其他的距離，因此先給 `Infinity`
<img src="https://hackmd.io/_uploads/S1fbwFf_R.png" width="400" />
2. 尋找離自己最近的 Node 前往，以目前來說為 A ( 也就是自己 )
<img src="https://hackmd.io/_uploads/ryPjvKz_A.png" width="400" />
3. 接著查看他的鄰居 ( B, C )，去查看離起始點的距離是否小於原本的值，是的話就取代掉
A → B ( 4 )
<img src="https://hackmd.io/_uploads/HkZedKzuC.png" width="400" />
A → C ( 2 )
<img src="https://hackmd.io/_uploads/ryS7_KMuC.png" width="400" />
4. 往離起始點的距離較短的那個 Node 移動 ( 且不能重複拜訪 )，也就是移動到 C
<img src="https://hackmd.io/_uploads/SJBzKYGOR.png" width="400" />
5. 查看和鄰居 ( D, F )，去查看離起始點的距離是否小於原本的值，是的話就取代掉
C → D ( 2 )
<img src="https://hackmd.io/_uploads/HJwK5tzuC.png" width="400" />
C → F ( 4 )
<img src="https://hackmd.io/_uploads/SkG5qYzuR.png" width="400" />
6. 往離起始點的距離較短的那個 Node 移動 ( 且不能重複拜訪 )，也就是移動到 B 或 D，這邊先按字母順序進行 ( B )
<img src="https://hackmd.io/_uploads/ryZEsKGdC.pngg" width="400" />
7. 接著查看他的鄰居 ( E )，去查看離起始點的距離是否小於原本的值，是的話就取代掉
B → E ( 3 )
<img src="https://hackmd.io/_uploads/SyTOotGOA.png" width="400" />
8. 接著回到 D ( A → D 和 A → B 的距離同為 4 )
<img src="https://hackmd.io/_uploads/r116iYGO0.png" width="400" />
9. 查看他的鄰居 ( E, F )，去查看離起始點的距離是否小於原本的值，是的話就取代掉
C 拜訪過了跳過
D → E ( 3 )
<img src="https://hackmd.io/_uploads/rkxoAqf_0.png" width="400" />
D → F ( 1 )
<img src="https://hackmd.io/_uploads/BJjJ1jG_R.png" width="400" />
10. 往離起始點的距離較短的那個 Node 移動 ( 且不能重複拜訪 )，也就是移動到 F
<img src="https://hackmd.io/_uploads/BJE4JoMuA.png" width="400" />
11. 接著查看他的鄰居 ( E )，去查看離起始點的距離是否小於原本的值，是的話就取代掉
F → E ( 1 )
<img src="https://hackmd.io/_uploads/rkgvJsMOR.png" width="400" />
12. 最後走到 E，透過紀錄順序的物件回推取得 A 走到 E 的最短路徑
> E ← F ← D ← C ← A
<img src="https://hackmd.io/_uploads/HkByxszdA.png" width="400" />
:::
:::info
Pseudo Code
```=
Function 接收一個起始點和終點的 Vertex
建立一個 `distances` object，以 Ajacency List 中的 Vertecies 為 key，並將除了 starting vertex 設為 0 外，每個 Value 都先設為 `Infinity`
建立一個 Priority Queue 並將每個 vertex
- Add each vertex with a priority of `infinity` to the priority queue, except the starting vertex, which should have a priority of `0`, because that’s where we begin
- Create another object called previous and set each key to be every vertex in the adjacency list with a value of `null`
- Start Looping as long as there is anything in the priority queue
- dequeue a vertex from the priority queue
- If that vertex is the same as the ending vertex → done !!
- Otherwise loop through each value in the adjacency list at the vertex
- Calculate the distance to that vertex from starting vertex
- If the distance is less than currently stored in distances obj
- Update the distances obj with lower distance
- Update the previous obj to contain the vertex
- Enqueue the vertex with the total distance from starting node
```
:::
:::spoiler Implementation
簡易的 Priority Queue
> 更好的方式可以參考使用 Linked List 實作
```typescript=
class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(val, priority) {
this.values.push({ val, priority });
this.sort();
}
dequeue() {
return this.values.shift();
}
sort() {
this.values.sort((a, b) => a.priority - b.priority);
}
}
```
延續使用上面的 Weighted Graph 實作 Dijkstra
:::
## 參考文章
- [學習筆記 — 7. Graph 圖](https://medium.com/@amber.fragments/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-7-graph-%E5%9C%96-d4359fb6f19a)
- [JavaScript Algorithms and Data Structures Masterclass](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/?couponCode=ST9MT71624)
Sign in with Wallet
Connect another wallet