一些有关于深度优先广度优先算法简介以及dfs算法的时间复杂度的相关话题，你对深度优先广度优先算法简介这样的题有了解多少呢？就让小编带各位了解一下吧！
1.什么是“搜索”算法？
算法基于特定的数据结构进行操作。深度优先和广度优先搜索算法都是基于“图”的数据结构。
由于图的数据结构非常具有表现力，因此大多数与搜索相关的场景都可以抽象为“图”。
对图中搜索算法最直接的理解就是寻找图中从一个顶点到另一个顶点的路径。
具体方法有很多，最简单、最“暴力”的两种方法就是深度优先搜索和广度优先搜索，以及A、IDA等启发式搜索算法。
图的存储方式主要有两种邻接表和邻接矩阵。
以无向图为例，使用邻接表存储。
publicclassGraph/edgeparamsvertexparamtaddvertex/publicvoidaddEdgeints,intt2.广度优先搜索
广度优先搜索，简称BFS。
也就是说，“地毯式”搜索策略首先搜索最接近起始顶点的顶点，然后搜索下一个最接近的顶点，依此类推，向外搜索。
21、实施流程
/图的广度优先搜索，搜索从s到t的路径。这样得到的路径就是从s到t的最短路径。paramsstartvertexparamtendvertex/publicvoidbfsints,intt//访记录访过的顶点，避免重复访该顶点。当访顶点q时，其访[q]被设置为true。boolean[]已访=newboolean[v];访过[s]=true；//队列用于存储已访过但关联顶点尚未访过的顶点。由于广度优先搜索是逐层访的，只有当第k层的所有顶点都被访完后，才能访第k+1层的顶点。//访第k层顶点时，必须记录第k层顶点，然后通过第k层顶点可以找到第k+1层顶点。//所以我们将使用这个队列来实现录音功能。队列lt;整数gt;队列=新LinkedListlt;gt;队列添加；//prev用于记录搜索路径。当从顶点s开始搜索到广度优先顶点t时，prev数组存储搜索路径。//但这些路径是以相反的顺序存储的。prev[w]存储顶点w所遍历的前一个顶点。//例如，如果通过顶点2的邻接表访顶点3，则prev[3]等于2。为了打印前向路径，我们需要递归地打印它，这就是打印功能的实现方式。int[]prev=Arraysstreamnewint[v]mapf-gt;-1到数组；while队列大小!=0Visit[q]=true;队列添加q；//重复打印s-gt;t的路径。privatevoidprintint[]prev,ints,inttSystemoutprintt+34;原理如下。
22.复杂性分析
在最坏的情况下，结束顶点t距离起始顶点s很远，找到它需要遍历整个图。
此时每个顶点都要进出队列一次，每条边都要访一次，所以广度优先搜索的时间复杂度为OV+E。
其中，V表示顶点数，E表示边数。
对于连通图，即图中所有顶点都是连通的，E必须大于等于V-1，因此广度优先搜索的时间复杂度也可以简写为OE。
广度优先搜索的空间消耗主要在几个辅助变量访数组、队列队列和传输数组上。
这三个存储空间的大小不超过顶点数，因此空间复杂度为OV。
3.深度优先搜索
深度优先搜索，简称DFS。
最直观的例子就是“假设你在迷宫的岔路口，想要找到出口，然后穿过迷宫”。
如果你随机选择一个岔路口而无法行走，则返回到前一个岔路口，选择一条新路径，继续行走，直到最终找到出口。此举是深度优先的搜索策略。
对图应用深度优先搜索以查找从一个顶点到另一个顶点的路径，如下所示。
搜索的起始顶点为s，结束顶点为t，在图中可以找到从顶点s到顶点t的路径。
使用深度递归算法显示整个搜索路径。实线箭头表示遍历，虚线箭头表示回滚。
从图中可以看到，深度优先搜索找到的路径并不是从顶点s到顶点t的最短路径。
31.实施过程
//全局变量或类成员变量，表示是否找到端点tbooleanfound=false;/深度优先搜索参数start顶点参数endvertex/publicvoiddfsints,inttprivatevoidrecurDfsintw,intt,boolean[]Visit,int[]上次访[w]=true;ifw==tLinkedListlt;Integergt;wLinked=adj[w];对于inti=0；我lt;w链接大小；++i32.复杂性分析
在深度搜索中，每条边最多被访两次，一次用于导航，一次用于回滚。
因此，深度优先搜索算法的时间复杂度为OE，E代表边的数量。
深度优先搜索算法消耗的内存主要是访、先前的数组和递归调用堆栈。
访过的数组和之前访过的数组的大小与顶点V的数量成正比。递归调用栈的最大深度不超过顶点数，因此整体空间复杂度为OV。
四、两者对比
广度优先搜索和深度优先搜索是图中最常用的两种基本搜索算法，与A、IDA等其他高级搜索算法相比，它们不需要任何优化，更加简单粗暴，因此它们也称为暴力搜索算法。
因此，这两种搜索算法只适合状态空间不大，即图不大的搜索。
广度优先搜索的通俗理解是，从起始顶点开始，按顺序向外逐层进行。
广度优先搜索必须借助队列来实现，遍历得到的路径是从起始顶点到结束顶点的最短路径。
深度优先搜索使用称为回溯的概念，它非常适合递归实现。也就是说，深度优先搜索是借助栈来实现的。
从执行效率来看，深度优先搜索和广度优先搜索的时间复杂度为OE，空间复杂度为OV。
No Comment