图的深度优先搜索：
1.将最初访问的顶点压入栈；
2.只要栈中仍有顶点，就循环进行下述操作:
（1）访问栈顶部的顶点u；
（2）从当前访问的顶点u 移动至顶点v 时，将v 压入栈。如果当前顶点u 不存在未访问的相邻矩阵，则将u 从栈中删除；
主要的几个变量：
| color[n] | 用WHITE、GRAY、BLACK 中的一个来表示顶点i 的访问状态 |
| M[n][n] | 邻接矩阵， 如果存在顶点i 到顶点j 的边，则M[i][j]为true |
| Stack S | 栈， 暂存访问过程中的顶点 |
其中color 数组中， 白色代表“未访问的顶点”， 灰色代表“访问过的顶点”（虽然被访问过了，但仍然可能留有通往未访问顶点的边）， 黑色代表”访问结束的顶点”；
有俩种方法实现深度优先遍历
（1）用递归实现的深度优先搜索
#include<stdio.h> #define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2 int n, M[N][N];
int color[N], d[N], f[N], tt;//color[n]表示该顶点访问与否，d[n]表示该顶点的发现时刻 ，f[n]表示该顶点的结束时刻 ,tt表示时间 //用递归函数实现的深度优先搜索
void dfs_visit(int u) {
int v;
color[u] = GRAY;
d[u] = ++tt;
for(v = ; v < n; v++) {
if(M[u][v] == ) continue;
if(color[v] == WHITE)
dfs_visit(v);
}
color[u] = BLACK;
f[u] = ++tt;//访问结束
} void dfs() {
int u;
//初始化
for(u = ; u < n; u++) color[u] = WHITE;
tt = ; //以未访问的u为起点进行深度优先搜索
for(u = ; u < n; u++) {
if(color[u] == WHITE)
dfs_visit(u);
} //输出
for(u = ; u < n; u++) {
printf("%d %d %d\n", u+, d[u], f[u]);
}
} int main() {
int u, v, k, i, j; scanf("%d", &n);
//初始化
for(i = ; i < n; i++) {
for(j = ; j < n; j++) {
M[i][j] = ;
}
}
//输入数据，构造邻接矩阵
for(i = ; i < n; i++) {
scanf("%d %d", &u, &k);
u--;
for(j = ; j < k; j++) {
scanf("%d", &v);
v--;
M[u][v] = ;
}
} dfs(); return ;
} /*
6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0
*/
（2）用栈实现的深度优先搜索
#include<iostream>
#include<stack>
using namespace std; static const int N = ;
static const int WHITE = ;
static const int GRAY = ;
static const int BLACK = ; int n, M[N][N];
int color[N], d[N], f[N], tt;//color[n]表示该顶点访问与否，d[n]表示该顶点的发现时刻 ，f[n]表示该顶点的结束时刻
int nt[N];//记录每个顶点的邻接顶点偏移量，eg：顶点0有俩个顶点1，2；现已经访问过1了，那么， nt[u] = 1; 下次直接访问2 //按编号顺序获取与u相邻的v
int next(int u) {
for(int v = nt[u]; v < n; v++) {
nt[u] = v + ;
if(M[u][v]) return v;
}
return -;
} void dfs_visit(int r) {
for(int i = ; i < n; i++) nt[i] = ; stack <int> S;
S.push(r);
color[r] = GRAY;
d[r] = ++tt; while( !S.empty() ) {
int u = S.top();
int v = next(u);
if(v != -) {
if(color[v] == WHITE) {
color[v] = GRAY;
d[v] = ++tt;
S.push(v);
}
}
else {
S.pop();
color[u] = BLACK;
f[u] = ++tt;
}
}
} void dfs() {
//初始化
for( int i = ; i < n; i++) {
color[i] = WHITE;
nt[i] = ;
}
//设置时间
tt = ; //以未访问的u为起点进行深度优先搜索，设置循环的目的应该是防止该图不是连通图
for(int u = ; u < n; u++) {
if(color[u] == WHITE) dfs_visit(u);
} for(int i = ; i < n; i++) {
cout << i+ << " " << d[i] << " " << f[i] << endl;
}
} int main() {
int u, k, v;
cin >> n; //顶点数 //邻接矩阵置零
for( int i = ; i < n; i++) {
for(int j = ; j < n; j++)
M[i][j] = ;
} //创建邻接矩阵
for(int i = ; i < n; i++) {
cin >> u >> k;//输入顶点和顶点的度
u--;
for(int j = ; j < k; j++) {
cin >> v;
v--;
M[u][v] = ;
}
} dfs(); return ;
} /*
6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0
*/