数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Javascript中的深度优先搜索遍历
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) {
// Create a Stack and add our initial node in it
let s = new Stack(this.nodes.length);
let explored = new Set();
s.push(node);
// Mark the first node as explored
explored.add(node);
// We'll continue till our Stack gets empty
while (!s.isEmpty()) {
let t = s.pop();
// Log every element that comes out of the Stack
console.log(t);
// 1. In the edges object, we search for nodes this node is directly connected to.
// 2. We filter out the nodes that have already been explored.
// 3. Then we mark each unexplored node as explored and push it to the Stack.
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");输出
这将给出输出。
A D E F B G C
更新于：2020年6月15日
4K+ 次查看
广告