dfs和bfs算法 C++

### C++ 实现 DFS 和 BFS 的方法 #### 深度优先搜索 (DFS) 深度优先搜索是一种通过递归方式遍历图或树结构的算法。其核心思想是从某个顶点出发，沿着一条路径尽可能深入地探索下去，直到无法继续为止，然后回溯并尝试其他可能的路径。 以下是基于邻接表表示的图结构实现的 DFS 算法： ```cpp #include <iostream> #include <vector> using namespace std; void dfs(int node, vector<vector<int>>& adjList, vector<bool>& visited) { cout << node << " "; // 访问当前节点 visited[node] = true; // 标记已访问 for (int neighbor : adjList[node]) { // 遍历相邻节点 if (!visited[neighbor]) { // 如果未访问过，则递归调用 dfs(neighbor, adjList, visited); } } } int main() { int n = 6; // 节点数量 vector<vector<int>> adjList(n); // 创建邻接表 adjList = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}}; // 初始化边关系 vector<bool> visited(n, false); // 初始化访问标记数组 cout << "Depth First Traversal (starting from vertex 0): "; dfs(0, adjList, visited); // 开始 DFS 遍历 } ``` 上述代码实现了从指定节点开始的深度优先遍历过程[^1]。 --- #### 广度优先搜索 (BFS) 广度优先搜索则采用队列来管理待访问的节点列表。它的特点是从起始节点开始逐步扩展至每一层的所有邻居节点后再进入下一层级。 下面是同样针对邻接表形式存储的图数据结构所编写的 BFS 方法： ```cpp #include <iostream> #include <vector> #include <queue> using namespace std; void bfs(int startNode, vector<vector<int>>& adjList, vector<bool>& visited) { queue<int> q; q.push(startNode); // 将初始节点加入队列 visited[startNode] = true; // 设置为已访问状态 while (!q.empty()) { // 当队列不为空时循环处理 int currentNode = q.front(); // 获取队首元素作为当前操作对象 q.pop(); cout << currentNode << " "; // 输出该节点 for (int neighbor : adjList[currentNode]) { // 查看所有关联节点 if (!visited[neighbor]) { // 若尚未被探测到就记录下来准备后续分析 visited[neighbor] = true; q.push(neighbor); } } } } int main() { int n = 6; // 定义总共有多少个顶点 vector<vector<int>> adjList(n); // 构建空的邻接链表容器 adjList = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}}; // 描述各条连接线路情况 vector<bool> visited(n, false); // 准备好布尔型标志位组，默认全设成false代表没走过任何地方 cout << "\nBreadth First Traversal (starting from vertex 0): "; bfs(0, adjList, visited); // 执行实际的功能逻辑部分 } ``` 此段程序展示了如何利用标准模板库(STL)中的`std::queue`类完成基本层次化的广度优先扫描功能[^2][^3]。 --- ### 总结说明 以上分别介绍了两种经典图形解析技术——DFS与BFS的具体实践方案及其对应的C++源码实例。两者各有优劣之处，在解决不同类型的实际应用场合中发挥着不可替代的作用。