图遍历算法

图遍历算法，本质上就是一个更泛的树遍历算法。其遍历本质其实还是递归与回溯。

图的数据结构表示形式多以邻接表和邻接矩阵为主，这样能比较清晰的表示图中节点的连接关系。

邻接表的表示形式多以二维数组或集合（Set）数组为主，主要是表现对于每一个节点，其相邻的节点有哪些。数组形式也能表明对于每一个元素，其所对应的出度是什么。

邻接矩阵的表现形式为二维数组。横纵轴分别为每个节点，单元格中的值为从节点 A 至节点 B 的权重。

有向无环图 (DAG) 的遍历

无环图的特点在于不需要判断当前节点是否被访问过，可以节省一个 visited 的数组空间。

这种题型的遍历方式与多叉树的遍历十分相似，都是递归其所有子节点。

这类题型基本上都是需要达到目标点时的路径，因此需要维护一个 path 数组来记录每一次经过的节点。

与回溯法类似，每消费完当前节点后，一定要记得将当前节点从选择路径中去除，来撤销当前选择，便于下一个递归函数继承 path。

这类题型典型代表是 [797] 所有可能的路径。

  // 结果数组
  const res: number[][] = [];
  // 记录已遍历过的路径
  const path: number[] = [];

  traverse(root);
  return res;

  function traverse(curr: Node) {
    // 添加当前节点到路径中
    path.push(curr);

    // 遍历到达终点
    if (curr 到达目标点） {
      // 拷贝一份当前路径，将其添加到结果数组中
      res.push([...path]);
      // 从路径中移除当前节点，相当于回溯法中的撤销选择
      path.pop();
      return;
    }

    // 递归所有相邻节点
    for (const adjacent of graph[curr]) {
      traverse(adjacent);
    }

    // 从路径中移除当前节点，相当于回溯法中的撤销选择
    path.pop();
  }

题型参考：

1. [797] 所有可能的路径

图的成环检测

那么，如果不确定图是否是一个 DAG，那么该如何进行检测呢？

我们只需要再多维护一个 visited 数组，记录下每个已遍历过的节点。

  const visited: boolean[] = [];
  const onPath: boolean[] = [];

  // 此处是图的邻接表
  const graph: Set<number>[];

  let hasCycle = false;
  // 从每个节点为起点，开始进行遍历，保证每一个节点都被遍历到
  for (let i = 0; i < numCourses; i++) {
    traverse(i);
  }

  return !hasCycle;

  function traverse(index: number) {
    // 当前路径中的节点被再一次访问到了，说明出现了环
    if (onPath[index]) {
      hasCycle = true;
      // 已经发现环，则直接退出
      return;
    }

    // 若已经遍历过该节点，则剪枝
    if (visited[index]) {
      return;
    }

    // 做选择
    visited[index] = true;
    onPath[index] = true;
    // 递归遍历子节点
    for (const childIndex of graph[index]) {
      traverse(childIndex);
    }
    // 撤销选择
    onPath[index] = false;
  }

题型参考：

1. [207] 课程表

拓扑排序

拓扑排序。

注意，有环图是无法进行拓扑排序的。因此若不确定图无环，在进行拓扑排序前，需要先进行一次环检测算法。

拓扑排序其实就是图的后序遍历结果。因此与图的遍历方式密切相关。

  const res = [];
  traverse(root);
  return res;

  function traverse(curr: Node) {
    // 添加当前节点到路径中
    path.push(curr);

    // 遍历到达终点
    if (curr 到达目标点） {
      // 拷贝一份当前路径，将其添加到结果数组中
      res.push([...path]);
      // 从路径中移除当前节点，相当于回溯法中的撤销选择
      path.pop();
      return;
    }

    // 递归所有相邻节点
    for (const adjacent of graph[curr]) {
      traverse(adjacent);
    }
    // 后序遍历位置，记录当前值并塞入拓扑排序序列
    res.push(curr.val)
    // 从路径中移除当前节点，相当于回溯法中的撤销选择
    path.pop();
  }

题型参考：

1. [210] 课程表 ii

有权图的最短路径

有权图又是一种新的图类型。如果图的路径是有加权的，即相邻节点之间的距离并不一定为 1，那么通过普通 BFS 的方式第一次遍历到的某节点并不一定就是最短的节点。因此，如果要求出这种情况下的最短路径，我们需要对普通图的 BFS 算法做出些改进。

首先需要改进的点是图的数据结构。由于路径的权重也是一个变量，因此我们对于一个邻接节点的表示方式应该为：

{
  to: number,
  weight: number
}

同理，我们每一次推队列的节点也应该是类似数据结构，为当前的节点 id，以及该节点通过该条路径算出的与起点的距离。

{
  curNodeId: number,
  cur2StartDistance: number
}

于此同时，我们可以建立一个最短路径数组 minDists，表示从 start 位置到各个点的最短距离。类似于动态规划的 dp 数组，能够帮我们存储每一个节点距离起点的最小距离，同时提前进行剪枝判断。

在遍历出队节点的每个子节点时，我们会将会比较当前这条加权路径与起点的距离，与在 minDists 中已知的子节点最短距离相比，只有当发现更短加权路径时，才进行最短路径更新，并将子节点以及新的最短距离塞入队列便于进行下一次遍历。否则说明该路径不是最优的，剪枝丢弃。

经过这样一番改造，实际上我们就实现了一个迪杰斯特拉算法的基础结构。它能获取到由某一起点到图中每个节点的最短加权距离。

  const graph: { to: number; weight: number }[][] = Array(n + 1)
    .fill(0)
    .map(x => Array());
  const distances = dijkstra(start);

  function dijkstra(start: number): number[] {
    const minDists: number[] = Array(n + 1).fill(Number.MAX_VALUE);
    // 去除无意义的节点距离
    minDists[0] = -1;
    // 起点距离自己的最短距离是 0
    minDists[start] = 0;

    const queue = [{ curId: start, curToStartDist: 0 }];

    while (queue.length > 0) {
      const { curId, curToStartDist } = queue.shift();
      // 与当前路径到该节点相比，已经有更短的路径了，剪枝
      if (curToStartDist > minDists[curId]) {
        continue;
      }

      // 遍历所有邻接节点，以期望获取更小距离
      for (const { to, weight } of graph[curId]) {
        // 判断从当前节点到相邻节点的这条加权路径是否更短
        const newDistance = minDists[curId] + weight;
        if (newDistance < minDists[to]) {
          //  如果更短，更新相邻节点的最短路径
          // 由于该路径是可行的，将该路径信息加入到队列中等待下次递归
          minDists[to] = newDistance;
          queue.push({
            curId: to,
            curToStartDist: newDistance
          });
        }
      }
    }
    return minDists;
  }

题型参考：

1. [743] 网络延迟时间