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

【算法通关指南：数据结构与算法篇】树形结构遍历指南：DFS 递归深搜与 BFS 队列广搜实战解析 - 详解

news 2026/3/27 4:05:30

在这里插入图片描述

小龙报：个人主页
作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南》
✨ 永远相信美好的事情即将发生

在这里插入图片描述

文章目录

前言
一、深度优先遍历-DFS
- 1.1 vector数组
- 1.2 链式前向星
- 1.3 复杂度分析
- - 1.3.1 时间复杂度
  - 1.3.2 空间复杂度
二、宽度优先遍历-BFS
- 2.1 vector数组
- 2.2 链式前向星
- 2.3 复杂度分析
- - 2.3.1 时间复杂度
  - 2.3.2 空间复杂度
总结与每日励志

前言

树的遍历 ：就是不重不漏的将树中所有的点都扫描⼀遍
在之前学过的线性结构中，遍历就很容易，直接从前往后扫描⼀遍即可。但是在树形结构中，如果不按照⼀定的规则遍历，就会漏掉或者重复遍历⼀些结点。因此，在树形结构中，要按照⼀定规则去遍历。常用的遍历方式有两种，一种是深度优先遍历（DFS），另⼀种是宽度优先遍历（BFS）

我们将以一道例题讲解这些遍历方法：
在这里插入图片描述
树的逻辑图

一、深度优先遍历-DFS

深度优先遍历，英文缩写为DFS，全称是DepthFirstSearch，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走，也就是⼀条路走到黑。
具体流程：
（1）从根节点出发，依次遍历每⼀棵子树；
（2）遍历子树的时候，重复第一步。
因此，深度优先遍历是⼀种递归形式的遍历可以用递归来实现。
注：存储树结构的时候，会把相邻的所有结点都存下来，这样在扫描子树的时候会直接扫描到上一层，这不是我们想要的结果。
因此，需要一个数组来标记，哪些结点已经访问过，接下来的时候，就不去遍历那些点。

1.1 vector数组

#include <iostream>#include <vector>using namespace std;const int N = 1e5 + 10;vector<int> edges[N];   // edges[i] 保存着i号结点相连的所有点bool st[N];  // 标记当前结点是否已经被遍历过// 当前遍历到u这棵⼦树void dfs(int u){// 先访问该点cout << u << " ";st[u] = true;  //标记表明该节点已被访问//访问子树for (auto v : edges[u]){if (!st[v])dfs(v);  //如果没有遍历过再去递归}}int main(){int n;cin >> n;for (int i = 1; i < n; i++){int a, b;cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}dfs(1);return 0;}

运行结果：
在这里插入图片描述

1.2 链式前向星

#include <iostream>using namespace std;const int N = 1e5 + 10;int h[N],ne[N * 2], e[N * 2],id;bool st[N];void add(int a, int b){id++;e[id] = b;ne[id] = h[a];h[a] = id;}void dfs(int u){cout << u << " ";st[u] = true;for (int i = h[u]; i; i = ne[i]){int v = e[i];if (!st[v])dfs(v);}}int main(){int n;cin >> n;for (int i = 1; i < n; i++){int a, b;cin >> a >> b;add(a, b);add(b, a);}dfs(1);return 0;}

运行结果：
在这里插入图片描述

1.3 复杂度分析

1.3.1 时间复杂度

简单估计一下，在遍历的整个过程中，会把树中所有的边扫描量两遍。边的数量为n - 1 故时间复杂度为O(N）。

1.3.2 空间复杂度

最差情况下，结点个数为n的树，高度也是n ，也就是变成一个链表。此时递归的深度也是n,故一个时间复杂度O(N);

二、宽度优先遍历-BFS

宽度优先遍历，英文缩写为BFS，全称是BreadthFirstSearch，也叫广度优先遍历。也是⼀种用于遍历或搜索树或图的算法。
所谓宽度优先。就是每次都尝试访问同⼀层的节点。如果同⼀层都访问完了，再访问下⼀层。
算法过程可以看做是在树和图中，在起点放上一个细菌，每秒向周围的那些干净的位置扩散⼀层，直到把所有位置都感染
具体实现方式 ：借助队列
（1）初始化一个队列；
（2）根节点入队，同时标记该节点已经入队；
（3）当队列不为空时，拿出队头元素，访问，然后将队头元素的所有孩子入队，同时打上标记。
（4）重复过程，直到队列为空。

2.1 vector数组

#include <iostream>#include <vector>#include <queue>using namespace std;const int N = 1e5 + 10;vector<int> edges[N];queue < int> q;bool st[N];void bfs(int u){q.push(u);st[u] = true;while (q.size()){auto u = q.front();cout << u << " ";q.pop();for (auto v : edges[u]){if (!st[v]){q.push(v);st[v] = true;}}}}int main(){int n;cin >> n;for (int i = 1; i < n; i++){int a, b;cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}bfs(1);return 0;}

运行结果：
在这里插入图片描述

2.2 链式前向星

#include <iostream>#include <queue>using namespace std;const int N = 1e5 + 10;queue<int> q;int id, h[N], e[N * 2], ne[N * 2];bool st[N];  //st[i]表示那些节点已经入队void add(int a, int b){id++;e[id] = b;ne[id] = h[a];h[a] = id;}void bfs(int u){q.push(u);st[u] = true;while (q.size()){auto v = q.front();cout << v << " ";q.pop();// 让孩子入队for (int i = h[v]; i; i = ne[i]){int x = e[i];if (!st[x]){q.push(x);st[x] = true;}}}}int main(){int n;cin >> n;for (int i = 1; i < n; i++){int a, b;cin >> a >> b;add(a, b);add(b, a);}bfs(1);return 0;}