---
# System prepended metadata

title: Graph
tags: [Algorithm & Data Structure]

---

# 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. 好友關係 )

![image](https://hackmd.io/_uploads/SksCai9PR.png)
  
#### Weighted Graph vs Unweighted Graph ( Edges 有無 value )

> Weighted Graph - Edges 之間有 value ( Ex. 地圖上的 Edges 會有距離、時間等數值 )
> Unweighted Graph - Edges 之間沒有 value

![image](https://hackmd.io/_uploads/HyxnpicD0.png)

## Graph Data Structures
### Adjacency Matrix
> 用矩陣的方式來儲存節點以及它們之間是否相連，也就是記錄 Vertex 之間是否有 Edge。
  例如下方例子中的 [A, B] 間相連，在表格中的 1 可能會以 boolean true 表示

![image](https://hackmd.io/_uploads/Sk529FiD0.png)


### Adjacency List
> 用陣列儲存節點(Vertex)間的關聯
> ・當節點是的值是數字，可用陣列的 index 來記錄值，並在陣列中儲存與它相連的節點號碼
> ・當節點的值不是數字如字母，可以使用 Hash Table 來儲存 Graph 的資料

![image](https://hackmd.io/_uploads/S15TcKivA.png)

### 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)