图

图的相关术语

图是网络结构的抽象模型。是一组由边连接的节点（或顶点）

任何二元关系都可以用图来表示。

数学上表示为 , 表示一组顶点， 表示一组边，连接中的顶点

相关概念

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

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

• 路径是顶点v1, v2, …, vk 的一个连续序列，其中vi 和vi+1 是相邻的。以上一示意图中的图为例，其中包含路径A B E I 和A C D G。

• 简单路径要求不包含重复的顶点。举个例子，A D G 是一条简单路径。除去最后一个顶点（因为它和第一个顶点是同一个顶点），环也是一个简单路径，比如A D C A（最后一个顶点重新回到A）

• 如果图中不存在环，则称该图是无环的。如果图中每两个顶点间都存在路径，则该图是连通的。

有向图 无向图

图可以是无向的（边没有方向）或是有向的（有向图）。第一张图是无向图，下面这张是有向图

如果图中每两个顶点间在双向上都存在路径，则该图是强连通的。例如，C 和D 是强连通的，而A 和B 不是强连通的。

图还可以是未加权的（目前为止我们看到的图都是未加权的）或是加权的。如下图所示，加权图的边被赋予了权值。

应用

• 搜索图中的一个特定顶点或搜索一条特定边

• 寻找图中的一条路径（从一个顶点到另一个顶点

• 寻找两个顶点之间的最短路径，以及环检测。

图的表示

邻接矩阵

每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点之间的连接。

如果索引为i 的节点和索引为 j 的节点相邻，则 array[i][j] === 1，否则array[i][j] === 0，如下图所示。

由于不是强连通图（每两个节点间都存在路径），所以数组中有大量的0

给定顶点的相邻顶点，即使该顶点只有一个相邻顶点，我们也不得不迭代一整行。

邻接矩阵表示法不够好的另一个理由是，图中顶点的数量可能会改变，修改二维数组不够灵活。

邻接表

邻接表由图中每个顶点的相邻顶点列表所组成。

存在好几种方式来表示这种数据结构。我们可以用列表（数组）、链表，甚至是散列表或是字典来表示相邻顶点列表。

对大多数问题来说都是更好的选择

但要找出顶点 v 和 w 是否相邻，使用邻接矩阵会比较快

关联矩阵

关联矩阵中，矩阵的行表示顶点，列表示边。如下图所示，

使用二维数组来表示两者之间的连通性，如果顶点 v 是边 e 的入射点，则 array[v][e] === 1

否则，array[v][e] === 0

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

创建Graph 类

类的结构

• 图是否有向，默认无无向图 ①

• 使用一个数组来储存顶点的名字 ②

• 使用一个字典来储存邻接表，字典将会使用顶点的名字作为键，邻接顶点列表作为值 ③

class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // ①
    this.vertices = []; // ②
    this.adjList = new Map(); // ③
  }
}

插入顶点方法

• 如果顶点不存 ④ 在顶点列表中添加节点 ⑤

• 在邻接表中为该顶点创建空数组 ⑥

addVertex(v) {
  if (!this.vertices.has(v)) { // ④
    this.vertices.push(v); // ⑤ 
    this.adjList.add(v, []); // ⑥
  }
}

建立链接方法

• 如果建立链接的两个点不在顶点列表中，要先填入顶点列表

• 将 w 加入到 v 的邻接表中，表示添加了一条自顶点 v 到顶点 w 的边

• 无向图需要添加一条自 w 到 v 的边

addEdge(v, w) {
  if (!this.adjList.has(v)) {
    this.addVertex(v);
  }
  if (!this.adjList.has(w)) {
    this.addVertex(w);
  }
  this.adjList.get(v).push(w);
  if (!this.isDirected) {
    this.adjList.get(w).push(v);
  }
}

请注意我们只是往数组里新增元素，因为数组已经在行 ⑥ 被初始化了

取值

一个返回顶点列表，另一个返回邻接表

getVertices() {
  return this.vertices;
}
getAdjList() {
  return this.adjList;
}

测试

