Javascript 中的深度优先搜索遍历

javascriptweb developmentfront end technology

DFS 在访问兄弟顶点之前先访问子顶点；也就是说，它在探索任何特定路径的广度之前先遍历其深度。实现算法时通常使用堆栈(通常是程序通过递归调用的堆栈)。

以下是 DFS 的工作原理 −

访问相邻的未访问顶点。将其标记为已访问。显示它。将其推入堆栈。
如果未找到相邻顶点，则从堆栈中弹出一个顶点。 (它将弹出堆栈中所有没有相邻顶点的顶点。)
重复规则 1 和规则 2，直到堆栈为空。

让我们看一下 DFS 遍历的工作原理。

步骤	遍历	描述
1		初始化堆栈。
2		将 S 标记为已访问并将其放入堆栈。从 S 探索任何未访问的相邻节点。我们有三个节点，我们可以选择其中任何一个。在此示例中，我们将按字母顺序获取节点。
3		将 A 标记为已访问并将其放入堆栈。从 A 探索任何未访问的相邻节点。 S 和 D 都与 A 相邻，但我们只关注未访问的节点。
4		访问 D 并将其标记为已访问并放入堆栈。这里，我们有 B 和 C 节点，它们与 D 相邻，并且都未被访问过。但是，我们还是要按照字母顺序进行选择。
5		我们选择 B，将其标记为已访问并放入堆栈。这里 B 没有任何未访问的相邻节点。因此，我们从堆栈中弹出 B。
6		我们检查堆栈顶部是否返回到前一个节点，并检查它是否有任何未访问的节点。在这里，我们发现 D 位于堆栈顶部。
7		现在只有来自 D 的未访问相邻节点是 C。所以我们访问 C，将其标记为已访问并将其放入堆栈。

由于 C 没有任何未访问的相邻节点，因此我们不断弹出堆栈，直到找到具有未访问相邻节点的节点。在这种情况下，没有未访问的相邻节点，我们继续弹出直到堆栈为空。让我们看看如何在 JavaScript 中实现这一点。

示例

DFS(node) {
   // 创建一个 Stack 并在其中添加我们的初始节点
   let s = new Stack(this.nodes.length);
   let explored = new Set();
   s.push(node);

   // 将第一个节点标记为已探索
   explored.add(node);

   // 我们将继续，直到 Stack 变空
   while (!s.isEmpty()) {
      let t = s.pop();

   // 记录从 Stack 中出来的每个元素
      console.log(t);

   // 1. 在边对象中，我们搜索此节点直接连接到的节点。
   // 2. 我们过滤掉已经被探索过的节点。
   // 3. 然后我们将每个未探索的节点标记为已探索并将其推送到堆栈。
   this.edges[t]
   .filter(n => !explored.has(n))
   .forEach(n => {
      explored.add(n);
      s.push(n);
      });
   }
}

嗯，这很简单。我们实际上只是将队列换成了堆栈，然后我们就有了 DFS。这实际上是两者之间的唯一区别。DFS 也可以使用递归来实现。但在这种情况下最好避免这种情况，因为更大的图意味着我们需要额外的内存来跟踪调用堆栈。

您可以使用以下方法进行测试 −

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");

g.DFS("A");