深度优先遍历算法代码

深度优先遍历算法是一种用于遍历或搜寻树或图的算法，其说的简单点就是从一个这个节点开始，一直找到底端，返回到这个节点，再找其他的。

深度优先遍历算法的思想就是把图看成一棵树，按照深度优先的原则来遍历。具体的原则是，从某个顶点出发，访问完它的子节点，再依次访问从这些子节点出发的子节点。这样沿着每一条路径递归进行搜索，直到找到目标或者搜索到底。深度优先遍历算法需要用到栈来记录当前遍历的路径，每次遍历到一个节点时先将其标记，然后将该节点加入栈中，再将其的第一个未被访问的节点作为下一个遍历的节点。

示例代码如下：

```

function depthFirstSearch(root) {

let stack = [root]

while (stack.length) {

let node = stack.pop()

if (node.visited) {

continue

}

node.visited = true

// process

for (let neighbor of node.neighbors) {

stack.push(neighbor)

}

}

}

```

上述代码中，`root` 是根节点，`node.neighbors` 是指节点 `node` 的邻居节点，`node.visited` 是用于标记是否已经被访问。

深度优先遍历算法的时间复杂度为 $O(n+m)$，其中 $n$ 为节点数，$m$ 为边数。其空间复杂度也为 $O(n+m)$，因为需要用到栈来记录遍历的路径。但是在实际应用中，可能会因为递归深度过大而引起栈溢出，因此需要注意如何优化算法。

如何优化深度优先遍历算法？

1. 递归深度优化：可以使用尾递归来优化递归深度，尾递归在递归过程中只保留一个栈帧，因此不会引起栈溢出。示例代码如下：

```

function depthFirstSearch(node, visited) {

visited[node] = true

// process

for (let neighbor of node.neighbors) {

if (!visited[neighbor]) {

depthFirstSearch(neighbor, visited)

}

}

}

```

2. 非递归深度优化：可以使用深度限制防止递归深度过大，也就是说如果深度达到一定值就转换为广度优先遍历。示例代码如下：

```

function depthFirstSearch(root) {

let stack = [{ node: root, depth: 0 }]

while (stack.length) {

let { node, depth } = stack.pop()

if (node.visited) {

continue

}

node.visited = true

// process

if (depth < 100) {

for (let neighbor of node.neighbors) {

stack.push({ node: neighbor, depth: depth + 1 })

}

} else {

breadthFirstSearch(node)

}

}

}

function breadthFirstSearch(node) {

let queue = [node]

while (queue.length) {

let node = queue.shift()

if (node.visited) {

continue

}

node.visited = true

// process

for (let neighbor of node.neighbors) {

queue.push(neighbor)

}

}

}

```

上述代码中，`depth` 用于记录深度，如果深度达到一定值 `100` 就转换为广度优先遍历。

深度优先遍历算法是一种非常常用的算法，在图论中很有用。但是在应用中，需要注意一些细节问题，比如递归深度和栈的空间占用等。可以通过一些优化方法像上述代码中所展示的来解决这些问题，从而提高算法的效率。