class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // {1}
    this.vertices = []; // {2}
    this.adjList = new Map(); // {3}
  }
  addVertex(v) {
    if (!this.vertices.includes(v)) { // {5}
      this.vertices.push(v); // {6}
      this.adjList.set(v, []); // {7}
    }
  }
  addEdge(v, w) {
    if (!this.adjList.has(v)) {
      this.addVertex(v);
    }
    if (!this.adjList.has(w)) {
      this.addVertex(w);
    }
    this.adjList.get(v).push(w);
    if (!this.isDirected) {
      this.adjList.get(w).push(v);
    }
  }
  getVertices() {
    return this.vertices;
  }
  getAdjList() {
    return this.adjList;
  }
  toString() {
    let s = '';
    for (let i = 0; i < this.vertices.length; i++) { // {15}
      s += `${this.vertices[i]} -> `;
      const neighbors = this.adjList.get(this.vertices[i]); // {16}
      for (let j = 0; j < neighbors.length; j++) { // {17}
        s += `${neighbors[j]} `;
      }
      s += '\n'; // {18}
    }
    return s;
  }
}
const graph = new Graph();
const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']; // {12}
for (let i = 0; i < myVertices.length; i++) { // {13}
  graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B'); // {14}

graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

console.log(graph.toString());

图的遍历

有两种算法可以对图进行遍历：广度优先搜索（breadth-first search，BFS） 和 深度优先搜索（depth-first search，DFS）

图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环，等等。

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

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

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

广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点列表的数据结构，如下表所示。

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

广度优先遍历

队列结构是广度优先遍历的精髓

从起点节点开始相邻的节点会被添加到队列中

因为队列有先进先出的性质，所以相邻的节点在遍历队列的时候会先被拿到，从而是实现了广度优先遍历

下一个关键点是如何知道节点没有被重复访问，解决办法是给访问过的节点打一个标记，如果下次访问相同的节点就跳过

WHITE: 表示没有被访问过 GARY: 访问过但是没有遍历子节点 BALCK: 节点和子结点都被访问过

// startVertex 指定遍历的起点
function breadthFirstSearch(graph, startVertex, callback) {
  // 拿到节点列表
  const vertices = graph.getVertices()
  // 拿到邻接表结构
  const adjList = graph.getAdjList();
  //标记是否访问过 默认所有节点都是白色没有访问过
  const color = {}
  for (var i = 0; i < vertices.length; i++) {
    color[vertices[i]] = "WHITE"
  }
  // 创建一个队列
  const queue = [];
  queue.push(startVertex);

  while (queue.length) {
    const node = queue.shift();
    const nabor = adjList.get(node)
    color[node] = 'GARY';
    for (let v of nabor) {
      if(color[v] === 'WHITE'){
        color[v] = "GARY"
        queue.push(v);
      }
    }
    color[v] = "BLACK"
    console.log(node);
  }
}
breadthFirstSearch(graph,myVertices[0])

使用广度优先寻找最短路径

因为使用了广度优先，所以会先访问距离为1的节点，然后是距离为2的节点，路径长的那一条线路，因为同一个节点被访问过，所以不会被记录，从而记录的都是每个节点到起点的最短路径

// startVertex 指定遍历的起点
function breadthFirstSearch(graph, startVertex, callback) {
  // 拿到节点列表
  const vertices = graph.getVertices()
  // 拿到邻接表结构
  const adjList = graph.getAdjList();
  //标记是否访问过 默认所有节点都是白色没有访问过
  const color = {}
  // 距离
  const distance = {};
  // 回溯节点 标识上一个节点是什么
  const predecessors = {}
  for (let i = 0; i < vertices.length; i++) {
    color[vertices[i]] = "WHITE"
  }
  // 创建一个队列
  const queue = [];
  queue.push(startVertex);

  // 初始化默认距离，和回溯节点
  for(let i = 0; i < vertices.length; i++){
    distance[vertices[i]] = 0;
    predecessors[vertices[i]] = null
  }

  while (queue.length) {
    const node = queue.shift();
    const nabor = adjList.get(node)
    color[node] = 'GARY';
    for (let v of nabor) {
      if (color[v] === 'WHITE') {
        // 上级节点的最短路进
        distance[v] = distance[node] + 1;
        // 指定当前节点的上级节点
        predecessors[v] = node;
        color[v] = "GARY"
        queue.push(v);
      }
    }
  }
  console.log(
    distance,
    predecessors
  )
}
breadthFirstSearch(graph, myVertices[0])

通过生成的前溯表以及所有的节点我们可以生成每个节点到头节点的最短路径

// 遍历每一个节点
for (let v of myVertices) {
  const path = [];
  // 如果当前节点不是头节点，就存入上一个节点
  for (let w = v; w !== null; w = shortestPathA.predecessors[w]) {
    path.push(w);
  }
  let s = path.pop();
  //反向拼接每一个节点
  while (path.length) {
    s += '-' + path.pop()
  }
  console.log(s);
}

深度优先遍历

因为深度优先需要把一条路径遍历到底，所以拿到的节点需要继续遍子结点

所以深度优先的精髓就是栈的结构，拿到的子结点加入栈中，由于栈先进先出可以继续访问下层的子结点

const fn = function (graph) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  for (let v of vertices) {
    color[v] = "WHITE";
  }
  // 栈结构
  const stack = [];
  stack.unshift(vertices[0]);
  // 如果栈不为空就继续遍历
  while (stack.length) {
    const v = stack.shift();
    // 如果没有访问过就访问子结点
    if (color[v] === "WHITE") {
      color[v] = 'GARY';
      // 获取到子结点 放入栈中
      const nabor = adjList.get(v);
      for (let vn of nabor.reverse()) {
        stack.unshift(vn);
      }
    }
  }
}
fn(graph)

