[資料結構]Graph — 圖

發表於 更新於 分類於
圖是由節點(node)和邊(edge)所組成的，一個節點可能與多個節點相連著，而這些相連的節點又被稱作相鄰節點(neighbor)，圖在生活中應用的例子相當的普遍，像是人際關係的社交網路、尋找地圖最短路徑、通訊網路等等。

圖是由節點(node)和邊(edge)所組成的，一個節點可能與多個節點相連著，而這些相連的節點又被稱作相鄰節點(neighbor)，圖在生活中應用的例子相當的普遍，像是人際關係的社交網路、尋找地圖最短路徑、通訊網路等等。

無向圖(Undirected Graph)

邊沒有方向性，A 可以到 B，B 也可到 A，概念類似雙向道，兩邊都可以通行

有向圖 ( Directed Graph)

邊具有方向性，B 可以到 A 但是 A 不能到 B，概念類似單行道，僅限單邊通行

加權圖( Weighted Graph )

每條路線都有標記一個數字，稱為權重分數，這邊的權重分數可以是時間、成本、距離等等，加權圖最經典的應用就是處理最短路徑的問題，像是我要搭乘甚麼樣的交通工具才能最快到達目的地，Google map 的交通工具規劃就是採用了這樣的概念。

Graph Traversal

如果想要走遍 Graph 裡面所有的節點可以有兩種做法，第一種方法是廣度優先搜尋 Breadth First Search(BFS)，我們可以先從一個故事來理解廣度優先搜尋的概念，有一天小王、 小李、小林他們三個人要結拜成三兄弟，因此辦了一個派對邀請所有朋友來共襄盛舉，在派對上「我」認識了一個很可愛的女生，只可惜當天沒要到連絡方式，也不知道對方的名字，只有一起拍了一張照片，回家後心心念念那個女孩，好想再見她一面，於是我決定動用我的人脈， 來找到那個心儀的女孩!

於是我決定拜託我的三個好朋友，問他們認不認識這個女孩，結果三個朋友都說不認識，但很熱心地幫我問了他們的朋友有沒有人認識這個女孩，下圖的藍色節點代表是我認識的朋友，綠色節點則是朋友的朋友，所以我會先問過所有我認識的朋友(first degree 第一層)，而我的朋友會再去問他們的朋友(second degree 第二層)。

從上面的故事我們可以知道，廣度優先的搜尋順序會是先走訪相鄰節點，都走訪完了，就往下一層繼續走訪，廣度優先搜尋採用 queue 來實作，因為 queue 具有先進後出的特性，可以確保先搜尋到的節點，會優先成為下一個搜尋起點。

那麼就用 js 來實作 Breadth First Search，在開始之前我們要先建立一個 Graph

先用 js 實作出這個 Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Node {
  constructor(val) {
    this.value = val;
    this.neighbors = [];
    this.visited = false;
  }
  addNeighbor(n) {
    this.neighbors.push(n);
  }
}

let A = new Node("A");
let B = new Node("B");
let C = new Node("C");
let D = new Node("D");
let E = new Node("E");
let F = new Node("F");
let G = new Node("G");
let H = new Node("H");
A.addNeighbor(B);
A.addNeighbor(C);
A.addNeighbor(D);
B.addNeighbor(E);
B.addNeighbor(F);
D.addNeighbor(G);
D.addNeighbor(H);

用 js 實作 Breadth First Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const BFS = (starter) => {
  let queue = [];
  queue.push(starter);
  while (queue.length !== 0) {
    let firstNode = queue.shift();
    if (!firstNode.visited) {
      firstNode.visited = true;
      result.push(firstNode.value);
      firstNode.neighbors.forEach((element) => {
        if (!element.visited) {
          queue.push(element);
        }
      });
    }
  }
  return result;
};

BFS(A);

//輸出結果 ["A", "B", "C", "D", "E", "F", "G", "H"]

把走訪過程圖像化的話會如下圖

除了 Breadth First Search 之外，還有另一種搜尋方式叫深度優先搜尋 Depth First Search (DFS)，會先從一邊開始走訪，概念類似於走迷宮摸著牆走的概念，走到底了就折返，繼續往沒走過的節點探索，步驟如下:

  • 從 A 出發，沿著上方的牆依序訪問，A, B ,E
  • 走到 E 的時候發現是死路了，就折返到 B
  • 發現還有另外一條路再走到 F
  • 走到 F 發現又是死路，沿路折返到 A
  • 發現 A 還有其它相鄰節點，再走到 C
  • 依序走下去…

用 js 實作 Depth First Search

參考資料: breadth-first-search-a-simple-explanation