当前位置：首页 > news >正文

深度优先算法（DFS）和广度优先算法（BFS）

news 来源：原创 2025/7/5 0:02:47

一、深度优先算法

深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用栈stack数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

若将dfs策略应用于树结构，其效果等同与前中后序遍历，采用递归和队列来辅助实现。
若将dfs策略应用于图结构，则通过栈来辅助实现。

树（前中后序遍历）

树的前中后序遍历就是深度优先算法的体现，其思想就是从某一个根节点开始，向下遍历（使用递归的方式），

比如前序遍历，从根节点开始—》左子树—》右子树。先遍历完左子树，直到所有左子树遍历完毕后，再遍历右子树。

前序遍历代码实现：

 //前序遍历 从根节点开始——》左子树——》右子树public Queue<Key> preErgodic(){Queue<Key> keys=new Queue<>();preErgodic(root,keys);return keys;}//递归遍历 将遍历到的都添加在队列中private void preErgodic(TreeNode x,Queue<Key> key){if (x==null){return;}key.inQueue(x.key);if (x.left!=null){//如果左子节点不为空 则递归遍历左子节点preErgodic(x.left,key);}if (x.right!=null){preErgodic(x.right,key);}}

流程思想体现：

图
在图中，一般是通过散列表（数组+队列）的形式来表示（二维数组也可以），所以图的深度搜索会稍微比树要复杂一些。需要通过一个布尔数组，栈来辅助实现。
图的存储结构
数组的索引表示的就是图的顶点，而索引的值存储的是一个队列Queue，队列中存储的元素表示的是与该顶点相连的顶点。

图的深度优先搜索关键代码：

 //索引代表顶点，值表示当前顶点是否已经被搜索private boolean[] marked;//记录有多少个顶点与s顶点想通private int count;//构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相邻顶点public DepthFirstSearch(Graph G,int s){//创建一个和图顶点数量一样大小的布尔数组marked=new boolean[G.getV()];//搜索图中的与顶点s相同的所有顶点dfs(G,s);}//深度优先搜索找出图G中v的顶点的所有相邻顶点private void dfs(Graph G,int v){//把当前顶点标记为已搜索marked[v]=true;//遍历v顶点的邻接表，得到每一个顶点wSystem.out.println("搜索节点："+v);for (Integer w : G.adj(v)) {//如果当前顶点的w没有被搜索过,则递归搜索与w顶点相通的其他顶点if (!marked[w]){dfs(G,w);}}//想通的顶点数量+1count++;}

其中marked为一个布尔数组，其索引表示顶点，值表示当前顶点是否被搜索过。数组的大小和存储图的大小完全一致。那么当访问到一个顶点时，就可以从队列中获取到该顶点中的相连的元素，然后通过for循环与迭代的形式，来实现深度搜索。

二、广度优先算法

又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。

树（层序遍历）

广度优先搜索（也称宽度优先搜索，缩写BFS即即Breadth First Search）是连通图的一种遍历算法。这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。其属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。

比如树的层序遍历

树的层序遍历就需要使用一个队列来进行辅助，来存储待遍历节点。

代码实现：

  /*** 层序遍历* 将每一层的节点依次加入队列中*/public Queue<Key> layerErgodic(){Queue<Key> keys=new Queue<>();   //存储遍历结果队列Queue<TreeNode> nodes=new Queue<>();//循环节点队列nodes.inQueue(root); //将根节点添加至循环队列中while (!nodes.isEmpty()){ //如果不为空 则代表还需要判断是否有 子节点判断TreeNode treeNode = nodes.outQueue();keys.inQueue(treeNode.key); //先将该节点加入 结果队列中if (treeNode.left!=null){nodes.inQueue(treeNode.left);}if (treeNode.right!=null){nodes.inQueue(treeNode.right);}}return keys;}

其中会创建两个队列，一个keys队列用来存储遍历的结果，nodes队列存储的就是需要循环遍历的队列。
从根节点开始进行判断，查看当前节点是有有左右子节点，如若有就将其左右子节点放入到队列当众，由于队列是先进先出的特性，所以就可以实现一层一层的去遍历的效果

图
图的广度优先算法同样是需要一个队列来辅助，和树的层序遍历思路一致。
核心代码：

//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//记录有多少个顶点与s顶点相遇
private int count;
//用来存储待搜索邻接表的点
private Queue<Integer> waitSearch;//构造广度优先搜索对象,使用广度优先搜索找出图G中S顶点的所有相邻顶点
public BreadthFirstSearch(Graph g,int s){//创建一个和图顶点个数一样大小的布尔数组marked=new boolean[g.getV()];//初始化待抖索顶点的队列waitSearch=new Queue<>();//搜索G图中与顶点s相同的所有顶点dfs(g,s);
}//使用广度优先搜索找出G图中V顶点的所有相邻顶点
private void dfs(Graph g,int v){for (Integer w : g.adj(v)) {//取得当前顶点的所有子节点if (!marked[w]){//如果还没被搜索marked[w]=true; //标记为已经搜索waitSearch.inQueue(w);System.out.println("搜索子节点："+w);}}while (!waitSearch.isEmpty()){dfs(g,waitSearch.outQueue());}count++; //想通的顶点加一}

waitSearch：用来存储邻接表中的点，也就是每一个顶点相连的元素。

如上图所示，从根节点开始，那么首先就会将根节点所有相邻的顶点放入waitSearch中，只要waitSearch队列中不为空，就继续迭代遍历，来实现广度搜索。

一、深度优先算法

树（前中后序遍历）

二、广度优先算法

树（层序遍历）

相关文章：