[图] 遍历 | BFS | DFS
目录
1. 基本概念
2. 图的广度优先遍历（BFS）
3. 图的深度优先遍历（DFS）
4. 非连通图的遍历
1. 基本概念
给定一个图G和其中任意一个顶点v0，从v0出发，沿着图中各边访问图中的所有顶点，且每个顶点仅被遍历一次。"遍历"即对顶点进行某种操作的意思。
在前面的 树 里面 形象的总结过：
- DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。
2. 图的广度优先遍历（BFS）
- 借助队列实现：广度优先遍历依赖于队列来实现逐层遍历。
- 遍历过程：
-
- 以某个顶点为起点，当这个顶点出队列后，将与之邻接的所有顶点入队列。
- 每次处理一层顶点，然后继续向外扩展。
- 避免死循环：使用
bool类型的数组标记已经访问过的顶点，防止重复入队列。
void BFS(const V& src)
{
size_t srci = GetVertexindex(src);
size_t n = _vertexs.size();
queue<int> q;
vector<bool> vis(n, false);
q.push(srci);
vis[srci] = true;
while (!q.empty())
{
size_t front = q.front();
q.pop();
cout << front << ":" << _vertexs[front] << endl;
for (size_t i = 0; i < n; ++i)
{
if (_matrix[front][i] != MAX_W && !vis[i])
{
q.push(i);
vis[i] = true;
}
}
}
}图解：
- 有树的基础就知道广度优先遍历必然要借助 队列 来实现。
- 广度优先遍历就是以某个点为起点，当这个顶点出队列就把和这个顶点的 邻接顶点都入队列，然后一层一层往外走。
- 但是要注意的是 已经入过队列的顶点下一次不能在入队列，否则就会死循环，因此还要来一个标记bool类型数组。当一个顶点入队列后就标记一下。
问题：
错误 C2995 “size_t Graph＜V,W＞::GetVertexindex(const V &)”: 函数模板已经定义
测试：
应用实例：
- 例如找到六度好友的问题，可以利用BFS的一层一层遍历特性，通过计算队列内元素个数确保分层处理。
代码：
void RecommendFriends(const V& src, size_t max_degree = 6, size_t max_recommendations = 10) {
try {
size_t srci = GetVertexindex(src);
size_t n = _vertexs.size();
queue<pair<size_t, size_t>> q; // 存储顶点索引及其对应的度数
vector<bool> vis(n, false); // 访问标记数组
vector<V> recommended_friends; // 推荐好友列表
q.push(make_pair(srci, 0));
vis[srci] = true;
while (!q.empty() && recommended_friends.size() < max_recommendations) {
size_t k = q.size();
while (k--) {
pair<size_t, size_t> front_level = q.front();
q.pop();
size_t front = front_level.first;
size_t level = front_level.second;
// 不打印起点本身
if (level > 0 && level <= max_degree) {
cout << "Degree " << level << ": " << _vertexs[front] << endl;
recommended_friends.push_back(_vertexs[front]);
if (recommended_friends.size() >= max_recommendations) break;
}
for (size_t i = 0; i < n; ++i) {
if (_matrix[front][i] != MAX_W && !vis[i]) {
q.push(make_pair(i, level + 1));
vis[i] = true;
}
}
}
}回想一下刚才我们的BFS顶点出队列是怎么出的？是一个一个出的。
对于这道题我们 出队列的就要求一层一层出。那怎么一层一层出呢？很简单出队列之前计算一下当前队列内元素的个数。每次出队列内元素个数次。
3. 图的深度优先遍历（DFS）
上图中，红色箭头是递归，绿色箭头是回溯。
深度优先遍历，就是优先将邻接顶点的所有其它邻接顶点都遍历完，再遍历下一个邻接顶点，其实和树是一样的。
- 比如对于
F顶点，其有三个连通顶点，除去C比F先遍历，F首先遍历D连通的所有顶点，但是D连通的顶点都被遍历过了，所以没有继续深入。 - 当绿色箭头返回到
F，说明和D连通的所有顶点都被遍历完了，此时再去遍历H，H有一个连通的顶点I，所以先去遍历I，再回到F。 - 唯一不同的是，树有固定的根节点，每次都从根结点开始遍历，而图没有固定的根，用户传入任意一个顶点都可以开始遍历。
void _DFS(size_t srci, const size_t& n, vector<bool>& vis)
{
cout << srci << ":" << _vertexs[srci] << endl;
vis[srci] = true;
for (size_t i = 0; i < n; ++i)
{
if (_matrix[srci][i] != MAX_W && !vis[i])
{
_DFS(i, n, vis);
}
}
}
void DFS(const V& src)
{
size_t srci = GetVertexindex(src);
size_t n = _vertexs.size();
vector<bool> vis(n, false);
_DFS(srci, n, vis);
}DFS接口接收一个src，从该顶点开始遍历，将遍历结果按顺序放在数组ret中进行返回。
在递归本体_DFS中，每递归一个节点，将当前节点visited[srci] = true，表示已经遍历过，防止重复遍历。
!visited[i] && _matrix[srci][i] != MAX_W：只要下标i对应的顶点没有遍历过，并且和当前的srci是连通的，就进行递归遍历。
4. 非连通图的遍历
- 如果图不是完全连通的，那么从单一顶点开始的BFS或DFS可能无法访问到所有顶点。
其实很简单，不是有标记数组吗。
把标记数组在遍历一遍，如果还有顶点没有被遍历到那就以这个顶点在做一次BFS或DFS。
以 bfs 为例：
// 遍历非连通图中的所有连通分量
void TraverseAllComponents() {
size_t n = _vertexs.size();
vector<bool> visited(n, false);
for (size_t i = 0; i < n; ++i) {
if (!visited[i]) {
cout << "Starting new component from vertex: " << _vertexs[i] << endl;
BFSComponent(i, visited);
}
}
}
// 广度优先搜索遍历单个连通分量
void BFSComponent(size_t start, vector<bool>& visited) {
size_t n = _vertexs.size();
queue<size_t> q; // 存储顶点索引
q.push(start);
visited[start] = true;
while (!q.empty()) {
size_t front = q.front();
q.pop();
cout << "Visited: " << _vertexs[front] << endl;
for (size_t i = 0; i < n; ++i) {
if (_matrix[front][i] != MAX_W && !visited[i]) {
q.push(i);
visited[i] = true;
}
}
}
}
};