[C++知识库]图的深度优先遍历C++代码模板

const int MAXV = 1000;//最大顶点数
const int INF = 1000000000;//设INF是一个很大的数
int n; //n为顶点数
bool vis[MAXV] = { false };//如果顶点i已被访问，则vis[i]=true.初值为false

邻接矩阵版

int G[MAXV][MAXV];//MAXV为最大顶点数

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

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

邻接表版

vector<int> Adj[MAXV];//图G的邻接表

void DFS(int u,int depth) {//u为当前访问的顶点标号，depth为深度
	vis[u] = true;//设置u已被访问
	//如果需要对u进行一些操作，可以在这里进行
	for (int i = 0; i < Adj[u].size(); i++) {//对从u出发能到达的所有顶点v
		int v = Adj[u][i];
		if (vis[v] == false) {//如果v未被访问
			DFS(v,depth+1);//访问v，深度加1
		}
	}
}

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