数据结构与算法系列 - 深度优先和广度优先

发布时间：2025-11-05 10:26:26 来源：码上建站 作者：数据库

前言

数据结构与算法系列(完成部分)：

PS：大部分已经完成在公众号或者GitHub上，后面陆续会在头条补充链接(不允许有外部链接)

本篇讨论深度优先搜索和广度优先搜索相关内容。企商汇度优

关于搜索&遍历

对于搜索来说，数据算法深度我们绝大多数情况下处理的结构都是叫 “所谓的暴力搜索” ，或者是系列先说比较简单朴素的搜索，也就是说你在搜索的时候没有任何所谓的智能的情况在里面考虑，很多情况下它做的一件事情就是把所有的结点全部遍历一次，然后找到你要的结果。

基于这样的一个数据结构，如果这个数据结构本身是没有任何特点的，也就是说是一个很普通的树或者很普通的图。那么我们要做的一件事情就是遍历所有的结点。香港云服务器同时保证每个点访问一次且仅访问一次，最后找到结果。

那么我们先把搜索整个先化简情况，我们就收缩到在树的这种情况下来进行搜索。

如果我们要找到我们需要的一个值，在这个树里面我们要怎么做？那么毫无疑问就是从根这边开始先搜左子树，然后再往下一个一个一个一个点走过去，然后走完来之后再走右子树，直到找到我们的点，这就是我们所采用的方式。

再回到我们数据结构定义，它只有左子树和右子树。

我们要实现这样一个遍历或者搜索的话，毫无疑问我们要保证的事情就是

仅访问一次的意思就是代表我们在搜索中，我们不想做过多无用的访问，不然的话我们的访问的效率会非常的慢。云服务器提供商

当然的话还可以有其余的搜索，其余的搜索的话就不再是深度优先或者广度优先了，而是按照优先级优先 。当然你也可以随意定义，比如说从中间优先类似于其他的东西，但只不过的话你定义的话要有现实中的场景。所以你可以认为是一般来说就是深度优先、广度优先，另外的话就是优先级优先。按照优先级优先搜索的话，其实更加适用于现实中的很多业务场景，而这样的算法我们一般把它称为启发式搜索，更多应用在深度学习领域。而这种比如说优先级优先的话，在很多时候现在已经应用在各种推荐算法和高级的搜索算法，让你搜出你中间最感兴趣的内容，以及每天打开抖音、快手的话就给你推荐你最感兴趣的内容，其实就是这个原因。

深度优先搜索(DFS)

递归写法

递归的写法，一开始就是递归的终止条件，然后处理当前的层，然后再下转。

1.二叉树模版

Java 版本

Python 版本

C/C++ 版本

JavaScript版本

2.多叉树模版

非递归写法

Python版本

C/C++版本

遍历顺序

我们看深度优先搜索或者深度优先遍历的话，它的整个遍历顺序毫无疑问根节点 1 永远最先开始的，接下来往那个分支走其实都一样的，我们简单起见就是从最左边开始走，那么它深度优先的话就会走到底。

参考多叉树模版我们可以在脑子里面或者画一个图把它递归起来的话，把递归的状态树画出来，就是这么一个结构。

图的遍历顺序

广度优先搜索（BFS）

广度优先遍历它就不再是用递归也不再是用栈了，而是用所谓的队列。你可以把它想象成一个水滴，滴到1这个位置，然后它的水波纹一层一层一层扩散出去就行了。

两者对比

BFS代码模板

//Java public class TreeNode {     int val;     TreeNode left;     TreeNode right;     TreeNode(int x) {         val = x;     } } public List> levelOrder(TreeNode root) {     List> allResults = new ArrayList<>();     if (root == null) {         return allResults;     }     Queue nodes = new LinkedList<>();     nodes.add(root);     while (!nodes.isEmpty()) {         int size = nodes.size();         List results = new ArrayList<>();         for (int i = 0; i < size; i++) {             TreeNode node = nodes.poll();             results.add(node.val);             if (node.left != null) {                 nodes.add(node.left);             }             if (node.right != null) {                 nodes.add(node.right);             }         }         allResults.add(results);     }     return allResults; } 

# Python def BFS(graph, start, end):     visited = set()     queue = []      queue.append([start])      while queue:          node = queue.pop()          visited.add(node)         process(node)          nodes = generate_related_nodes(node)          queue.push(nodes)     # other processing work      ... 

// C/C++ void bfs(Node* root) {   map visited;   if(!root) return ;   queue queueNode;   queueNode.push(root);   while (!queueNode.empty()) {     Node* node = queueNode.top();     queueNode.pop();     if (visited.count(node->val)) continue;     visited[node->val] = 1;     for (int i = 0; i < node->children.size(); ++i) {         queueNode.push(node->children[i]);     }   }   return ; } 

相关文章