简介

深度优先遍历（Depth-First Search，DFS）和广度优先遍历（Breadth-First Search，BFS）是图遍历算法中常用的两种方法。它们可以用于搜索和遍历图中的顶点，每种方法都有其独特的特点和应用场景。

深度优先遍历

深度优先遍历是一种递归的遍历算法，它从图的某个顶点开始，沿着一条路径尽可能深入地访问顶点，直到无法继续深入为止，然后回溯到上一个顶点，继续访问其他未被访问的顶点，直到所有顶点都被访问完毕。

思路解析：

1. 创建一个visited数组，用于记录顶点是否被访问。
2. 从graph中第一个未被访问顶点v0开始
3. 查找v0的第一个未被访问的邻接点，访问该顶点，并以该顶点为新顶点，依此循环，直到没有未被访问的邻接点。
4. 回到前一个访问过的仍有未被访问的邻接点，继续访问。
5. 重复步骤2，3，直至所有顶点均被访问。

递归实现

示例代码：

#include <iostream>
#include <vector>using namespace std;void dfs(vector<vector<int>> &graph, vector<bool> &visited, int vertex) {visited[vertex] = true;for (int i = 0; i < graph[vertex].size(); i++) {int neighbor = graph[vertex][i];if (!visited[neighbor]) {dfs(graph, visited, neighbor);}}
}void dfsTraversal(vector<vector<int>> &graph) {int numVertices = graph.size();vector<bool> visited(numVertices, false);for (int i = 0; i < numVertices; i++) {if (!visited[i]) {cout << "connected components:";dfs(graph, visited, i);cout << endl;}}
}int main() {vector<vector<int>> graph = {{1, 2},{0},{0},{4},{5},{4}};dfsTraversal(graph);return 0;
}

输出结果（求的连通分量）：

connected components:012
connected components:345

总结：使用递归的优点是它更容易实现。但是，也存在一些缺点，如果深度太深，会造成堆栈溢出。这种情况下我们会考虑使用 BFS，或使用显示栈实现 DFS。（其实我们上面使用的是系统提供的隐式栈，也成为调用栈 Call Stack）

显示栈实现

我们只需要修改上面 dfs 函数即可。

示例代码：

void dfs(vector<vector<int>> &graph, vector<bool> &visited, int vertex) {// 将根顶点压栈stack<int> s;s.push(vertex);while (!s.empty()) {// 取栈顶元素int vertex = s.top();s.pop();if (!visited[vertex]) {visited[vertex] = true;cout << vertex << " ";for (int i = 0; i < graph[vertex].size(); i++) {int neighbor = graph[vertex][i];if (!visited[neighbor]) {// 邻接点压栈s.push(neighbor);}}}}
}

总结：使用显示栈实现递归有以下几个优点

- 避免栈溢出：递归算法在处理大规模问题时可能会导致栈溢出的问题，因为每次递归调用都会占用一定的栈空间。使用显示栈可以更好地控制栈的使用，从而避免栈溢出的风险。- 提高性能：递归调用会引入函数调用和返回的开销，包括保存和恢复上下文、参数传递等。使用显示栈可以避免这些开销，因为所有的状态都显式地保存在栈中，而不是通过函数调用和返回来传递。这可以提高算法的性能。- 灵活控制递归过程：使用显示栈可以手动控制递归的深度和顺序。递归函数的执行顺序是由函数调用和返回决定的，而使用显示栈可以在需要时手动推入和弹出栈帧，从而灵活控制递归的深度和顺序。

广度优先遍历

广度优先遍历是一种迭代的遍历算法，它从图的某个顶点开始，先访问该顶点的所有邻居，然后再依次访问邻居的邻居，以此类推，直到遍历完所有可达的顶点。

思路解析：

1. 创建一个visited数组，用于记录已经访问过的顶点。
2. 创建一个队列，并将起始顶点放入队列中。
3. 将起始顶点标记为已访问。
4. 从队列中取出一个顶点，访问该顶点，并将其所有未访问过的邻居顶点放入队列中。
5. 标记刚刚访问过的顶点为已访问。
6. 重复步骤4、5，直到队列为空。

示例代码：

#include <iostream>
#include <vector>
#include <queue>using namespace std;void bfs(vector<vector<int>> &graph, vector<bool> &visited, int start) {visited[start] = true;queue<int> q;q.push(start);while (!q.empty()) {int vertex = q.front();q.pop();cout << vertex << " ";for (int i = 0; i < graph[vertex].size(); i++) {int neighbor = graph[vertex][i];if (!visited[neighbor]) {q.push(neighbor);visited[neighbor] = true;}}}
}void bfsTraversal(vector<vector<int>> &graph) {int numVertices = graph.size();vector<bool> visited(numVertices, false);for (int i = 0; i < numVertices; i++) {if (!visited[i]) {cout << "connected components:";bfs(graph, visited, i);cout << endl;}}
}int main() {vector<vector<int>> graph = {{1, 2},{0},{0},{4},{5},{4}};bfsTraversal(graph);return 0;
}

对比

深度优先遍历（DFS）和广度优先遍历（BFS）是两种常用的图遍历算法，它们在遍历顺序、实现方式和应用场景上有一些区别。

遍历顺序：

DFS：深度优先遍历从起始节点开始，沿着一条路径尽可能深入地遍历，直到无法继续深入为止，然后回溯到上一个节点，继续遍历其他路径。DFS会优先探索深度而不是广度。
BFS：广度优先遍历从起始节点开始，逐层地遍历图中的节点，先访问离起始节点最近的节点，然后逐渐扩展到离起始节点更远的节点。BFS会优先探索广度而不是深度。

实现方式：