企业官网建设流程全解析

怎么用企业网站做营销,网站推广线上推广,安阳网站建设优化渠道,主流电商平台有哪些深度优先搜索#xff08;DFS#xff09;详解及C实现 一、什么是深度优先搜索#xff08;DFS#xff09;#xff1f; 深度优先搜索#xff08;Depth-First Search#xff0c;简称DFS#xff09;是一种用于遍历或搜索树或图的算法。其核心思想是#xff1a;尽可能深地搜…深度优先搜索DFS详解及C实现一、什么是深度优先搜索DFS深度优先搜索Depth-First Search简称DFS是一种用于遍历或搜索树或图的算法。其核心思想是尽可能深地搜索图的分支当某条分支搜索到尽头无法继续前进时回溯到上一个节点再选择另一条未探索的分支继续搜索直到所有节点都被访问完毕。可以用一个生动的比喻理解DFS想象你走进一个迷宫每次遇到岔路时随机选择一条路一直走直到走到死胡同无法继续前进然后沿原路返回上一个岔路选择另一条未走过的路继续探索直到找到出口或遍历完整个迷宫。DFS的实现通常依赖栈Stack这种数据结构手动实现时或者直接利用递归函数调用栈更简洁也是最常用的方式。递归实现的本质是将每次的节点访问和回溯过程交给函数栈来管理无需手动维护栈结构。二、DFS的核心特性与适用场景1. 核心特性不撞南墙不回头优先深入探索当前分支而非横向遍历同级节点回溯思想探索到尽头后返回上一节点继续探索其他分支需要记录节点访问状态避免重复访问空间复杂度取决于递归深度或栈的大小最坏情况下为O(n)n为节点数时间复杂度遍历图时时间复杂度为O(VE)V为顶点数E为边数遍历树时为O(n)树中边数为n-1。2. 适用场景图的遍历连通分量查找、拓扑排序等树的遍历前序、中序、后序遍历路径搜索等迷宫问题最短路径不适用DFS不保证最短需用BFS但可用于判断是否存在路径排列组合问题如全排列、子集生成等回溯法解决的经典问题如N皇后、数独求解等。三、DFS的两种实现方式CDFS的实现分为递归实现和非递归实现手动栈。递归实现代码简洁易于理解非递归实现则更灵活可避免递归深度过大导致的栈溢出问题。下面以「无向图的遍历」和「树的前序遍历」为例讲解两种实现方式。1. 递归实现最常用递归实现的核心逻辑访问当前节点标记为已访问遍历当前节点的所有邻接节点对每个未访问的邻接节点递归调用DFS函数。案例1无向图的DFS遍历假设我们有如下无向图0 → 1 → 20 → 3 → 4用邻接表存储图邻接表是图的常用存储方式适合稀疏图然后通过递归DFS遍历所有节点。#includeiostream#includevectorusingnamespacestd;// 邻接表存储图vectorvectorintadj;// 标记节点是否被访问vectorboolvisited;// 递归实现DFSvoiddfs(intu){// 标记当前节点为已访问visited[u]true;// 访问当前节点此处为打印节点值coutu ;// 遍历当前节点的所有邻接节点for(intv:adj[u]){// 如果邻接节点未被访问递归调用DFSif(!visited[v]){dfs(v);}}}intmain(){// 图的节点数intn5;// 初始化邻接表和访问标记数组adj.resize(n);visited.resize(n,false);// 构建无向图adj[0].push_back(1);adj[1].push_back(0);adj[1].push_back(2);adj[2].push_back(1);adj[0].push_back(3);adj[3].push_back(0);adj[3].push_back(4);adj[4].push_back(3);coutDFS遍历结果递归;// 从节点0开始遍历若图不连通需遍历所有未访问节点dfs(0);coutendl;return0;}输出结果DFS遍历结果递归0 1 2 3 4说明从节点0出发先深入探索1→2分支回溯后再探索3→4分支最终遍历所有节点。案例2二叉树的前序遍历DFS二叉树的前序遍历根→左→右是DFS的典型应用递归实现非常简洁。#includeiostreamusingnamespacestd;// 二叉树节点定义structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};// 递归实现前序遍历DFSvoidpreorderDFS(TreeNode*root){// 递归终止条件节点为空if(rootnullptr){return;}// 访问根节点coutroot-val ;// 递归遍历左子树preorderDFS(root-left);// 递归遍历右子树preorderDFS(root-right);}intmain(){// 构建一棵二叉树// 1// \ // 2// /// 3TreeNode*rootnewTreeNode(1);root-rightnewTreeNode(2);root-right-leftnewTreeNode(3);cout二叉树前序遍历DFS;preorderDFS(root);coutendl;// 释放内存简化处理实际应手动遍历释放deleteroot-right-left;deleteroot-right;deleteroot;return0;}输出结果二叉树前序遍历DFS1 2 32. 非递归实现手动栈当递归深度过大时如遍历深度为1e4的树会导致栈溢出C默认递归栈大小有限此时需要用手动栈实现DFS。核心逻辑与递归一致只是将递归调用栈替换为手动维护的栈。非递归实现步骤将起始节点压入栈标记为已访问弹出栈顶节点访问该节点将该节点的所有未访问邻接节点压入栈注意为保证遍历顺序与递归一致需逆序压入因为栈是先进后出重复步骤2-3直到栈为空。案例1无向图的DFS遍历非递归#includeiostream#includevector#includestackusingnamespacestd;vectorvectorintadj;vectorboolvisited;// 非递归实现DFS手动栈voiddfsNonRecursive(intstart){stackintst;// 压入起始节点标记为已访问st.push(start);visited[start]true;while(!st.empty()){// 弹出栈顶节点intust.top();st.pop();// 访问当前节点coutu ;// 遍历邻接节点逆序压入保证遍历顺序与递归一致for(autoitadj[u].rbegin();it!adj[u].rend();it){intv*it;if(!visited[v]){visited[v]true;st.push(v);}}}}intmain(){intn5;adj.resize(n);visited.resize(n,false);// 构建无向图同递归案例adj[0].push_back(1);adj[1].push_back(0);adj[1].push_back(2);adj[2].push_back(1);adj[0].push_back(3);adj[3].push_back(0);adj[3].push_back(4);adj[4].push_back(3);coutDFS遍历结果非递归;dfsNonRecursive(0);coutendl;return0;}输出结果DFS遍历结果非递归0 1 2 3 4说明这里对邻接节点逆序遍历rbegin()和rend()是因为栈是“先进后出”的。如果直接正序压入遍历顺序会变成0→3→4→1→2虽然也是DFS但与递归实现的顺序不一致不影响遍历完整性仅影响顺序。案例2二叉树的前序遍历非递归DFS#includeiostream#includestackusingnamespacestd;structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};// 非递归实现前序遍历DFSvoidpreorderDFSNonRecursive(TreeNode*root){if(rootnullptr){return;}stackTreeNode*st;// 压入根节点st.push(root);while(!st.empty()){// 弹出栈顶节点访问TreeNode*nodest.top();st.pop();coutnode-val ;// 注意先压右子树再压左子树栈先进后出保证左子树先访问if(node-right!nullptr){st.push(node-right);}if(node-left!nullptr){st.push(node-left);}}}intmain(){// 构建与递归案例相同的二叉树TreeNode*rootnewTreeNode(1);root-rightnewTreeNode(2);root-right-leftnewTreeNode(3);cout二叉树前序遍历非递归DFS;preorderDFSNonRecursive(root);coutendl;// 释放内存deleteroot-right-left;deleteroot-right;deleteroot;return0;}输出结果二叉树前序遍历非递归DFS1 2 3四、DFS的经典应用回溯法求解N皇后问题DFS的核心是“探索-回溯”而回溯法是DFS的一种延伸应用常用于解决“选择-验证-回溯-再选择”的组合优化问题。N皇后问题是回溯法的经典案例在n×n的棋盘上放置n个皇后使得任意两个皇后不处于同一行、同一列或同一斜线上。#includeiostream#includevector#includestringusingnamespacestd;vectorvectorstringresult;// 存储所有合法解// 检查当前位置(row, col)是否可以放置皇后boolisValid(intn,introw,intcol,vectorstringboard){// 检查同一列是否有皇后for(inti0;irow;i){if(board[i][col]Q){returnfalse;}}// 检查左上到右下的斜线左上方向for(intirow-1,jcol-1;i0j0;--i,--j){if(board[i][j]Q){returnfalse;}}// 检查右上到左下的斜线右上方向for(intirow-1,jcol1;i0jn;--i,j){if(board[i][j]Q){returnfalse;}}returntrue;}// DFS回溯函数当前处理第row行voidbacktrack(intn,introw,vectorstringboard){// 递归终止条件所有行都处理完毕找到一个合法解if(rown){result.push_back(board);return;}// 遍历当前行的每一列尝试放置皇后for(intcol0;coln;col){if(isValid(n,row,col,board)){// 选择在当前位置放置皇后board[row][col]Q;// 探索处理下一行backtrack(n,row1,board);// 回溯撤销选择恢复原状board[row][col].;}}}// 求解N皇后问题vectorvectorstringsolveNQueens(intn){result.clear();// 初始化棋盘n行n列全部为.vectorstringboard(n,string(n,.));backtrack(n,0,board);returnresult;}// 打印所有解voidprintResult(constvectorvectorstringresult){for(autosolution:result){coutendl;for(autorow:solution){coutrowendl;}}}intmain(){intn4;// 求解4皇后问题vectorvectorstringsolutionssolveNQueens(n);coutn皇后问题共有 solutions.size() 个解endl;printResult(solutions);return0;}输出结果4皇后问题的2个解4皇后问题共有 2 个解.Q……QQ……Q.…Q.Q……Q.Q…说明该代码通过DFS回溯逐行尝试放置皇后每放置一个皇后就验证合法性若合法则继续探索下一行若不合法则回溯到上一行重新选择列。最终遍历出所有合法的放置方案。五、DFS的常见注意事项避免重复访问必须使用visited数组或其他标记方式标记已访问的节点否则会陷入无限循环尤其是图中有环的情况递归深度控制递归实现时若问题规模过大如n1e4会导致栈溢出此时需改用非递归实现回溯的撤销操作回溯法中每次选择后必须撤销选择如N皇后问题中恢复board[row][col]为’.否则会影响后续探索邻接表的构建图的DFS遍历中邻接表比邻接矩阵更高效空间复杂度O(VE) vs O(V²)适合稀疏图多连通分量处理若图不连通需遍历所有节点对每个未访问的节点调用DFS如for(int i0; in; i) if(!visited[i]) dfs(i);。六、总结DFS是一种基于“深度优先、回溯探索”的遍历算法核心依赖栈递归栈或手动栈实现。其代码简洁、思想直观广泛应用于图遍历、树遍历、排列组合、回溯优化等问题。在C实现中递归版本适合小规模问题代码易写非递归版本适合大规模问题避免栈溢出。学习DFS的关键是理解“探索-回溯”的思想以及如何通过标记和撤销操作控制遍历过程。