文章目录
- 引言
- 一、深度优先遍历
- 1.1 定义
- 1.2 实现
- 二、广度优先遍历
- 2.1 定义
- 2.2 实现
- 三、DFS与BFS的对比
引言
前置知识：【数据结构】图的概念和存储结构
一、深度优先遍历
1.1 定义
深度优先遍历（Depth First Search，DFS），是一种从某个顶点开始，沿着一条路径不断深入到未访问的顶点，直到没有新的顶点可以访问为止。然后回溯到前一个顶点，再继续访问其他未被访问的顶点，直到所有顶点都被访问到。
1.2 实现
思路：
- 创建vis数组，用于标记已遍历过的顶点，初始为false。
- 由于DFS需要递归展开，所以分出一个子函数_DFS。
- 进入子函数代表已到达src，所以将vis[srci]标记为true。
- 随后for循环查找与当前点相连且没被遍历过的点，再次以新点作为当前点进入子函数，构成重复子问题。
- _DFS调用完后，再检查vis数组是否还有未被遍历的点。若有，则再次以此点进行_DFS，防止不连通的区域未被遍历。
void _DFS(int srci, vector<bool>& vis)
{vis[srci] = true;cout << "[" << srci << "]" << ":" << _vertexs[srci] << endl;for (int i = 0; i < _vertexs.size(); ++i){if (_edges[srci][i] != W_MAX && !vis[i]){_DFS(i, vis);}}
}void DFS(const V& src)
{int n = _vertexs.size();vector<bool> vis(n, false);int srci = GetIndex(src);_DFS(srci, vis);//防止不连通的区域未被遍历for (int i = 0; i < n; ++i){if (!vis[i]){_DFS(i, vis);}}
}
细节：vis数组的作用，是为了保证遍历的过程中，不遍历相同的点，防止算法时间复杂度大大增加，导致冗余计算。利用vis数组不去遍历相同的点，这个过程又称为剪枝。
二、广度优先遍历
2.1 定义
广度优先遍历（Breadth First Search, BFS），是一种从某个顶点开始，先访问当前顶点的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点。BFS 是逐层遍历的过程，优先访问离起点较近的顶点。
2.2 实现
思路：
- 创建vis数组，用于标记已遍历过的顶点，初始为false。
- 创建队列，用于存储待访问的顶点下标。
- 初始化，将源点下标存入队列，vis中标记为true。
- while循环中，每次取出队头数据并弹出，随后for循环查找与当前点相连且没被遍历过的点，将其存入队列，并且vis中标记为true，构成重复子问题。
void BFS(const V& src)
{int n = _edges.size();vector<bool> vis(n, false);queue<int> q;int srci = GetIndex(src);q.push(srci);vis[srci] = true;int levelSize = 1;while (!q.empty()){//每层分行打印for (int i = 0; i < levelSize; ++i){int front = q.front();q.pop();cout << "[" << front << "]" << ":" << _vertexs[front] << " ";for (int j = 0; j < n; ++j){if (_edges[front][j] != W_MAX && !vis[j]){q.push(j);vis[j] = true;}}}cout << endl;levelSize = q.size();}
}
细节：levelSize的设置，是为了按源点的度从小到大分层打印。每次while循环里用for循环控制打印换行，随后更新levelSize。看似增加一套循环，实际并没有增加时间复杂度。
三、DFS与BFS的对比
以下是 深度优先遍历（DFS） 和 广度优先遍历（BFS） 的对比表格：
| 特性 | 深度优先遍历（DFS） | 广度优先遍历（BFS） |
|---|---|---|
| 使用的数据结构 | 栈（隐式或显式） | 队列 |
| 遍历顺序 | 深入某一条路径，直至没有未访问顶点再回溯 | 按层遍历，从起点逐层向外扩展 |
| 适用场景 | 连通分量、拓扑排序、路径搜索 | 最短路径、层次遍历、二分图判定 |
| 实现难度 | 简单（递归实现） | 需要队列，稍复杂 |
| 空间复杂度 | O(V)（递归栈） | O(V)（队列） |
| 时间复杂度 | O(V + E) | O(V + E) |
- V 是图中的顶点数，E 是图中的边数。