这种写法可以实现遍历，但是不方便统计某个节点的子结点是否全部遍历，也就是置成BLACK

另一个关键点，函数递归调用也可以调用栈，保存每个函数的调用帧, 所以深度优先也常用递归来解决

const fn = function (graph) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  for (let v of vertices) {
    color[v] = "WHITE";
  }
  depthFirstSearch(vertices[0], adjList, color);
}
const depthFirstSearch = function (v, adjList, color) {
  const nabor = adjList.get(v);
  if (color[v] === 'WHITE') {
  console.log(v);

    color[v] = 'GARY'
    for (let vn of nabor) {
      depthFirstSearch(vn, adjList, color);
    }
    // 子结点遍历完成之后标记为黑色
    color[v] === 'BLACK'
  }
}
fn(graph)

加入节点信息

在遍历图的时候加入更多的节点信息

1.每个节点的发现时间，到达某个节点经历的步数
2.每个节点的访问时间，某个节点所有子结点都被访问过的步数
3.节点的前溯节点表

const depthFirstSearch = function (v, adjList, color, find, visit, back, time) {
  const nabor = adjList.get(v);
  if (color[v] === 'WHITE') {
    find[v] = ++(time.t);
    color[v] = 'GARY'
    for (let vn of nabor) {
      back[vn] = v;
      depthFirstSearch(vn, adjList, color, find, visit, back, time);
    }
    color[v] === 'BLACK'
    visit[v] = ++(time.t);
  }
}
const fn = function (graph,) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  const find = {};// 发现时间
  const visit = {};// 访问时间
  const back = {};// 回溯时间
  const time = { t: 0 }//用于计时
  for (let v of vertices) {
    color[v] = "WHITE";
    //初始化
    find[v] = 0;
    visit[v] = 0;
    back[v] = null;
  }
  depthFirstSearch(vertices[0], adjList, color, find, visit, back, time);
  return {
    find, visit, back, time
  }
}
fn(graph)

通过深度优先搜索拓扑排序

有些任务需要按顺序执行，而且不同的任务会公用一些子任务，编排这些有序任务被成为拓扑排序

这些任务形成了有向无环图，通过上面一节添加的节点信息，生成这些任务的执行顺序

首先生成图

graph = new Graph(true); // 有向图
myVertices = ['A', 'B', 'C', 'D', 'E', 'F'];
for (i = 0; i < myVertices.length; i++) {
    graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('F', 'E');

添加节点信息

const depthFirstSearch = function (v, adjList, color, find, visit, back, time) {
      const nabor = adjList.get(v);
      if (color[v] === 'WHITE') {
        find[v] = ++(time.t);
        color[v] = 'GARY'
        for (let vn of nabor) {
          back[vn] = v;
          depthFirstSearch(vn, adjList, color, find, visit, back, time);
        }
        color[v] === 'BLACK'
        visit[v] = ++(time.t);
      }
    }
    const fn = function (graph,) {
      const vertices = graph.getVertices();
      const adjList = graph.getAdjList();
      const color = {};
      const find = {};// 发现时间
      const visit = {};// 访问时间
      const back = {};// 回溯时间
      const time = { t: 0 }//用于计时
      for (let v of vertices) {
        color[v] = "WHITE";
        //初始化
        find[v] = 0;
        visit[v] = 0;
        back[v] = null;
      }
      // 因为有向图，每个节点不一定能到达其他节点
      for(let v of vertices){
        depthFirstSearch(v, adjList, color, find, visit, back, time);
      }
      return {
        find, visit, back, time
      }
    }
    fn(graph)

通过节点信息经行拓扑排序,按照访问时间从大到小

Object.entries(visit).sort((it, it2) => it2[1] - it1[1])

打赏