图

图的相关术语

图是网络结构的抽象模型。图是一组由边连接的节点。由一条边连接在一起的顶点称为相邻顶点。一个顶点的度是其相邻顶点的数量。路径是顶点的一个连续序列。简单路径要求不包含重复的顶点。环是除去最后一个顶点的简单路径。如果图中每两个顶点之间都存在路径，则该图是连通的。

有向图和无向图

图可以是无向的或是有向的。如果图中每两个顶点间在双向上都存在路径，则该图是强连通的。图还可以是未加权的或是加权的。

图的表示

邻接矩阵

图最常见的实现是邻接矩阵。每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点之间的连接。如果索引为i的节点和索引为j的节点相邻，则array[i][j] === 1，否则为0。

不是强连通的图如果用邻接矩阵来表示，则矩阵中将会有很多0，这意味着我们浪费了计算机存储空间来表示根本不存在的边。

邻接表

邻接表由图中每个顶点的相邻顶点列表所组成。可以用列表、链表、散列表、字典来表示相邻顶点列表。

关联矩阵

在关联矩阵中，矩阵的行表示顶点，列表示边。通常用于边的数量比顶点多的情况，以节省空间和内存。

创建Graph类

接收一个参数来表示图是否有向，默认情况下，图是无向的。用一个数组来存储图中所有顶点的名字，用字典来存储邻接表。字典将会使用顶点的名字作为键，邻接顶点列表作为值。

  1. class Graph {
  2.     constructor(isDirected = false) {
  3.         this.isDirected = isDirected;
  4.         this.vertices = [];
  5.         this.adjList = new Dictionary();
  6.     }
  7.     //接着实现两个方法，一个用来向图中添加一个新的顶点，一个用来添加顶点之间的边。
  8.     addVertex(v) {
  9.         if(!this.vertices.includes(v)) {
  10.             this.vertices.push(v);
  11.             this.adjList.set(v, []);
  12.         }
  13.     }
  14.     addEdge(v, w) {
  15.         if(!this.adjList.get(v)) {
  16.             this.addVertex(v);
  17.         }
  18.         if(!this.adjList.get(w)) {
  19.             this.addVertex(w);
  20.         }
  21.         this.adjList.get(v).push(w);
  22.         if(!this.isDirected) {
  23.             this.adjList.get(w).push(v);
  24.         }
  25.     }
  26.     //取值方法
  27.     getVertices() {
  28.         return this.vertices;
  29.     }
  30.     getAdjList() {
  31.         return this.adjList;
  32.     }
  33.     toString() {
  34.         let s = '';
  35.         for(let i = 0; i < this.vertices.length; i++) {
  36.             s += `${this.vertices[i]} -> `;
  37.             const neighbors = this.adjList.get(this.vertices[i]);
  38.             for(let j = 0; j < neighbors.length; j++) {
  39.                 s += `${neighbors[j]}`;
  40.             }
  41.             s += '\n';
  42.         }
  43.         return s;
  44.     }
  45. }

addEdge方法接收两个顶点作为参数，需要验证顶点是否存在于图中，不存在则加入顶点列表。

然后通过将w加入到v的邻接表中，我们添加了一条自v到w的边。如果要实现无向图，需要再添加一条反向的边。

图的遍历

算法有广度优先搜索和深度优先搜寻。

图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。

完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。

为了保证算法效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。

广度优先搜索和深度优先搜寻基本相同，只有一点不同，那就是待访问顶点的数据结构。

算法 数据结构 描述
深度优先搜寻 栈 将顶点存入栈，顶点是沿着路径被搜索的，存在新的相邻顶点去访问。
广度优先搜索 队列 将顶点存入队列，最先入队列的顶点先被搜索。

当要标注已经访问过的顶点时，我们用三种颜色反映它们的状态。

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

灰色：被访问过，但并未被搜索过。

黑色：被访问且完全探索过。

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

为了有助于在广度优先和深度优先中标记顶点，我们要使用Colors变量（作为一个枚举器）：

  1. const Colors = {
  2.     WHITE:0,
  3.     GREY:1,
  4.     BLACK:2
  5. }

两个算法还需要一个辅助对象来帮助存储顶点是否被访问过。在每个算法开头，所有的顶点会被标记为未访问（白色）。我们要用下面的函数初始化每个顶点的颜色。

  1. const initializeColor = vertices => {
  2.     const color = {};
  3.     for(let i = 0; i < vertices.length; i++) {
  4.         color[vertices[i]] = Colors.WHITE;
  5.     }
  6.     return color;
  7. };

