图的遍历

从图中某个顶点出发，沿图中的路径依次去访问图中的所有顶点，使得每一个顶点刚好被访问一次，这一过程就叫做图的遍历。

对图进行遍历，最常见到的两个算法是广度优先搜索（BFS）和深度优先搜索（DFS）算法。

生成树

在学习遍历算法之前，我们还要先学习一个知识：生成树。因为在对图进行遍历的时候，会指定一个根顶点作为遍历的入口，这样的话就可以把图看成是树来遍历了。

生成树是在研究图的遍历时产生的一个概念，我们在遍历一个连通图的所有顶点的时候，可以近似看做是在对一棵树进行遍历，而且图中的一些边很可能是不需要再次去走通的，比如某个结点已经被遍历过了，那么还有一些边连向它，那其它的这些边就感觉是多余的了，因为我延着一条路就能把所有结点都遍历完，不需要再走那些多余的通路了。

所以在把图转换成生成树的时候，假设原图的顶点 $V_n=n$Vn​=n，那么把原图的边减少到不能再少为止，一般减少到 $n-1$n−1 条就可以满足遍历所有结点的条件了，于是我们把这个新的边数最少的连通子图叫做该图的生成树。一个图可以拥有多棵生成树。

我们在生成树上随机取一个结点作为它的根节点，也就是对图进行遍历的起始顶点，这样我们对图进行遍历时就方便了一些。

在对图进行遍历的时候不一定需要这个生成树，比如接下来要讲解的两种遍历算法就没有刻意去做这一步操作。

深度优先搜索（DFS）

在之前，我们已经知道了图的存储结构，接下来就来实现图的深度优先搜索算法。

DFS 会从某个结点开始，按照某个深度依次往下遍历，就跟二叉树的先序遍历有点类似。

深度优先搜索遍历到最深层后会有一个回溯到根顶点的过程，所以就需要使用一个栈来保存这个访问的顺序，又因为函数的递归执行过程也相当于一个栈的执行过程，所以深度优先搜索就选用递归来实现。

本文使用邻接表来保存图的结构

/**
 * 保存顶点的链表结点
 * @param {*} vertex 顶点
 */
function Node(vertex) {
  this.vertex = vertex;
  this.next = null;
}

/**
 * 图的邻接表结构，为了实现 DFS 我们增加一个用来记录顶点访问记录的属性，
 * visited 初始化为 0
 * @param {*} length 长度
 */
function GraphList(length) {
  this.length = length;
  this.edges = [];
  for (let i = 0; i < length; i++) {
    this.edges[i] = null;
  }
  this.visited = [];
  for (let i = 0; i < length; i++) {
    this.visited[i] = 0;
  }
}

/**
 * 按倒序插入结点（结点的顺序如何没有关系）
 * @param {*} head 头结点
 * @param {*} index 顶点
 * @returns 倒序的链表
 */
function insertNode(head, index) {
  const node = new Node(index);
  node.next = head;
  head = node;
  return head;
}

/**
 * 创建邻接表，按照无向图来创建
 * @param {*} graph 图
 * @param {*} i 顶点
 * @param {*} j 顶点
 * @returns 
 */
function insertGraph(graph, i, j) {
  if (i < 0 || i >= graph.length || j < 0 || j >= graph.length) {
    return;
  }
  graph.edges[i] = insertNode(graph.edges[i], j);
  graph.edges[j] = insertNode(graph.edges[j], i);
}

/**
 * 深度优先搜索
 * @param {*} graph 图
 * @param {*} vertex 顶点
 */
function dfs(graph, vertex) {
  // 打印出当前遍历的顶点
  console.log(vertex);
  // 遍历过后打上已遍历的标
  graph.visited[vertex] = 1;
  // 从邻接表里面取出每一条链来遍历，用递归实现深度优先搜索
  for (let adj = graph.edges[vertex]; adj !== null; adj = adj.next) {
    if (!graph.visited[adj.vertex]) {
      dfs(graph, adj.vertex);
    }
  }
}

// 初始化有 5 个顶点的图
const graph = new GraphList(5);

// 加上如下关系
insertGraph(graph, 0, 1);
insertGraph(graph, 1, 2);
insertGraph(graph, 1, 3);
insertGraph(graph, 2, 3);
insertGraph(graph, 0, 4);
insertGraph(graph, 1, 4);

// 这样就能得到拥有如下关系的一张图：
//      0
//    /   \
//   1 --- 4
//  / \
// 2 - 3

console.log(graph);
// 随机选取一个顶点 1 开始进行深度优先遍历
dfs(graph, 1);

广度优先搜索（BFS）

广度优先搜索一般用来求解起点到各点的最短路径以及求两点之间的最优路径等问题，最优路径问题以后再学，现在只需要知道它有这种作用。

广度优先搜索相对于深度优先搜索来说，它是一个以层为优先的遍历过程，比如先遍历完第二层才会进入到第三层的遍历，而深度优先搜索是一直往一个方向深度遍历进去，一直遍历到最后一层，才回溯出来遍历其它相邻的结点。

结合队列先进先出的特性，我们在对某层的结点进行遍历的时候，就可以使用队列的这种特性来保存已访问过的结点。

接下来我们来实现 BFS，以下代码中不包含在 DFS 中已定义过的图的相关代码。

/**
 * 队列结构
 * @param {*} length 队列长度
 */
function Queue(length) {
  this.data = [];
  this.head = 0;
  this.tail = -1;
  this.length = length;
}

/**
 * 入队
 * @param {*} queue 队列
 * @param {*} element 入队元素
 */
function push(queue, element) {
  if (queue.tail + 1 < queue.length) {
    queue.tail++;
    queue.data[queue.tail] = element;
  }
}

/**
 * 取得队首元素
 * @param {*} queue 队列
 * @returns 队首元素
 */
function front(queue) {
  return queue.data[queue.head];
}

/**
 * 出队
 * @param {*} queue 队列
 */
function pop(queue) {
  queue.head++;
}

/**
 * 判断队列是否为空
 * @param {*} queue 队列
 * @returns 
 */
function empty(queue) {
  if (queue.head > queue.tail) {
    return true;
  }
  return false;
}

/**
 * 广度优先搜索
 * @param {*} graph 图
 * @param {*} rootVertex 根结点
 */
function bfs(graph, rootVertex) {
  // 使用一个队列来保存遍历到的顶点
  const queue = new Queue(graph.length);
  // 首先把跟顶点放入队列中
  push(queue, rootVertex);
  // 把它标记为已访问
  graph.visited[rootVertex] = 1;
  // 接下来就从根结点开始遍历相邻的结点
  while (!empty(queue)) {
    // 从队列头取一个元素
    const vertex = front(queue);
    console.log(vertex);
    // 输出后，让其出队
    pop(queue);
    // 遍历邻接表中的链表，把遍历到的还没访问过的顶点入队
    for (let adj = graph.edges[vertex]; adj !== null; adj = adj.next) {
      // 如果顶点没有被访问过，就入队
      if (!graph.visited[adj.vertex]) {
        graph.visited[adj.vertex] = 1;
        push(queue, adj.vertex);
      }
    }
  }
}

// 这里使用的示例数据跟 DFS 的一样

// 初始化有 5 个顶点的图
const graph = new GraphList(5);

insertGraph(graph, 1, 0, 1);
insertGraph(graph, 1, 1, 2);
insertGraph(graph, 1, 1, 3);
insertGraph(graph, 1, 2, 3);
insertGraph(graph, 1, 0, 4);
insertGraph(graph, 1, 1, 4);

console.log(graph);
outputGraph(graph);
bfs(graph, 1);