深度优先遍历算法代码
深度优先遍历算法是一种用于遍历或搜寻树或图的算法，其说的简单点就是从一个这个节点开始，一直找到底端，返回到这个节点，再找其他的。
深度优先遍历算法的思想就是把图看成一棵树，按照深度优先的原则来遍历。具体的原则是，从某个顶点出发，访问完它的子节点，再依次访问从这些子节点出发的子节点。这样沿着每一条路径递归进行搜索，直到找到目标或者搜索到底。深度优先遍历算法需要用到栈来记录当前遍历的路径，每次遍历到一个节点时先将其标记，然后将该节点加入栈中，再将其的第一个未被访问的节点作为下一个遍历的节点。
示例代码如下：
```
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` 就转换为广度优先遍历。
深度优先遍历算法是一种非常常用的算法，在图论中很有用。但是在应用中，需要注意一些细节问题，比如递归深度和栈的空间占用等。可以通过一些优化方法像上述代码中所展示的来解决这些问题，从而提高算法的效率。
