帮我用C++写一段dfs模板
时间: 2024-02-28 13:24:29 浏览: 168
以下是一个基本的DFS模板,可以用于解决许多问题:
```
#include <stdio.h>
#define MAXN 1000
int graph[MAXN][MAXN]; // 邻接矩阵存图
int visited[MAXN]; // 标记数组,记录每个节点是否被访问过
void dfs(int curNode, int n) { // curNode表示当前遍历的节点,n表示节点总数
visited[curNode] = 1; // 标记当前节点已被访问
for (int i = 0; i < n; ++i) {
if (graph[curNode][i] && !visited[i]) { // 如果当前节点与节点i有连通且节点i未被访问
dfs(i, n); // 递归访问节点i
}
}
}
int main() {
int n; // 节点总数
scanf("%d", &n);
// 读入图的邻接矩阵
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &graph[i][j]);
}
}
// 对每个未被访问的节点进行DFS
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(i, n);
}
}
return 0;
}
```
阅读全文