## 数据结构 - 图

<img src='./image/tu-1.png' alt='' width=300 />

由一条边连接在一起的`顶点`称为: 相邻顶点, 比如，A 和 B 是相邻的，A 和 D 是相邻的，A 和 C 是相邻的，A 和 E 不是相邻的

**一个顶点的度是其相邻顶点的数量**。比如，A 和其他三个顶点相连接，因此，A 的度为 3; E 和其他两个顶点相连，因此，E 的度为 2。

### 创建图

声明图的骨架

```javascript
function Graph() {
  var vertices = []; // 定义数组来存储图中所有顶点的名字
  var adjList = new Dictionary(); // 字典来存储邻接表
}
```

[字典](./数据结构-字典.md) 将会使用顶点的名字作为键，邻接顶点列表作为值。vertices 数组和 adjList 字典两者都是我们 Graph 类的私有属性

接着，我们将实现两个方法: 一个用来向图中添加一个新的顶点(因为图实例化后是空的)， 另外一个方法用来添加顶点之间的边。

```javascript
// 这个方法接受顶点v作为参数。我们将该顶点添加到顶点列表中，并且在邻接表中，
// 设置顶点v作为键对应的字典值为一个空数组

this.addVertex = function(v) {
  vertices.push(v);
  adjList.set(v, []);
};
```

```javascript
// 这个方法接受两个顶点作为参数。
// 首先，通过将w加入到v的邻接表中，我们添加了一条自顶点v到顶点w的边
// 例子采用无向图，所以还要加一条自定点w到v的边

this.addEdge = function(v, w) {
  adjList.get(v).push(w);
  adjList.get(w).push(v);
};
```

具体请看这个例子: [createGraph.js]()

---

### 图的遍历

和树数据结构类似，我们可以访问图的所有节点。有两种算法可以对图进行遍历: `广度优先搜索(Breadth-First Search，BFS)` 和 `深度优先搜索(Depth-First Search，DFS)`。

图遍历可以用来干哈？

- 寻找特定的顶点

- 寻找两个顶点之间的路径

- 检查图是否连通

- 检查图是否含有环

|       算法       | 数据结构 |                                 描述                                 |
| :--------------: | :------: | :------------------------------------------------------------------: |
| 深度优先搜索 DFS |    栈    | 通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问 |
| 广度优先搜索 BFS |   队列   |            通过将顶点存入队列中，最先入队列的顶点先被探索            |

### 最短路径？

首先先搞明白一点，广度优先搜索(BFS)能够让我们找到两样东西之间的`最短路径`，也就是说，最短路径问题，用到的算法叫做 “广度优先搜索”，用到的数据结构是 “队列”

但是最短路径问题，不是只有`广度优先搜索算法`，比如`狄克斯特拉算法`，也是解决最短路径问题

> 广度优先搜索用于在非加权图中查找最短路径

> 狄克斯特拉算法用于在加权图中查找最短路径

总的来说，BFS 多用于寻找最短路径的问题，DFS 多用于快速发现底部节点。

废话说的有点多了，下面继续看 DFS 和 BFS，当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态。

- 白色:表示该顶点还没有被访问。

- 灰色:表示该顶点被访问过，但并未被探索过。

- 黑色:表示该顶点被访问过且被完全探索过。

这就是之前提到的务必访问每个顶点最多两次的原因

#### BFS

广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访
问图的一层。换句话说，就是先宽后深地访问顶点，如下图所示:

<div algin='center'>
  <img src='./image/tu-2.png' alt='' width=280 />
</div>

以下是从顶点 v 开始的广度优先搜索算法所遵循的步骤。

- (1) 创建一个队列 Q。

- (2) 将 v 标注为被发现的(灰色)，并将 v 入队列 Q。

- (3) 如果 Q 非空，则运行以下步骤:

  - (a) 将 u 从 Q 中出队列;
  - (b) 将标注 u 为被发现的(灰色);
  - (c) 将 u 所有未被访问过的邻点(白色)入队列;
  - (d) 将 u 标注为已被探索的(黑色)。

看看该如何实现这个 简易版的 BFS 算法 ？

```javascript
// 使用一个辅助数组 color。由于当算法开始执行时，所有的顶点颜色都是白色
var initializeColor = function() {
  var color = [];
  for (let i = 0; i < vertices.length; i++) {
    color[vertices[i]] = 'white';
  }
  return color;
};

this.bfs = function(v, callback) {
  var color = initializeColor(); // 1.初始化所有顶点
  var queue = new Queue(); // 2.初始化一个队列, 它将会存储待访问和待探索的顶点

  queue.enqueue(v); // 3.将起始点 v 入队列

  while (!queue.isEmpty()) {
    // 4. 队列非空
    var u = queue.dequeue(); // 5. 从队列中移除一个顶点
    neighbors = adjList.get(u); // 6. 从字典中取得它的邻接表
    color[u] = 'grey'; // 7. 将该顶点置为灰色，表示被访问过，但未被探索过

    for (let j = 0; j < neighbors.length; j++) {
      // 8. 对于出队的这个顶点，遍历它的相邻点
      var w = neighbors[j]; // 9. 取得这个点
      if (color[w] === 'white') {
        // 10. 如果这个点没有被访问过
        color[w] = 'grey'; // 11. 标注为发现了这点，但是还没有探索
        queue.enqueue(w); // 12. 将这个顶点加入到队列中
      }
    }
    color[u] = 'black'; // 13. 标注出队点这个顶点已经访问并探索完毕，下次不应该访问
    if (callback) {
      callback(u); // 14. 接受一个回调
    }
  }
};
```

