dfs与bfs模板c++

深度优先搜索 (DFS) 和广度优先搜索 (BFS) 是常用的图遍历算法，它们通常用于寻找树形结构中的路径、查找最短路径或者连通分量等问题。 **DFS 模板(C++)**: ```cpp #include <iostream> using namespace std; // 图的邻接表表示 vector<vector<int>> adj; void dfs(int node, vector<bool>& visited) { // 标记当前节点已访问 visited[node] = true; cout << node << " "; // 遍历邻居节点 for (int neighbor : adj[node]) { if (!visited[neighbor]) { dfs(neighbor, visited); } } } // 主函数示例 int main() { int n, m; // n是顶点数，m是边数 cin >> n >> m; adj.resize(n + 1); // 初始化邻接表 // 填充边信息 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); // 如果是无向图，添加反向边 } vector<bool> visited(n + 1, false); // 初始化所有节点未访问 dfs(1, visited); // 从节点1开始搜索，1通常是起点 return 0; } ``` **BFS 模板(C++)**: ```cpp #include <iostream> #include <queue> using namespace std; void bfs(int start, vector<bool>& visited) { queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int current = q.front(); q.pop(); cout << current << " "; for (int neighbor : adj[current]) { // 邻居节点 if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } int main() { ... // 同样读取n, m, adj等信息 visited.resize(n + 1, false); bfs(1, visited); // 从节点1开始搜索 return 0; } ```

阅读全文