图的深度优先搜索 - wangshengliang

图的深度优先搜索，其实就是深度优先遍历，如果用一句话来概括，那就是 不撞南墙不回头。举个例子，假设有如下的有向图：

然后我们从 V1 出发，那就可以是这样的顺序：

V1 → V2 → V5

首先从 V1 出发，下一个顶点到 V2，然后再下一个顶点到 V5。到了 V5 后，发现后面没有顶点了，则回退到 V2，V2 也没有其他的路，于是回退到 V1，然后访问 V4 和 V3。因此整个遍历出来的顺序为：

V1 → V2 → V5 → V4 → V3

回到 V1 后，到下一个顶点 V4，之后是顶点 V3，从而完成了一整个图的遍历。

需要注意的是，深度优先遍历的路径不是唯一的，哪怕是从 V1 出发，也可以有如下不同的遍历路径：

V1 → V4 → V3 → V2 → V5
V1 → V4 → V3 → V5 → V2

在上面的例子中，我们选择了 V1 作为我们的起始顶点。那能不能选择其他顶点作为起始顶点呢？

其实也是可以的，例如这里我们选择 V2 作为起始顶点，那么 V2 能够走的路径就是：

V2 → V5

此时你会发现并没有遍历完整张图，所以就还需要再选择一个未遍历的顶点作为起始顶点来进行遍历。

一般来讲，我们可以选择一个 入度为 0 的顶点 来作为起始顶点，因此在上面的示例中，选择 V1 作为起始顶点是最合适的。

对于无向图的深度优先遍历，道理是一样的，不过相对于有向图，无向图能够走的边会更多一些。例如下面的无向图：

采用深度优先遍历能够走的路径有：

V1 → V2 → V3 → V4 → V5
V1 → V2 → V3 → V5 → V4
V1 → V2 → V5 → V3 → V4
V1 → V4 → V3 → V2 → V5
V1 → V4 → V3 → V5 → V2

一共有 5 条路径。

代码实现

dfs(startVertex){
  if(!this.adjacencyList.has(startVertex)) return [];

  const visited = new Set();
  const result = []; // 存储遍历的结果

  const dfsHelper = (vertex)=>{
    visited.add(vertex);
    result.push(vertex);

    for(let nodeObj of this.adjacencyList.get(vertex)){
      const v = nodeObj.node;
      if(!visited.has(v)){
        // 进入该分支，说明当前这个节点还没有遍历到
        dfsHelper(v);
      }
    }
  }
  dfsHelper(startVertex);

  return result;
}

-EOF-