遍历图DFS模板

邻接矩阵

const int MAXV = 1000;//最大顶点数
const int INF = 100000000;

int n, G[MAXV][MAXV];//G为邻接矩阵
bool vis[MAXV] = { false };//顶点vis[i]已访问的话为true

void DFS(int u, int depth) {//u为当前访问的顶点编号，depth为深度
	vis[u] = true;//设置已被访问
	//可以在此对u进行额外操作
	//下面对所有从u出发能达到的分支顶点进行枚举
	for (int v = 0; v < n; v++) {//对所有顶点
		if (vis[v] == false && G[u][v] != INF) {//顶点未访问而且u可到达
			DFS(v, depth + 1);//访问v，深度+1
		}
	}
}

void DFSTrave() {//遍历图
	for (int u = 0; u < n; u++) {//对每个顶点
		if (vis[u] == false) {//如果u未访问
			DFS(u, 1);//访问u和u所在的连通块,1表示初始为第一层
		}
	}
}

邻接表：

const int MAXN = 1000;
const int INF = 10000000;
vector<int> Adj[MAXN];//G的邻接表
int n;//定点数
bool vis[MAXN] = { false };

void DFS(int u, int depth) {
	vis[u] = true;
	for (int i = 0; i < Adj[u].size(); i++) {
		int v = Adj[u][i];
		if (vis[v] == false) {
			DFS(v, depth + 1);
		}
	}
}

//便利图
void DFSTrave() {
	for (int u = 0; u < n; u++) {
		if (vis[u] == false) {
			DFS(u, 1);
		}
	}
}