建网站需要的设备,企业门户网站 php,宁波建网站可按需定制,php网站开发范例目录 一、引言二、算法步骤三、原理演示递归实现非递归实现#xff08;使用堆栈#xff09; 四、代码实战五、结论 一、引言 深度优先搜索#xff08;DFS#xff09;是一种在图或树中进行搜索的算法#xff0c;它沿着树的深度遍历树的节点#xff0c;尽可能深的搜索树的分… 目录 一、引言二、算法步骤三、原理演示递归实现非递归实现使用堆栈 四、代码实战五、结论 一、引言 深度优先搜索DFS是一种在图或树中进行搜索的算法它沿着树的深度遍历树的节点尽可能深的搜索树的分支。当节点v的所有边都已探寻过搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点则选择其中一个作为源节点并重复以上过程整个进程反复进行直到所有节点都被访问为止。 DFS是一种盲目搜索即它并不需要知道目标的位置只是尽可能地遍历所有可能的路径。因此它的搜索效率并不高特别是在面对大规模数据时。然而DFS可以找到目标值或解决目标问题对于解决NP问题作用很大。 此外DFS如同数据结构中的栈结构是一种后进先出的结构导致了所有的点进入栈时有一个顺序我们称之为 “DFS序”。 二、算法步骤 深度优先搜索算法的步骤如下 选取图中某一顶点Vi为出发点访问并标记该顶点。以Vi为当前顶点依次搜索Vi的每个邻接点Vj若Vj未被访问过则访问和标记邻接点Vj若Vj已被访问过则搜索Vi的下一个邻接点。以Vj为当前顶点重复步骤2直到图中和Vi有路径相通的顶点都被访问为止。若图中尚有顶点未被访问过非连通的情况下则可任取图中的一个未被访问的顶点作为出发点重复上述过程直至图中所有顶点都被访问。 三、原理演示
递归实现 选择起始节点从图中的一个起始节点开始将该节点标记为已访问。递归探索邻居节点对于当前节点遍历它的邻居节点。如果邻居节点尚未被访问就递归地调用深度优先搜索函数以此邻居节点为新的起始节点重复步骤1。回溯当当前节点的所有邻居节点都被访问后回溯到上一个节点并继续遍历其未被访问的邻居节点。重复步骤2和3直到图中的所有节点都被访问。 下面是递归实现深度优先搜索的示例代码 public void dfsRecursive(Node node, SetNode visited) {visited.add(node);System.out.print(node.value );for (Node neighbor : node.neighbors) {if (!visited.contains(neighbor)) {dfsRecursive(neighbor, visited);}}
}非递归实现使用堆栈 选择起始节点从图中的一个起始节点开始将该节点标记为已访问并将它入栈。迭代遍历使用一个循环不断从栈中弹出节点然后遍历它的邻居节点。探索邻居节点对于当前弹出的节点遍历其邻居节点。如果邻居节点尚未被访问就将其标记为已访问并将其入栈。重复步骤2和3直到栈为空。 下面是非递归实现深度优先搜索的示例代码 public void dfsIterative(Node start) {StackNode stack new Stack();SetNode visited new HashSet();stack.push(start);visited.add(start);while (!stack.isEmpty()) {Node current stack.pop();System.out.print(current.value );for (Node neighbor : current.neighbors) {if (!visited.contains(neighbor)) {stack.push(neighbor);visited.add(neighbor);}}}
}无论采用递归还是非递归方式深度优先搜索的关键思想是深入到尽可能深的层级直到无法再深入为止然后回溯到上一个节点继续探索。这一过程不断重复直到遍历整个图。深度优先搜索对于解决路径查找、拓扑排序、连通性检测等问题都非常有用。 四、代码实战 以下是深度优先搜索算法的Java代码实现 import java.util.*;public class DFS {private int V; // 顶点数量private LinkedListInteger adj[]; // 邻接表// 构造函数DFS(int v) {V v;adj new LinkedList[v];for (int i 0; i v; i) {adj[i] new LinkedList();}}// 添加边void addEdge(int v, int w) {adj[v].add(w);}// DFS函数void DFSUtil(int v, boolean visited[]) {// 标记当前节点为已访问并输出该节点visited[v] true;System.out.print(v );// 递归访问与v节点相邻的未访问节点IteratorInteger i adj[v].listIterator();while (i.hasNext()) {int n i.next();if (!visited[n])DFSUtil(n, visited);}}// DFS函数void DFS(int v) {// 标记所有顶点为未访问状态boolean visited[] new boolean[V];// 调用递归函数DFSUtil开始从顶点v进行DFS遍历DFSUtil(v, visited);}
}五、结论 我们一起来总结一下 深度优先搜索在计算机科学中有着广泛的应用例如用于遍历树或图的结构、查找路径、解决优化问题等。它的优点在于空间复杂度相对较小可以处理大规模的数据同时可以避免搜索冗余的节点。然而深度优先搜索也有其局限性例如可能会陷入死循环或无法找到最优解因此需要根据具体问题选择合适的算法进行优化。 点赞收藏富婆包养✋✋
