[图] 遍历 | BFS

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;}}}}
};