广度优先搜索

会从指定的第一个顶点开始遍历图，先访问其所有的邻点（相邻顶点），就像一次访问图的一层。换句话说就是先宽后深地访问顶点。

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

  1. 创建一个队列Q。
  2. 标注v为被发现的（灰色），并将v入队列Q。

  3. 如果Q非空，则运行以下步骤：

    1. 将u从Q中出队列；
    2. 标注u为被发现的（灰色）；
    3. 将u所有未被访问过的邻点（白色）入队列；
    4. 标注u为已被搜索的（黑色）。
  1. export const breadthFirstSearch = (graph, startVertex, callback) => {
  2.     const vertices = graph.getVertices();
  3.     const adjList = graph.getAdjList();
  4.     const color = initializeColor(vertices);
  5.     const queue = new Queue();
  7.     queue.enqueue(startVertex);
  9.     while(!queue.isEmpty()) {
  10.         const u = queue.dequeue();
  11.         const neighbors = adjList.get(u);
  12.         color[u] = Colors.GREY;
  13.         for(let i = 0; i<neighbors.length; i++) {
  14.             const w = neighbors[i];    
  15.             if(color[w] === Colors.WHITE) {
  16.                 color[w] = Colors.GREY;
  17.                 queue.enqueue(w);
  18.             }
  19.         }
  20.         color[u] = Colors.BLACK;
  21.         if(callback) {
  22.             callback(u);
  23.         }
  24.     }
  25. }

1.使用BFS寻找最短路径

考虑如何解决以下问题：给定一个图G和源顶点v，找出每个顶点u和v之间最短路径的距离。

对于给定顶点v，广度优先搜索会访问所有与其距离为1的顶点，接着是距离为2的顶点，以此类推。所以，可以用广度优先算法解决这个问题，可以修改上面的算法：

从v到u的距离distances[u]；前溯点predecessors[u]，用来推导出从v到其他每个顶点u的最短路径。

  1. const BFS = (graph, startVertex) => {
  2.     const vertices = graph.getVertices();
  3.     const adjList = graph.getAdjList();
  4.     const color = initializeColor(vertices);
  5.     const queue = new Queue();
  6.     const distances = {};
  7.     const predecessors = {};
  8.     queue.enqueue(startVertex);
  10.     for(let i = 0; i < vertices.length; i++) {
  11.         //用0初始化数组
  12.         distances[vertices[i]] = 0;
  13.         predecessors[vertices[i]] = null;
  14.     }
  15.     while(!queue.isEmpty()) {
  16.         const u = queue.dequeue();
  17.         const neighbors = adjList.get(u);
  18.         color[u] = Colors.GREY;
  19.         for(let i = 0; i<neighbors.length; i++) {
  20.             if(color[w] === Colors.WHITE) {
  21.                 color[w] = Colors.GREY;
  22.                 distances[w] = distances[u] + 1;
  23.                 predecessors[w] = u;
  24.                 queue.enqueue(w);
  25.             }
  26.         }
  27.         color[u] = Colors.BLACK;
  28.     }
  29.     return {
  30.             distances, predecessors
  31.         };
  32. }

深度优先搜寻

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

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

要访问顶点v，需要：

  1. 标注v为被发现的（灰色）；
  2. 对于v的所有未访问（白色）的邻点w，访问顶点w；
  3. 标注v为已被探索的（黑色）。

深度优先搜索的步骤是递归的，这意味着深度优先搜索算法使用栈来存储函数调用。

  1. //深度优先搜索
  2. const depthFirstSearch = (graph, callback) => {
  3.     const vertices = graph.getVertices();
  4.     const adjList = graph.getAdjList();
  5.     const color = initializeColor(vertices);
  7.     for (let i = 0; i < vertices.length; i++) {
  8.         if (color[vertices[i]] === Colors.WHITE) {
  9.             depthFirstSearchVisit(vertices[i], color, adjList, callback);
  10.         }
  11.     }
  12. };
  14. const depthFirstSearchVisit = (u, color, adjList, callback) => {
  15.     color[u] = Colors.GREY;
  16.     if (callback) {
  17.         callback(u);
  18.     }
  19.     const neighbors = adjList.get(u);
  20.     for (let i = 0; i < neighbors.length; i++) {
  21.         const w = neighbors[i];
  22.         if (color[w] === Colors.WHITE) {
  23.             depthFirstSearchVisit(w, color, adjList, callback);
  24.         }
  25.     }
  26.     color[u] = Colors.BLACK;
  27. };