所谓图的遍历，即是对结点的访问，一个图会有很多的结点，那么如何遍历这些结点，需要特定的策略，一般有两种访问策略深度遍历优先和广度遍历优先。今天一起来学习图的深度优先遍历算法。
图的深度优先搜索
（1）深度优先遍历，是从初始访问结点出发，而初始访问结点可能有多个邻接结点，深度优先遍历的策略是首先访问第一个邻接结点，然后再从这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次都在访问完当前结点后，首先访问当前结点的第一个邻接结点。
（2）这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
（3）显然，深度优先搜索是一个递归的过程。
深度优先遍历算法步骤
1）访问初始结点v，并标记结点v为已访问。
2）查找结点v的第一个邻接结点w。
3）若w存在，则继续执行第四步，若w不存在，则回到第一步，将从v的下一个结点继续。
4）若结点w未被访问，对w进行深度优先遍历递归（即把w当作另一个v，然后重新执行步骤）。
5）若结点w已经被访问，查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
伪代码如上图所示，接下来写几个关键的方法，首先是得到第一个邻接结点的下标,如果存在就返回对应的下标，否则返回-1，代码如下：
//得到第一个邻接结点的下标,如果存在就返回对应的下标，否则返回-1publicintgetFirstNeighbor(intindex){for(intj=0;jvertexList.size();j++){if(edges[index][j]0){returnj;}}return-1;}
接下来是根据前一个邻接结点的下标来获取下一个邻接结点，代码如下：
//根据前一个邻接结点的下标来获取下一个邻接结点publicintgetNextNeighbor(intv1,intv2){for(intj=v2+1;jvertexList.size();j++){if(edges[v1][j]0){returnj;}}return-1;
然后就是根据伪代码，写出深度优先遍历算法的代码：
//深度优先遍历算法publicvoiddfs(boolean[]isVisited,inti){//首先访问该结点输出System.out.print(getValueByIndex(i)+"-");//将这个结点设置为已经访问isVisited=true;//查找结点i的第一个邻接结点wintw=getFirstNeighbor(i);while(w!=-1){//说明有邻接结点if(isVisited[w]!=true){dfs(isVisited,w);}//如果w结点已经被访问w=getNextNeighbor(i,w);}}//对dfs进行一个重载，遍历所有结点并进行dfspublicvoiddfs(){for(inti=0;igetNumOfVertex();i++){if(isVisited!=true){dfs(isVisited,i);}}}
可以看到，我们对DFS算法最后中步骤三会有一个重载，重载是伪代码的步骤3中，若w不存在，则回到第一步将从v的下一个结点继续，所以每次都需要首先判断这个结点是否被访问，如果已经被访问过了就要从v的下一个结点继续，因此写了一个DFS重载。
全部代码如下：
/**Tochangethislicenseheader,chooseLicenseHeadersinProjectProperties.*Tochangethistemplatefile,chooseTools
Templates*andopenthetemplateintheeditor.*/packagegraph;importjava.util.ArrayList;importjava.util.Arrays;/****
authorAdministrator*/publicclassGraph{/***paramargsthe