dfs

DFS（深度优先搜索）简介

DFS是一种常见的图形搜索算法，从根节点开始，沿着一条路径走到底，然后回溯到上一个节点，再继续向下走，直到遍历完整个图。在实现上，可以使用递归和迭代两种方式。

递归实现DFS

递归实现DFS比较简单直观。我们可以先访问当前节点，然后递归遍历所有邻接节点。为了防止重复访问某个节点，需要使用一个visited数组记录已经访问过的节点。

代码如下：

voiddfs(intcur,vectorgraph,vector&visited){visited[cur]=true;for(inti=0;i< graph[cur].size(); i++) { int next = graph[cur][i]; if (!visited[next]) { dfs(next, graph, visited); } }}

迭代实现DFS

迭代实现DFS则需要借助栈来存储节点信息。我们先将根节点入栈，并标记为已访问。每次取出栈顶元素，并遍历所有邻接点，将未被访问过的邻接点入栈并标记为已访问。重复以上步骤直到栈为空。

代码如下：

voiddfs(vectorgraph,vector&visited){stacks;s.push(0);//根节点入栈visited[0]=true;//标记为已访问while(!s.empty()){intcur=s.top();s.pop();for(inti=0;i<graph[cur].size();i++){intnext=graph[cur][i];if(!visited[next]){//如果未被访问过，则入栈并标记为已访问s.push(next);visited[next]=true;}}}}

应用场景

DFS常用于求解图上的连通性问题、拓扑排序、欧拉回路等问题。在人工智能领域中也有广泛应用，例如AlphaGo中就使用了深度优先搜索算法。

总结

DFS是一种重要的图形搜索算法解决各种图论问题时都有广泛应用。通过递归或迭代两种方式都可以实现DFS。掌握好算法提高编程能力有很大帮助。