Day10: [资料结构] Graph - 图

图是由节点(node)和边(edge)所组成的，一个节点可能与多个节点相连着，而这些相连的节点又被称作相邻节点(neighbor)，图在生活中应用的例子相当的普遍，像是人际关系的社交网路、寻找地图最短路径、通讯网路等等。

无向图(Undirected Graph)

边没有方向性，A可以到B，B也可到A，概念类似双向道，两边都可以通行

有向图 ( Directed Graph)

边具有方向性，B可以到A但是A不能到B，概念类似单行道，仅限单边通行

加权图( Weighted Graph )

每条路线都有标记一个数字，称为权重分数，这边的权重分数可以是时间、成本、距离等等，加权图最经典的应用就是处理最短路径的问题，像是我要搭乘甚麽样的交通工具才能最快到达目的地，Google map的交通工具规划就是采用了这样的概念。

google map

Graph Traversal

如果想要走遍Graph里面所有的节点可以有两种做法，第一种方法是广度优先搜寻 Breadth First Search(BFS)，我们可以先从一个故事来理解广度优先搜寻的概念，有一天小王、 小李、小林他们三个人要结拜成三兄弟，因此办了一个派对邀请所有朋友来共襄盛举，在派对上「我」认识了一个很可爱的女生，只可惜当天没要到连络方式，也不知道对方的名字，只有一起拍了一张照片，回家後心心念念那个女孩，好想再见她一面，於是我决定动用我的人脉， 来找到那个心仪的女孩!

每个人都是一个节点(node)相邻的节点会有边(edge)连接着

於是我决定拜托我的三个好朋友，问他们认不认识这个女孩，结果三个朋友都说不认识，但很热心地帮我问了他们的朋友有没有人认识这个女孩，下图的蓝色节点代表是我认识的朋友，绿色节点则是朋友的朋友，所以我会先问过所有我认识的朋友(first degree第一层)，而我的朋友会再去问他们的朋友(second degree第二层)。

从上面的故事我们可以知道，广度优先的搜寻顺序会是先走访相邻节点，都走访完了，就往下一层继续走访，广度优先搜寻采用queue来实作，因为queue具有先进後出的特性，可以确保先搜寻到的节点，会优先成为下一个搜寻起点。
那麽就用js来实作Breadth First Search，在开始之前我们要先建立一个Graph

先用js实作出这个Graph

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

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

let result = [];
const DFT = (starter) => {
    starter.visited = true;
    result.push(starter.value);
    starter.neighbors.forEach((element) => {
        if (!element.visited) DFT(element);
    });
    return result;
};

DFT(A);

//输出结果 ["A", "B", "E", "F", "C", "D", "G", "H"]

参考资料: breadth-first-search-a-simple-explanation