图深度优先遍历
编写程序对给定的 有向图（不一定连通） 进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。
输入格式:
输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。
输出格式:
输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。
输入样例1:
3 3
0 1
1 2
0 2
输出样例1:
0 1 2
输入样例2:
4 4
0 2
0 1
1 2
3 0
输出样例2:
0 1 2 3
深度优先遍历的主要思想：
首先以一个未被访问过的顶点作为起始顶点，延当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则返回上一个顶点，继续试探访问别的顶点，知道所有的顶点都被访问过。
显然，深度优先遍历时沿着图的某一条分支遍历直到末端，即“一条路走到黑”，然后再回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止
代码如下
importjava.util.Scanner; publicclassMain { staticScannerscan=newScanner(System.in); //sum记录访问过多少个顶点staticintsum=0; //n表示顶点的数量staticintn; //e表示边的数量staticinte; //输入顶点数和边数static { n=scan.nextInt(); e=scan.nextInt(); } //book用来标记顶点已经访问过staticint[] book=newint[n]; //a用来存储图的邻接矩阵存储法staticint[][] a=newint[n][n]; publicstaticvoidmain(String[] args) { //初始化二维矩阵，对角线为0，其他为无穷for (inti=0; i<n; i++) { for (intj=0; j<n; j++) { if (i==j) a[i][j] =0; elsea[i][j] =99; } } //输入顶点之间的有向边for (inti=0; i<e; i++) { intx=scan.nextInt(); inty=scan.nextInt(); a[x][y] =1; } //图有可能不连通，因此深度优先遍历每个结点for (inti=0; i<n; i++) { if (book[i] ==0) { book[i] =1; dfs(i); } } } //cur是当前所在的顶点编号publicstaticvoiddfs(intcur) { book[cur] =1; //每访问一个结点，sum就加1sum++; System.out.print(cur+" "); //所有的顶点已经访问过就直接退出if (sum==n) return; //从第一个顶点依次尝试，查看哪些顶点与当前顶点cur有边相连for (inti=0; i<n; i++) { //判断当前顶点cur到顶点i是否有边，并判断顶点i是否已经访问过if (a[cur][i] ==0&&book[i] ==0) { //标记顶点已经访问过book[i] =1; //从顶点i再出发继续遍历dfs(i); } } return; } }
