---
tags: DSA in JavaScript
---
# Ch.26 Graph

Graph (圖) 是一種抽象的數據結構，由許多的節點 (vertex/node) 與邊 (edge/connection) 組成。


## Graph, Tree, Linked List

- 任意兩點間只有單一路徑能連結的 Graph，判定為 Tree
- 每個節點最多只會連結兩個節點的 Tree，判定為 Linked List

## 應用情境

- 社群網站 (追蹤、好友連結)
- 地圖/導航
- 網站推薦
- 檔案系統最佳化

## 圖的種類

基本的圖，依照 edge 的種類，可以分為四種類型。

- weight / unweight：每個 edge 都有自己的權重 (ex: 距離、運費等)
- directed / undirected: 每個 edge 都有自己的方向性 (ex: 單行道)

## 儲存方式

圖有兩種基本的儲存方式---相鄰矩陣與相鄰串列

### 相鄰矩陣 (adjacency matrix)

使用一個二維矩陣來儲存各個節點的關係。

### 相鄰串列 (adjacency list)

使用串列儲存每個節點有連結的邊。


### 小結

以下為兩者的時間複雜度比較表
V 為節點數，E 為邊的數量

| | 相鄰矩陣 | 相鄰串列 |
| ------------ | -------- | -------- |
| 新增節點 | $O(V^2)$ | $O(1)$ |
| 新增邊(連結) | $O(1)$ | $O(1)$ |
| 刪除節點 | $O(V^2)$ | $O(V+E)$ |
| 刪除邊(連結) | $O(1)$ | $O(E)$ |
| 尋找節點 | $O(1)$ | $O(V+E)$ |
| 儲存圖 | $O(V^2)$ | $O(V+E)$ |

相鄰矩陣有以下幾種優勢：

- 增刪連結比較快速，適合頻繁增刪連結的情境
- 適用於較稠密(連結較多)的圖

相鄰串列有以下幾種優勢：

- 佔用較少記憶體空間
- 增刪節點比較快速，適合頻繁增刪節點的情境
- 適用於教稀疏(連結較少)的圖

## 實作
**以下案例為 undirected graph，並使用 adjacency list 儲存**

這裡使用物件來儲存每個節點 (key) 並使用陣列 (value) 儲存與該節點相連的節點。

class Graph {
  constructor () {
    this.adjacencyList = {}
  }
}

### `addVertex(vertex)`

增加一個節點。

addVertex (vertex) {
  if (!this.adjacencyList[vertex]) {
    this.adjacencyList[vertex] = []
  }
}

### `addEdge(vertex1,vertex2)`

因為這邊使用 undirected graph，因此兩個節點都得加上彼此關聯。

addEdge (v1, v2) {
  this.adjacencyList[v1].push(v2)
  this.adjacencyList[v2].push(v1)
}

### `removeEdge(vertex1, vertex2)`

此處的作法是直接替換成新的陣列，也可以使用其他方法，只要能把節點從彼此的陣列中移除就行了。

addEdge (v1, v2) {
  this.adjacencyList[v1].push(v2)
  this.adjacencyList[v2].push(v1)
}

### `removeVertex(vertex)`

從物件移除該節點之前，要先移除其他節點與它的連結。

removeVertex (vertex) {
  this.adjacencyList[vertex].forEach(value => {
    this.removeEdge(vertex, value)
  })
  delete this.adjacencyList[vertex]
}

## To be countinued

目前簡單介紹圖與它的四種方法 (增刪節點、連結) 下一篇會介紹如何從一個節點遍歷至圖內的所有節點。