OK，上边的只是一个 BFS 算法的工作原理，但是可以用该算法做更多事情，而不只是输出被访问顶点的顺序。例如，考虑如何来解决下面这个问题。

给定一个图 G 和源顶点 v，找出对每个顶点 u，u 和 v 之间最短路径的距离(以边的数量计)。

对于给定顶点 v，广度优先算法会访问所有与其距离为 1 的顶点，接着是距离为 2 的顶点， 以此类推。所以，可以用广度优先算法来解这个问题。我们可以修改 bfs 方法以返回给我们一 些信息:

- 从 v 到 u 的距离 d[u]

- 前溯点 pred[u]，用来推导出从 v 到其他每个顶点 u 的最短路径

改进版的 BFS 算法

```javascript
this.updateBFS = function() {
  var color = initializeColor(); // 1.初始化所有顶点
  var queue = new Queue(); // 2.初始化一个队列, 它将会存储待访问和待探索的顶点
  var d = []; // 3. 声明数组来表示距离
  var pred = []; // 4. 声明pred数组来表示前溯点

  queue.enqueue(v); // 5.将起始点 v 入队列

  for (let i = 0; i < vertices.length; i++) {
    d[vertices[i]] = 0; // 6.图中的每一个顶点，用0来初始化数组d
    pred[vertices[i]] = null; // 7. 用null来初始化数组pred
  }

  while (!queue.isEmpty()) {
    // 8. 队列非空
    var u = queue.dequeue(); // 9. 从队列中移除一个顶点
    neighbors = adjList.get(u); // 10. 从字典中取得它的邻接表
    color[u] = 'grey'; // 11. 将该顶点置为灰色，表示被访问过，但未被探索过

    for (let j = 0; j < neighbors.length; j++) {
      // 12. 对于出队的这个顶点，遍历它的相邻点
      var w = neighbors[j]; // 13. 取得这个点
      if (color[w] === 'white') {
        // 14. 如果这个点没有被访问过
        color[w] = 'grey'; // 15. 标注为发现了这点，但是还没有探索
        d[w] = d[u] + 1; // 16. 通过给d[u]加1来设置两点之间的距离
        pred[w] = u; // 17. 发现顶点u的邻点w时，则设置w的前溯点值为u
        queue.enqueue(w); // 18. 将这个顶点加入到队列中
      }
    }
    color[u] = 'black'; // 19. 标注出队点这个顶点已经访问并探索完毕，下次不应该访问

    // 20. 方法最后返回了一个包含d和pred的对象
    return {
      distances: d,
      predecessors: pred
    };
  }
};
```

---

#### DFS

深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶 点被访问了，接着原路回退并探索下一条路径。换句话说，它是先深度后广度地访问顶点，如下图所示:

<div algin='center'>
  <img src='./image/tu-3.png' alt=''width=280 />
</div>

深度优先搜索算法不需要一个源顶点。在深度优先搜索算法中，若图中顶点 v 未访问，则访问该顶点 v。

要访问顶点 v，照如下步骤做。

- (1) 标注 v 为被发现的(灰色)。

- (2) 对于 v 的所有未访问的邻点 w:

  - (a) 访问顶点 w。

- (3) 标注 v 为已被探索的(黑色)。

如你所见，_深度优先搜索的步骤是递归的_，这意味着深度优先搜索算法使用栈来存储函数调用(由递归调用所创建的栈)。

看看该如何实现这个 简易版的 DFS 算法 ？

```javascript
this.dfs = function(callback) {
  var color = initializeColor(); // 1.初始化所有顶点

  for (let i = 0; i < vertices.length; i++) {
    // 2. 对每一个未被访问过的顶点
    if (color[vertices[i]] === 'white') {
      dfsVisit(vertices[i], color, callback); // 3. 调用私有递归函数 dfsVisit
    }
  }
};

this.dfsVisit = function(u, color, callback) {
  color[u] = 'grey'; // 4. 置为被发现，但是还未探索
  if (callback) {
    callback(u);
  }

  var neighbors = adjList.get(u); // 5. 取得顶点 u 所有邻点的列表

  for (let j = 0; j < neighbors.length; j++) {
    // 6. 遍历所有邻点
    var w = neighbors[j]; // 7. 顶点u的每一个未被访问过的邻点w
    if (color[w] === 'white') {
      dfsVisit(w, color, callback); // 8. 调用dfsVisit函数，添加顶点w入栈
    }
  }
  color[u] = 'blank';
};
```

如以下图所示 :

<div algin='center'>
  <img src='./image/tu-4.png' alt='' width=800 />
</div>

---

> 我强烈推荐，先去看这篇 [搜索思想-DFS & BFS](https://zhuanlan.zhihu.com/p/24986203) 文章，然后接着去 youbute 看这个视频 [BFS、DFS 算法原理及 JS 实现](https://segmentfault.com/a/1190000012457151#articleHeader2)！！！

### 相关文章

- [搜索思想-DFS & BFS](https://zhuanlan.zhihu.com/p/24986203)

- [youtube DFS DFS 算法讲解](https://www.youtube.com/watch?v=oLtvUWpAnTQ)

- [BFS、DFS 算法原理及 JS 实现](https://segmentfault.com/a/1190000012457151#articleHeader2)

- [麻省理工学院公开课-最短路径算法](https://open.163.com/movie/2010/12/E/P/M6UTT5U0I_M6V2U4BEP.html)