【数据结构】图的遍历

快乐的流畅：个人主页

个人专栏：《C游记》《进击的C++》《Linux迷航》

远方有一堆篝火，在为久候之人燃烧！

---

引言

前置知识：【数据结构】图的概念和存储结构

一、深度优先遍历

1.1 定义

深度优先遍历（Depth First Search，DFS），是一种从某个顶点开始，沿着一条路径不断深入到未访问的顶点，直到没有新的顶点可以访问为止。然后回溯到前一个顶点，再继续访问其他未被访问的顶点，直到所有顶点都被访问到。

1.2 实现

思路：

1. 创建vis数组，用于标记已遍历过的顶点，初始为false。
2. 由于DFS需要递归展开，所以分出一个子函数_DFS。
3. 进入子函数代表已到达src，所以将vis[srci]标记为true。
4. 随后for循环查找与当前点相连且没被遍历过的点，再次以新点作为当前点进入子函数，构成重复子问题。
5. _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 实现

思路：

1. 创建vis数组，用于标记已遍历过的顶点，初始为false。
2. 创建队列，用于存储待访问的顶点下标。
3. 初始化，将源点下标存入队列，vis中标记为true。
4. 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 是图中的边数。
  
  

真诚点赞，手有余香