DFS、BFS和Backtracking模板_Jaylon Wang的专栏 - CSDN博客

DFS和Backtracking的区别Backtracking是一种更通用的算法。

深度优先搜索是与搜索树结构相关的特定回溯形式。

来自维基百科：一个从根开始（在图形情况 ... DFS、BFS和Backtracking模板 kingmax54212008 2019-12-1618:05:18 377 收藏 版权声明：本文为博主原创文章，遵循CC4.0BY-SA版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/kingmax54212008/article/details/103567280 版权   DFS和Backtracking的区别 Backtracking是一种更通用的算法。

深度优先搜索是与搜索树结构相关的特定回溯形式。

来自维基百科： 一个从根开始（在图形情况下选择一个节点作为根）并在回溯之前尽可能地沿着每个分支进行探索。

它使用回溯作为其使用树的方法的一部分，但仅限于树结构。

但是，回溯可以用于任何类型的结构，其中可以消除域的部分-无论它是否是逻辑树。

Wiki示例使用棋盘和特定问题-您可以查看特定的移动，消除它，然后回溯到下一个可能的移动，消除它，等等。

  -DFSBacktrackingTargetStructureActualTree/GraphStructureAnytypeofstructurewhereportionsofthedomaincanbeeliminated(ChessBoard,matrix,implicittree)DefinitionAspecificformofbacktrackingrelatedtosearchingtree/graphstructuresTraversefromtheendandpruneunacceptablecasesStart-AtPointRootoftheTreeEndoftheGoalMovingDirectionFromtheroottoeachbranchFromtheendmovingbackwards     搜索问题的解法 DFS（深度优先搜索）BFS（广度优先搜索）backtracking（回溯） DFS模板 voiddfs(...) { //结束递归的条件 if(...){ .....//把“当前结果”加入“结果集容器”中 return; } //继续递归，里面可能有回溯，也可能没有 if(...){ ...//在容器中保存当前数据 dfs() ...//在容器中删除上面保存的数据（注：这种情况下就称为回溯，很明显它是dfs的一个步骤） } }   难点 寻找dfs结束条件继续dfs的条件 题目 78.Subsets93.RestoreIPAddresses DFS（回溯）题型： 1） Leetcode17.LetterCombinationsofaPhoneNumber Leetcode22.GenerateParentheses Leetcode39.CombinationSum Leetcode40.CombinationSumII Leetcode46.Permutations Leetcode47.PermutationsII Leetcode77.Combinations Leetcode78.Subsets 2）Leetcode37.SudokuSolver   BFS模板 模板1 voidbfs(...) { queueq; q.push(startRoot); while(!q.empty()){ //按照节点处理 curNode=q.front(); q.pop(); if(...){ //处理curNode,并把curNode的相邻Nodes加入队列 } } }   模板2 voidbfs(...) { queueq; q.push(startRoot); while(!q.empty()){ //按照层次处理 size=q.size(); for(i=0;ipostorderTraversal(TreeNode*root) 5{ 6vectoranswer; 7stack