下载文档原格式
深度优先算法和广度优先算法的时间复杂度深度优先算法和广度优先算法是在图论中常见的两种搜索算法，它们在解决各种问题时都有很重要的作用。
本文将以深入浅出的方式从时间复杂度的角度对这两种算法进行全面评估，并探讨它们在实际应用中的优劣势。
1. 深度优先算法的时间复杂度深度优先算法是一种用于遍历或搜索树或图的算法。
它从图中的某个顶点出发，沿着一条路径一直走到底，直到不能再前进为止，然后回溯到上一个节点，尝试走其他的路径，直到所有路径都被走过为止。
深度优先算法的时间复杂度与图的深度有关。
在最坏情况下，深度优先算法的时间复杂度为O(V+E)，其中V表示顶点的数量，E表示边的数量。
2. 广度优先算法的时间复杂度广度优先算法也是一种用于遍历或搜索树或图的算法。
与深度优先算法不同的是，广度优先算法是从图的某个顶点出发，首先访问这个顶点的所有邻接节点，然后再依次访问这些节点的邻接节点，依次类推。
广度优先算法的时间复杂度与图中边的数量有关。
在最坏情况下，广度优先算法的时间复杂度为O(V+E)。
3. 深度优先算法与广度优先算法的比较从时间复杂度的角度来看，深度优先算法和广度优先算法在最坏情况下都是O(V+E)，并没有明显的差异。
但从实际运行情况来看，深度优先算法和广度优先算法的性能差异是显而易见的。
在一般情况下，广度优先算法要比深度优先算法快，因为广度优先算法的搜索速度更快，且能够更快地找到最短路径。
4. 个人观点和理解在实际应用中，选择深度优先算法还是广度优先算法取决于具体的问题。
如果要找到两个节点之间的最短路径，那么广度优先算法是更好的选择；而如果要搜索整个图，那么深度优先算法可能是更好的选择。
要根据具体的问题来选择合适的算法。
5. 总结和回顾本文从时间复杂度的角度对深度优先算法和广度优先算法进行了全面评估，探讨了它们的优劣势和实际应用中的选择。
通过对两种算法的时间复杂度进行比较，可以更全面、深刻和灵活地理解深度优先算法和广度优先算法的特点和适用场景。
深度优先搜索和广度优先搜索一、深度优先搜索和广度优先搜索的深入讨论(一)深度优先搜索的特点是无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法(一)和深度优先算法(二)中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。
(2)深度优先搜索法有递归以及非递归两种设计方法。
一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。
当搜索深度较大时，当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。
(3)深度优先搜索方法有广义和狭义两种理解。
广义的理解是，只要最新产生的结点(即深度最大的结点)先进行扩展的方法，就称为深度优先搜索方法。
在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。
而狭义的理解是，仅仅只保留全部产生结点的算法。
本书取前一种广义的理解。
不保留全部结点的算法属于一般的回溯算法范畴。
保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。
(4)不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。
(5)从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解.如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。
二、广度优先搜索法的显著特点是：(1)在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。
为使算法便于实现，存放结点的数据库一般用队列的结构。
深度优先搜索和⼴度优先搜索 深度优先搜索和⼴度优先搜索都是图的遍历算法。
⼀、深度优先搜索（Depth First Search） 1、介绍 深度优先搜索（DFS），顾名思义，在进⾏遍历或者说搜索的时候，选择⼀个没有被搜过的结点（⼀般选择顶点），按照深度优先，⼀直往该结点的后续路径结点进⾏访问，直到该路径的最后⼀个结点，然后再从未被访问的邻结点进⾏深度优先搜索，重复以上过程，直⾄所有点都被访问，遍历结束。
⼀般步骤：（1）访问顶点v；（2）依次从v的未被访问的邻接点出发，对图进⾏深度优先遍历；直⾄图中和v有路径相通的顶点都被访问；（3）若此时图中尚有顶点未被访问，则从⼀个未被访问的顶点出发，重新进⾏深度优先遍历，直到图中所有顶点均被访问过为⽌。
可以看出，深度优先算法使⽤递归即可实现。
2、⽆向图的深度优先搜索 下⾯以⽆向图为例，进⾏深度优先搜索遍历： 遍历过程： 所以遍历结果是：A→C→B→D→F→G→E。
3、有向图的深度优先搜索 下⾯以有向图为例，进⾏深度优先遍历： 遍历过程： 所以遍历结果为：A→B→C→E→D→F→G。
⼆、⼴度优先搜索（Breadth First Search） 1、介绍 ⼴度优先搜索（BFS）是图的另⼀种遍历⽅式，与DFS相对，是以⼴度优先进⾏搜索。
简⾔之就是先访问图的顶点，然后⼴度优先访问其邻接点，然后再依次进⾏被访问点的邻接点，⼀层⼀层访问，直⾄访问完所有点，遍历结束。
2、⽆向图的⼴度优先搜索 下⾯是⽆向图的⼴度优先搜索过程： 所以遍历结果为：A→C→D→F→B→G→E。
3、有向图的⼴度优先搜索 下⾯是有向图的⼴度优先搜索过程： 所以遍历结果为：A→B→C→E→F→D→G。
三、两者实现⽅式对⽐ 深度优先搜索⽤栈（stack）来实现，整个过程可以想象成⼀个倒⽴的树形：把根节点压⼊栈中。
每次从栈中弹出⼀个元素，搜索所有在它下⼀级的元素，把这些元素压⼊栈中。
并把这个元素记为它下⼀级元素的前驱。
⼴度优先搜索（BFS）与深度优先搜索（DFS）的对⽐及优缺点 深搜，顾名思义，是深⼊其中、直取结果的⼀种搜索⽅法。
如果深搜是⼀个⼈，那么他的性格⼀定倔得像头⽜！他从⼀点出发去旅游，只朝着⼀个⽅向⾛，除⾮路断了，他绝不改变⽅向！除⾮四个⽅向全都不通或遇到终点，他绝不后退⼀步！因此，他的姐姐⼴搜总是嘲笑他，说他是个⼀根筋、不撞南墙不回头的家伙。
深搜很讨厌他姐姐的嘲笑，但⼜不想跟⾃⼰的亲姐姐闹⽭盾，于是他决定给姐姐讲述⾃⼰旅途中的经历，来改善姐姐对他的看法。
他成功了，⽽且只讲了⼀次。
从那以后他姐姐不仅再没有嘲笑过他，⽽且连看他的眼神都充满了赞赏。
他以为是⾃⼰路上的各种英勇征服了姐姐，但他不知道，其实另有原因…… 深搜是这样跟姐姐讲的：关于旅⾏呢，我并不把⽬的地的风光放在第⼀位，⽽是更注重于沿路的风景，所以我不会去追求最短路，⽽是把所有能通向终点的路都⾛⼀遍。
可是我并不知道往哪⾛能到达⽬的地，于是我只能每到⼀个地⽅，就向当地的⼈请教各个⽅向的道路情况。
为了避免重复向别⼈问同⼀个⽅向，我就给⾃⼰规定：先问北，如果有路，那就往北⾛，到达下⼀个地⽅的时候就在执⾏此规定，如果往北不通，我就再问西，其次是南、东，要是这四个⽅向都不通或者抵达了终点，那我回到上⼀个地⽅，继续探索其他没去过的⽅向。
我还要求⾃⼰要记住那些帮过他的⼈，但是那些给我帮倒忙的、让我⽩费⼒⽓的⼈，要忘记他们。
有了这些规定之后，我就可以⼤胆的往前⾛了，既不⽤担⼼到不了不⽬的地，也不⽤担⼼重复⾛以前的路。
哈哈哈……深搜优缺点优点1、能找出所有解决⽅案2、优先搜索⼀棵⼦树，然后是另⼀棵，所以和⼴搜对⽐，有着内存需要相对较少的优点缺点1、要多次遍历，搜索所有可能路径，标识做了之后还要取消。
2、在深度很⼤的情况下效率不⾼ ⼴搜，顾名思义，是多管齐下、⼴撒⽹的⼀种搜索⽅法 如果⼴搜是⼀个⼈，那么她⼀定很贪⼼，⽽且喜新厌旧！她从⼀点出发去旅游，先把与起点相邻的地⽅全部游览⼀遍，然后再把与她刚游览过的景点相邻的景点全都游览⼀边……⼀直这样，直⾄所有的景点都游览⼀遍。
广度优先和深度优先的例子广度优先搜索(BFS)和深度优先搜索(DFS)是图遍历中常用的两种算法。
它们在解决许多问题时都能提供有效的解决方案。
本文将分别介绍广度优先搜索和深度优先搜索，并给出各自的应用例子。
一、广度优先搜索(BFS)广度优先搜索是一种遍历或搜索图的算法，它从起始节点开始，逐层扩展，先访问起始节点的所有邻居节点，再依次访问其邻居节点的邻居节点，直到遍历完所有节点或找到目标节点。
例子1：迷宫问题假设有一个迷宫，迷宫中有多个房间，每个房间有四个相邻的房间：上、下、左、右。
现在我们需要找到从起始房间到目标房间的最短路径。
可以使用广度优先搜索算法来解决这个问题。
例子2：社交网络中的好友推荐在社交网络中，我们希望给用户推荐可能认识的新朋友。
可以使用广度优先搜索算法从用户的好友列表开始，逐层扩展，找到可能认识的新朋友。
例子3：网页爬虫网页爬虫是搜索引擎抓取网页的重要工具。
爬虫可以使用广度优先搜索算法从一个网页开始，逐层扩展，找到所有相关的网页并进行抓取。
例子4：图的最短路径在图中，我们希望找到两个节点之间的最短路径。
可以使用广度优先搜索算法从起始节点开始，逐层扩展，直到找到目标节点。
例子5：推荐系统在推荐系统中，我们希望给用户推荐可能感兴趣的物品。
可以使用广度优先搜索算法从用户喜欢的物品开始，逐层扩展，找到可能感兴趣的其他物品。
二、深度优先搜索(DFS)深度优先搜索是一种遍历或搜索图的算法，它从起始节点开始，沿着一条路径一直走到底，直到不能再继续下去为止，然后回溯到上一个节点，继续探索其他路径。
例子1：二叉树的遍历在二叉树中，深度优先搜索算法可以用来实现前序遍历、中序遍历和后序遍历。
通过深度优先搜索算法，我们可以按照不同的遍历顺序找到二叉树中所有节点。
例子2：回溯算法回溯算法是一种通过深度优先搜索的方式，在问题的解空间中搜索所有可能的解的算法。
回溯算法常用于解决组合问题、排列问题和子集问题。
例子3：拓扑排序拓扑排序是一种对有向无环图(DAG)进行排序的算法。
广度优先搜索和深度优先搜索有何区别在计算机科学和算法领域中，广度优先搜索（BreadthFirst Search，简称 BFS）和深度优先搜索（DepthFirst Search，简称 DFS）是两种常见且重要的图或树的遍历算法。
它们在解决各种问题时都有着广泛的应用，但在搜索策略和特点上存在着显著的差异。
让我们先来了解一下广度优先搜索。
想象一下你正在一个迷宫中，你从入口开始，先探索与入口相邻的所有房间，然后再依次探索这些相邻房间相邻的房间，以此类推。
这就是广度优先搜索的基本思路。
广度优先搜索是以逐层的方式进行的。
它首先访问起始节点，然后依次访问起始节点的所有邻接节点，接着再访问这些邻接节点的邻接节点，就像在平静的湖面上泛起的层层涟漪。
这种搜索方式确保在访问更深层次的节点之前，先访问同一层次的所有节点。
在实现广度优先搜索时，通常会使用一个队列（Queue）数据结构。
将起始节点入队，然后循环取出队列头部的节点，并将其未访问过的邻接节点入队，直到队列为空。
这种方式保证了搜索的顺序是按照层次进行的。
广度优先搜索的一个重要应用是在寻找最短路径问题上。
因为它先访问距离起始节点近的节点，所以如果存在最短路径，它往往能够更快地找到。
例如，在地图导航中，要找到从一个地点到另一个地点的最短路线，广度优先搜索就可能是一个不错的选择。
接下来，我们看看深度优先搜索。
如果说广度优先搜索是逐层展开，那么深度优先搜索就像是一个勇敢的探险家，沿着一条路径一直走下去，直到走到尽头或者无法继续，然后才回溯并尝试其他路径。
深度优先搜索通过递归或者使用栈（Stack）来实现。
从起始节点开始，不断深入访问未访问过的邻接节点，直到无法继续，然后回溯到上一个未完全探索的节点，继续探索其他分支。
深度优先搜索在探索复杂的树形结构或者处理递归问题时非常有用。
比如在检查一个表达式是否合法、遍历一个复杂的文件目录结构等方面，深度优先搜索能够发挥其优势。
深度优先和⼴度优先⽐较区别：1）⼆叉树的深度优先遍历的⾮递归的通⽤做法是采⽤栈，⼴度优先遍历的⾮递归的通⽤做法是采⽤队列。
2）深度优先遍历：对每⼀个可能的分⽀路径深⼊到不能再深⼊为⽌，⽽且每个结点只能访问⼀次。
要特别注意的是，⼆叉树的深度优先遍历⽐较特殊，可以细分为先序遍历、中序遍历、后序遍历。
具体说明如下：先序遍历：对任⼀⼦树，先访问根，然后遍历其左⼦树，最后遍历其右⼦树。
中序遍历：对任⼀⼦树，先遍历其左⼦树，然后访问根，最后遍历其右⼦树。
后序遍历：对任⼀⼦树，先遍历其左⼦树，然后遍历其右⼦树，最后访问根。
⼴度优先遍历：⼜叫层次遍历，从上往下对每⼀层依次访问，在每⼀层中，从左往右（也可以从右往左）访问结点，访问完⼀层就进⼊下⼀层，直到没有结点可以访问为⽌。
3）深度优先搜素算法：不全部保留结点，占⽤空间少；有回溯操作(即有⼊栈、出栈操作)，运⾏速度慢。
⼴度优先搜索算法：保留全部结点，占⽤空间⼤；⽆回溯操作(即⽆⼊栈、出栈操作)，运⾏速度快。
通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，⼀般在数据库中存储的结点数就是深度值，因此它占⽤空间较少。
所以，当搜索树的结点较多，⽤其它⽅法易产⽣内存溢出时，深度优先搜索不失为⼀种有效的求解⽅法。
⼴度优先搜索算法，⼀般需存储产⽣的所有结点，占⽤的存储空间要⽐深度优先搜索⼤得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。
但⼴度优先搜索法⼀般⽆回溯操作，即⼊栈和出栈的操作，所以运⾏速度⽐深度优先搜索要快些深度优先：前序遍历：35,20,15,16,29,28,30,40,50,45,55中序遍历：15,16,20,28,29,30,35,40,45,50,55后序遍历：16,15,28,30,29,20,45,55,50,40,35⼴度优先遍历：35 20 40 15 29 50 16 28 30 45 55代码：package www.hhy;import java.beans.beancontext.BeanContextChild;import java.util.*;class Binarytree {class TreeNode{int value;TreeNode left;TreeNode right;public TreeNode(int value) {this.value = value;}}//⽤递归创建⼆叉树public int i = 0;TreeNode creatTesttree(String s){TreeNode root = null;if (s.charAt(i)!='#') {root = new TreeNode(s.charAt(i));i++;root.left = creatTesttree(s);root.right = creatTesttree(s);}else{i++;}return root;}//⼆叉树的前序遍历递归void binaryTreePrevOrder(TreeNode root){if(root==null){return;}System.out.println(root.value+" ");binaryTreePrevOrder(root.left);binaryTreePrevOrder(root.right);}//⼆叉树的中序遍历递归void binaryTreeInOrder(TreeNode root){if(root==null){return;}binaryTreeInOrder(root.left);System.out.println(root.value+" ");binaryTreeInOrder(root.right);}//⼆叉树的后续遍历递归void binaryTreePostOrder(TreeNode root){if(root==null){return;}binaryTreePostOrder(root.left);binaryTreePostOrder(root.right);System.out.println(root.value+" ");}//层序遍历void binaryTreeLevelOrder(TreeNode root,int level){if(root ==null||level<1){return;}if(level==1){System.out.print(root.value+" ");}binaryTreeLevelOrder(root.left,level-1);binaryTreeLevelOrder(root.right,level-1);}void BTreeLevelOrder(TreeNode root){if (root == null)return;int dep = getHeight(root);for (int i = 1; i <= dep; i++){binaryTreeLevelOrder(root,i);}}//⼆叉树的层序遍历⾮递归void binaryTreeLevelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();if(root != null) {queue.offer(root);//LinkedList offer add}while (!queue.isEmpty()) {//1、拿到队头的元素把队头元素的左右⼦树⼊队 TreeNode cur = queue.poll();System.out.print(cur.value+" ");//2、不为空的时候才能⼊队if(cur.left != null) {queue.offer(cur.left);}if(cur.right != null) {queue.offer(cur.right);}}}//⼆叉树的前序遍历⾮递归void binaryTreePrevOrderNonR(TreeNode root){Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);System.out.print(cur.value + " ");cur = cur.left;}top = stack.pop();cur = top.right;}System.out.println();}//⼆叉树的中序遍历⾮递归void binaryTreeInOrderNonR(TreeNode root){Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);cur = cur.left;}top = stack.pop();System.out.print(top.value+" ");cur = top.right;}System.out.println();}//⼆叉树的后序遍历⾮递归void binaryTreePostOrderNonR(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.peek();//L D//cur.right == prev 代表的是 cur的右边已经打印过了if(cur.right == null || cur.right == prev) {stack.pop();System.out.println(cur.value);prev = cur;cur = null;}else {cur = cur.right;}}}//⼆叉树的节点个数递归int getSize(TreeNode root){if(root==null){return 0;}return getSize(root.left)+getSize(root.right)+1;}//⼆叉树的叶⼦节点的个数递归int getLeafSize(TreeNode root){if(root==null){return 0;}if(root.left==null && root.right==null){return 1;}return getLeafSize(root.left)+getLeafSize(root.right); }//⼆叉树得到第K层结点的个数int getKlevelSize(TreeNode root ,int k){if(root==null){return 0;}if(k == 1){return 1;}return getKlevelSize(root.left,k-1)+getKlevelSize(root.right,k-1);}//⼆叉树查找并返回该结点递归// 查找，依次在⼆叉树的根、左⼦树、// 右⼦树中查找 value，如果找到，返回结点，否则返回 nullTreeNode find(TreeNode root, int value){if(root == null) {return null;}if(root.value == value){return root;}TreeNode ret = find(root.left,value);if(ret != null) {return ret;}ret = find(root.right,value);if(ret != null) {return ret;}return null;}//⼆叉树的⾼度int getHeight(TreeNode root){if(root==null){return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight>rightHeight ? leftHeight+1:rightHeight+1;}//判断⼀个树是不是完全⼆叉树public int binaryTreeComplete(TreeNode root) {Queue<TreeNode> queue = new LinkedList<TreeNode>();if(root != null) {queue.add(root);//offer}while(!queue.isEmpty()) {TreeNode cur = queue.peek();queue.poll();if(cur != null) {queue.add(cur.left);queue.add(cur.right);}else {break;}}while(!queue.isEmpty()) {TreeNode cur = queue.peek();if (cur != null){//说明不是满⼆叉树return -1;}else{queue.poll();}}return 0;//代表是完全⼆叉树}//检查两棵树是否是相同的，如果两棵树结构相同，并且在结点上的值相同，那么这两棵树是相同返回true public boolean isSameTree(TreeNode p,TreeNode q){if((p==null&&q!=null)||(p!=null&&q==null)){}if(p==null && q==null){return true;}if(p.value!=q.value){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.left);}//检查是否为⼦树public boolean isSubTree(TreeNode s,TreeNode t){if(s==null||t==null){return false;}if(isSameTree(s,t)){return true;}else if (isSubTree(s.left,t)){return true;}else if(isSubTree(s.right,t)){return true;}else{return false;}}//1.判断是否为平衡⼆叉树，左右⼦树的⾼度之差不超过 "1"(⼤根本⾝是平衡⼆叉树，左右⼦树也必须是平衡⼆叉树) // 时间复杂度为n^2//2.求复杂度为O(n)的解法public boolean isBanlanced(TreeNode root){if(root==null){return true;}else{int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return Math.abs(leftHeight-rightHeight)<2&&isBanlanced(root.left)&&isBanlanced(root.right);}}//判断是否为对称⼆叉树public boolean isSymmetric(TreeNode root){if(root==null){return true;}return isSymmetric(root.left,root.right);}public boolean isSymmetric(TreeNode lefttree,TreeNode righttree){if((lefttree==null && righttree!=null)||(lefttree!=null && righttree ==null)){return false;}if(lefttree == null && righttree == null){return true;}return lefttree.value == righttree.value && isSymmetric(lefttree.left,righttree.right)&& isSymmetric(lefttree.right,righttree.left);}//⼆叉树创建字符串⾮递归写法public String tree2str(TreeNode t){StringBuilder sb = new StringBuilder();tree2strchild(t,sb);return sb.toString();}public void tree2strchild(TreeNode t ,StringBuilder sb){if (t==null){}sb.append(t.value);if (t.left!=null){sb.append("(");tree2strchild(t.left,sb);sb.append(")");}else {if (t.right==null){}}}//⼆叉树字符串递归写法public String CreateStr(TreeNode t){if(t==null){return "";}if(t.left==null&&t.right==null){return t.value+"";}if(t.left==null){return t.value+"()"+"("+CreateStr(t.right)+")";}if(t.right==null){return t.value+"("+CreateStr(t.left)+")";}return t.value+"("+CreateStr(t.left)+")"+"("+CreateStr(t.right)+")";}public int rob(TreeNode root) {if (root == null) return 0;return Math.max(robOK(root), robNG(root));}private int robOK(TreeNode root) {if (root == null) return 0;return root.value + robNG(root.left) + robNG(root.right);}private int robNG(TreeNode root) {if (root == null) return 0;return rob(root.left) + rob(root.right);}//⼆叉树的公共祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null){return null;}if(root==p||root==q){return root;}TreeNode leftTree = lowestCommonAncestor(root.left,p,q);//p||q nullTreeNode rightTree = lowestCommonAncestor(root.right,p,q);//p||q null//3if(leftTree!=null && rightTree!=null){return root;}//左边找到else if (leftTree!=null ){return leftTree;}//右边找到else if(rightTree!=null){return rightTree;}//都没找到的情况下return null;}//⼆叉搜索树，若他的左⼦树不为空，左⼦树上的所有节点都⼩于根节点，//如果他的右⼦树不为空，右⼦树上的所有节点都⼤于根节点//最终他的中序排列都是有序结果//输⼊⼀棵⼆叉搜索树，将该⼆叉搜索树转换成⼀个排序的双向链表。
全国青少年信息学奥林匹克联赛搜索基础算法一、深度搜索（DFS）从一个简单题目开始。
例1．输出n个元素的无重复的全排列。
（1<=n<=9）在这里我们可以对每一个元素编号，形成1,2,…,8,9个数字的全排列。
我们用一个一维数组来处理，相当于有9个位置，每个位置可以放1到9，再进行重复性判断，即在每个位置放一个数字时判断它前面是否已经使用该数字。
通过数组中元素值的变化，产生全排列。
下面给出非递归例程，其中，变量k是表示位置指针，数组x用来装每个位置的值。
const n=5;varx:array[1..10] of integer;k:integer; {位置指针}function try:boolean; {判重函数}var i:integer;beginfor i:=1 to k-1 doif x[i]=x[k] thenbegin try:=false;exit;end;try:=true;end;procedure out; {输出过程}var i:integer;beginfor i:=1 to n dowrite(x[i]);writeln;end;begink:=1;x[1]:=0;while k>0 dobegininc(x[k]); {当前第k个位置中增加1}if x[k]>n then {判断当前第k个位置中是否超界，超界指针后移一位} dec(k)elseif try then {判重}begininc(k);x[k]:=0; {前进1位}if k>n then {判断指针是否超界，决定一个排列是否完成,完成指针后移一位}begin out;dec(k);end;end;end;end.下面是递归例程：const n=5;varx:array[1..10] of integer;function try(v1,k:integer):boolean; {判重函数,v1表示位置，k表示所放的值}var i:integer;beginfor i:=1 to v1-1 doif x[i]=k thenbegin try:=false;exit;end;try:=true;end;procedure out; {输出过程}beginfor i:=1 to n dowrite(x[i]);writeln;end;procedure search(v:integer); {v表示第v个位置}var i:integer;beginif v>n then begin out;exit;end; {若v超界，一个排列完成}for i:=1 to n do {在第v个位置上分别放1到n}if try(v,i) then {如果不重复，处理第v+1个位置}begin x[v]:=i;search(v+1);end;end;beginsearch(1);end.说明：使用非递归的好处是节约内存，当一些题目对内存消耗较大时，建议使用非递归方式；但使用递归方式在程序运行时间上要好一些，因为在每个节点扩展时，递归方式少一个范围超界判断。
广度优先算法和深度优先算法
广度优先算法和深度优先算法是最常用的两种图遍历算法，它们都能
够遍历整个图的节点，但在具体应用场景中选择哪种算法需要根据实
际需求来判断。
广度优先算法（BFS）将当前节点的所有邻居节点都遍历一遍后再遍历下一层，可以确保找到最短路径。
具体实现方式是使用一个队列来存
储被访问过但还未被遍历过的节点，同一层的节点都在队列中，不同
层的节点通过队列的先进先出特性被访问。
BFS遍历图通常需要记录
每个节点是否被访问过，以防止重复遍历。
深度优先算法（DFS）是一种递归算法，从某一节点出发一直向下遍
历到底（即遍历到一个叶子节点），然后返回到上一层节点继续遍历，直到遍历完整个图。
DFS相较于BFS具有更好的空间复杂度，但不能
保证找到最短路径。
DFS遍历图时通常需要记录每个节点是否被访问过，并保证不重复访问。
广度优先算法和深度优先算法在选择上需要根据具体算法应用需求。
如果需要找到最短路径，则选择广度优先算法，如果需要搜索所有可
能路径，则选择深度优先算法。
例如，在迷宫的寻找最短路径场景中，BFS可以从迷宫入口出发，按照层级一层一层的向外扩展搜索，最终
一定能够找到终点，但会消耗较大的空间；而DFS则可以搜索所有可能的路径，但不能确保找到最短路径。
综上所述，广度优先算法和深度优先算法都各有优缺点，在选择上需要根据实际应用场景判断。
有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。
它们最终都会到达所有
连通的顶点。
深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。
深度优先搜索：
深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。
这种方法的搜索树是从树根开始一枝一枝逐渐形成的。
下面图中的数字显示了深度优先搜索顶点被访问的顺序。
"* ■ J 严-* 4
t C '4 --------------------------------- --- _
为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则：
(1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。
(2) 当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点。
(3) 如果不能执行规则1和规则2，就完成了整个搜索过程。
广度优先搜索：
在深度优先搜索算法中，是深度越大的结点越先得到扩展。
如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。
在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。
相反，在广度优先搜索中，
算法好像要尽可能地靠近起始点。
它首先访问起始顶点的所有邻接点，然后再访问较远的区
域。
它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。
实现广度优先搜索，也要遵守三个规则:
⑴ 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。
（2）如果因为已经没有未访问顶点而不能执行规则1
时，那么从队列头取一个顶点，并使其
成为当前顶点。
（3）如果因为队列为空而不能执行规则2,则搜索结束。
广度优先搜索
类剔：搜索算法
数据结构：图
时间复杂感0（ I叭+ |虔D二Q們空「可复杂度od ^|+|j|）= cx^）最佳解：是完全生是
BFS是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。
换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。
BFS并不使用经验法则算法。
从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的伫列中。
一般的实作里，其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中（例如伫列或是链表），而被检验过的节点则被放置在被称为closed的容器中。
（open-closed 表）
实作方法
1.首先将根节点放入伫列中。
2.从伫列中取出第一个节点，并检验它是否为目标。
o 如果找到目标，则结束搜寻并回传结果。
o 否则将它所有尚未检验过的直接子节点加入伫列中。
3. 若伫列为空，表示整张图都检查过了一一亦即图中没有欲搜寻的目标。
结束搜 寻并回传“找
不到目标”。
4. 重复步骤2。
C 的实作
广度优先搜索算法:
对图G=(V,E)进行广度优先搜索的主算法如下。
void TRAVEL_BFS(VLi nk G[], i nt visited[], i nt n)
{ int i;
for(i = 0; i < n; i ++)
{ visited[i] = 0;
/* 標記數組賦初值(清零) */
}
for(i = 0; i < n; i ++)
if(visited[i] == 0)
BFS(G,i);
} 深度优先搜索是图论中的经典算法， 利用深度优先搜索算法可以产生目标图的相应 拓扑 排序表，利用拓扑排序表可以方便的解决很多相关的 图论问题，如最大路径问题等等。
void BFS(VLi nk G[], i nt v)
{ int w;
VISIT(v);
/* visited[v] = 1;
/* ADDQ(Q,v);
while(!EMPTYQ(Q))
{ v = DELQ(Q);
/* w = FIRSTADJ(G,v); /* while(w != -1)
{ if(visited[w] == 0)
{ VISIT(w);
/* ADDQ(Q,w);
/* visited[w] = 1;
/* }
w = NEXTADJ(G,v); /*
}
}
}
訪問頂點v*/ 頂點v 對應的訪問標記置爲 1*/ 退出隊頭元素v*/ 求v 的第1個鄰接點。
無鄰接點則返回 -1*/ 訪問頂點v*/ 當前被訪問的頂點w 進隊*/ 頂點w 對應的訪問標記置爲 1*/ 求v 的下一個鄰接點。
若無鄰接點則返回 -1*/
8 3 6 12 5 11 概况 图 是 9)( |\ 10 : 深度优先铁素 定义一： O (g(n))={f(n) | 如果存在正常数 cl 、c2和正整数 n0,使得当 n>=n0时, 0<c1g(n)<=f(n)<=c2g(n)恒成立} 节点进行深度优先捜南的顺序 类别： 搜萦算法 定义二: c 和正整数 n0 ,使得当 n>=n0时, c 和正整数 n0 ,使得当 n>=n0时, 數据结构: Q ㈣ __________________________ O 伽) 否 完全性: 其他: 耐ISL 良鹽厦:-_ 空间复杂厦: 最佳解: 0<=f(n)<=cg( n) 恒成立} 定义三： Q (g(n))={f(n) |如果存在正常数 0<=cg(n)<=f(n) 恒成立} O (g(n))={f(n) |如果存在正常数。
