dfs和bfs c++

### C++ 中 DFS 和 BFS 的实现及其差异 在 C++ 编程中，深度优先搜索 (Depth First Search, DFS) 和广度优先搜索 (Broadth First Search, BFS) 是两种常见的图遍历算法。它们的主要区别在于访问节点的方式以及使用的数据结构。 #### 深度优先搜索 (DFS) DFS 使用栈来存储待访问的节点，在实际编程中通常通过递归来实现。它会尽可能深地探索某个分支直到无法继续为止，然后再回溯到上一层并重复此过程。 以下是基于邻接表表示法的一个简单 DFS 实现： ```cpp #include <iostream> #include <vector> using namespace std; void dfs(int node, vector<vector<int>> &adjList, vector<bool> &visited) { visited[node] = true; cout << "Visited Node: " << node << endl; // 访问当前节点 for(auto neighbor : adjList[node]) { // 遍历邻居节点 if(!visited[neighbor]) { // 如果未被访问，则递归调用 dfs(neighbor, adjList, visited); } } } int main() { int n = 5; // 假设有5个节点 vector<vector<int>> adjList(n); // 创建邻接表 adjList[0].push_back(1); adjList[0].push_back(2); adjList[1].push_back(3); adjList[2].push_back(4); vector<bool> visited(n, false); // 初始化所有节点为未访问状态 dfs(0, adjList, visited); // 开始从节点0进行DFS } ``` 上述代码展示了如何利用递归方法执行一次完整的 DFS 过程[^1]。 #### 广度优先搜索 (BFS) 相比之下，BFS 利用了队列这种先进先出的数据结构来进行层次化扩展。这意味着它总是先处理离起始点最近的所有顶点之后才会考虑更远距离上的其他可能路径。 下面是一个简单的 BFS 示例程序: ```cpp #include <iostream> #include <queue> #include <vector> 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<<"Visited:"<<currentNode<<endl; for(auto nextNode: adjList[currentNode]){ if(!visited[nextNode]){ visited[nextNode]=true; q.push(nextNode); } } } } int main(){ int nodesCount=6; vector<vector<int>> adjacencyLists(nodesCount,{}); /* 构建一些边 */ adjacencyLists[0]={1}; adjacencyLists[1]={2,3}; ... vector<bool> seenStatus(nodesCount,false); bfs(0,adjacencyLists,seenStatus); } ``` 这里我们定义了一个 `bfs` 函数用来完成整个流程，并且同样是从第一个索引位置出发作为起点[^2]。 #### 差异分析 | 特性 | DFS | BFS | |----------------|----------------------------------|---------------------------------| | 数据结构 | 栈（通常是隐式的函数调用堆栈） | 队列 | | 节点顺序 | 向下深入 | 层次展开 | | 时间复杂度 | O(V+E), V代表顶点数,E代表边的数量 | O(V+E) | 尽管两者的时间复杂度相同，但在某些特定场景下的表现可能会有所不同。例如当目标靠近根部时，BFS 可能更快找到解；而如果知道确切方向或者希望减少内存消耗则可以选择 DFS。