c++ 深度和广度优先搜索

深度优先搜索 (DFS)

DFS 是一种递归的遍历方法，它从根节点开始，沿着树的每一条路径深度遍历，直到到达叶子节点，之后回溯到上一个节点继续遍历。

主要特点：

深度优先搜索：从根节点开始，一直向下搜索直到叶子节点，然后回溯。
适合递归实现，栈可以用来模拟递归过程。
在树或图中，DFS的复杂度通常为 O(V + E)，其中V是节点数，E是边数。

#include <iostream>
#include <vector>using namespace std;// 定义二叉树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 递归实现深度优先遍历（前序遍历）
void dfs(TreeNode* root) {if (!root) {return;  // 递归结束条件}// 访问当前节点cout << root->val << " ";// 递归访问左子树dfs(root->left);// 递归访问右子树dfs(root->right);
}int main() {// 构建一个简单的二叉树TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);// 执行深度优先遍历（前序遍历）cout << "DFS Preorder Traversal: ";dfs(root);cout << endl;return 0;
}

图的连通分量

DFS可以用来在无向图中查找连通分量。一个连通分量是图中一个子集，其中每一对节点都通过边相互连接。DFS可以遍历每个连通分量，从一个未访问的节点开始遍历并标记所有可以访问的节点，直到整个连通分量都被遍历到。

示例：计算图中的连通分量

#include <iostream>
#include <vector>using namespace std;class Graph {
public:int V;  // 图的节点数vector<vector<int>> adj;  // 邻接表表示的图Graph(int V) {this->V = V;adj.resize(V);}void addEdge(int u, int v) {adj[u].push_back(v);adj[v].push_back(u);  // 无向图}void dfs(int v, vector<bool>& visited) {visited[v] = true;cout << v << " ";  // 访问当前节点// 遍历所有邻居for (int neighbor : adj[v]) {if (!visited[neighbor]) {dfs(neighbor, visited);}}}int countConnectedComponents() {vector<bool> visited(V, false);int count = 0;// 对每一个未访问过的节点执行DFSfor (int i = 0; i < V; ++i) {if (!visited[i]) {cout << "Connected component " << ++count << ": ";dfs(i, visited);cout << endl;}}return count;}
};int main() {Graph g(6);  // 创建一个有6个节点的图// 添加边g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(3, 4);g.addEdge(5, 5);  // 自环，表示一个单独的连通分量cout << "Number of connected components: " << g.countConnectedComponents() << endl;return 0;
}

广度优先搜索 (BFS)

BFS 是一种逐层遍历的算法，从根节点开始，先访问根节点的所有邻居节点，再依次访问其邻居的邻居，直到所有节点都被访问。

主要特点：

广度优先搜索：从根节点开始，逐层访问所有节点。
BFS 使用队列来存储当前层的节点，先进先出 (FIFO) 的队列实现了逐层遍历。
在树或图中，BFS的复杂度通常为 O(V + E)，其中V是节点数，E是边数。

#include <iostream>
#include <queue>
#include <vector>using namespace std;// 定义二叉树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 广度优先遍历（层序遍历）
vector<vector<int>> bfs(TreeNode* root) {vector<vector<int>> result;  // 存储每一层的节点if (!root) {return result;}queue<TreeNode*> q;  // 队列q.push(root);while (!q.empty()) {int levelSize = q.size();  // 当前层的节点数vector<int> currentLevel;  // 存储当前层的节点值for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();currentLevel.push_back(node->val);// 将左右子节点加入队列if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}result.push_back(currentLevel);  // 当前层遍历完毕}return result;
}int main() {// 构建一个简单的二叉树TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);// 执行广度优先遍历（层序遍历）vector<vector<int>> result = bfs(root);cout << "BFS Level Order Traversal: \n";for (const auto& level : result) {for (int val : level) {cout << val << " ";}cout << endl;}return 0;
}

最短路径问题

BFS非常适合解决无权图中的最短路径问题，即在图中寻找从起点到终点的最短路径。由于BFS是逐层扩展的，它可以保证第一次到达某个节点时就是从起点到该节点的最短路径。

示例：无权图中从源节点到目标节点的最短路径

#include <iostream>
#include <vector>
#include <queue>using namespace std;class Graph {
public:int V;  // 节点数量vector<vector<int>> adj;  // 邻接表表示的图Graph(int V) {this->V = V;adj.resize(V);}void addEdge(int u, int v) {adj[u].push_back(v);adj[v].push_back(u);  // 无向图}// 广度优先搜索，计算从source到其他节点的最短路径vector<int> bfsShortestPath(int source) {vector<int> dist(V, -1);  // dist[i]表示从source到节点i的距离queue<int> q;// 初始化dist[source] = 0;q.push(source);while (!q.empty()) {int node = q.front();q.pop();// 遍历所有邻居for (int neighbor : adj[node]) {if (dist[neighbor] == -1) {  // 如果该邻居未被访问dist[neighbor] = dist[node] + 1;q.push(neighbor);}}}return dist;}
};int main() {Graph g(6);// 添加边g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(2, 5);vector<int> dist = g.bfsShortestPath(0);  // 从节点0开始BFScout << "Shortest path distances from node 0: ";for (int i = 0; i < dist.size(); ++i) {cout << dist[i] << " ";}cout << endl;return 0;
}

拓扑排序

拓扑排序是有向无环图（DAG）中的一种排序方式，它将图中的所有节点排列成一个线性序列，且每条边 (u, v) 都满足 u 在 v 前面。拓扑排序有多个应用，例如任务调度、编译依赖等。

拓扑排序的应用通常使用 BFS（结合入度）来实现。

示例：拓扑排序（使用BFS）

#include <iostream>
#include <vector>
#include <queue>using namespace std;class Graph {
public:int V;  // 节点数vector<vector<int>> adj;  // 邻接表vector<int> inDegree;  // 每个节点的入度Graph(int V) {this->V = V;adj.resize(V);inDegree.resize(V, 0);}void addEdge(int u, int v) {adj[u].push_back(v);inDegree[v]++;  // 目标节点v的入度增加}vector<int> topologicalSort() {queue<int> q;vector<int> result;// 将所有入度为0的节点入队for (int i = 0; i < V; ++i) {if (inDegree[i] == 0) {q.push(i);}}while (!q.empty()) {int node = q.front();q.pop();result.push_back(node);// 遍历所有邻接节点，减少其入度for (int neighbor : adj[node]) {if (--inDegree[neighbor] == 0) {q.push(neighbor);}}}return result;}
};int main() {Graph g(6);// 添加有向边g.addEdge(5, 2);g.addEdge(5, 0);g.addEdge(4, 0);g.addEdge(4, 1);g.addEdge(2, 3);g.addEdge(3, 1);vector<int> result = g.topologicalSort();cout << "Topological Sort: ";for (int node : result) {cout << node << " ";}cout << endl;return 0;
}

总结

深度优先搜索 (DFS)：采用递归（或栈）策略，从根节点出发，一直深入到叶子节点。适合在树结构中需要访问每个节点的场景，如路径查找、图的遍历等。
- 典型实现：前序、中序、后序遍历。
广度优先搜索 (BFS)：采用队列策略，从根节点开始，逐层访问节点。适合查找最短路径等场景，尤其在图算法中广泛应用。
- 典型实现：层序遍历。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/19941.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！