本文已使用 Google Cloud Translation API 自动翻译。
某些文档最好以原文阅读。
在这篇文章中,我们将讨论深度优先搜索,一种遍历图形的方法。给定一个起始节点,深度优先搜索在回溯之前尽可能沿着每个分支探索。
算法的基本结构如下:
function depthFirstSearch(node) {
// base case: if node is null, return
if (node == null) {
return;
}
// mark node as visited
node.visited = true;
// do something with node
// ...
// recurse on each of node's unvisited children
for (let child of node.children) {
if (!child.visited) {
depthFirstSearch(child);
}
}
}
我们可以看到 depthFirstSearch 函数将一个节点作为输入。它做的第一件事是检查节点是否为空——如果是,函数简单地返回。如果该节点不为空,则将该节点标记为已访问,然后该函数对该节点执行某些操作。在我们的例子中,我们将简单地打印出节点。
之后,该函数循环遍历该节点的每个未访问的子节点,并对它们进行递归。
下面是 JavaScript 中深度优先搜索的简单实现:
function depthFirstSearch(node) {
if (node == null) {
return;
}
node.visited = true;
console.log(node.value);
for (let child of node.children) {
if (!child.visited) {
depthFirstSearch(child);
}
}
}
这是一个如何使用它的例子:
// create a graph
// the graph is an array of nodes, each of which has an array of children
let graph = [
{
value: 1,
children: [2, 3, 4]
},
{
value: 2,
children: [5, 6]
},
{
value: 3,
children: [7]
},
{
value: 4,
children: [8, 9]
},
{
value: 5,
children: []
},
{
value: 6,
children: []
},
{
value: 7,
children: []
},
{
value: 8,
children: []
},
{
value: 9,
children: []
}
];
// choose a starting node
let startingNode = graph[0];
// do the search
depthFirstSearch(startingNode);
运行上面的代码应该打印出以下内容:
1
2
5
6
3
7
4
8
9
尝试通过以下练习自己实现深度优先搜索:
以下是练习的答案: