一、算法描述只需用一种递归方法遍历所有顶点。 如果要访问其中一个顶点：
标记为已访问； 递归访问所有未标记的邻居的顶点。 这种方法称为深度优先搜索(DFS )。 可以使用布尔数组中的每个顶点是否被访问。 递归方法标记指定的顶点，并调用自身来访问该顶点相邻顶点列表中的所有未标记顶点。 如果图是相连的，则会检查相邻链表的每个元素。
二、api为depthfirstsearchprivategraph图对象private int startVer开始顶点编号private boolean[] publicdepthfirstsearch(graph， int startVer )公共构造函数public void dfs ) )深度优先搜索privatebooleanismarked(intw ) )顶点w是privatevoidDFS ) )
三、算法的实现本算法只对邻接表所示的图结构进行深度优先搜索，其图的编码参考前文的有向图的制作(java的实现)，本算法依赖前文所作的图。
包图形； import java.util.*； /** *深度优先搜索* @ author hh */publicclassdepthfirstsearch {/* * *图对象*/private Graph graph； /**开始顶点编号*/private int startVer； */private boolean [ ]标记； /** *专用构造函数*/privatedepthfirstsearch ({ }/* * *公共构造函数* @ paramstartver */publicdepthfirstsearch ) ) marked=new boolean [ graph.get vertices () ]； Arrays.fill(Marked，Boolean.FALSE )； } /** *深度优先搜索*/public void dfs () ) for(intv=0； v graph.getVertices (； v () if (！ ismarked(v ) ) this.search ) v； }//****顶点w是否被访问过* @param w :顶点编号* @return； 是否访问了*/privatebooleanismarked(intw ) returnthis.marked； } /** *深度优先搜索算法的实现* @ paramv */privatevoidsearch (intv ) ) system.out.print ) v ' )； marked[v]=true； integerw : graph.adj (v ) ) if (！ ismarked(w ) ) { search(w ) w； } }测试代码如下。
publicclassgraphtest (publicstaticvoidmain (string [ ] args ) throws exception (string filename=' d : (desktop ) ) ) Graph graph=new Graph (； graph.creategraphbyfile (filename )； depthfirstsearchdepthfirstsearch=newdepthfirstsearch (graph，0 )； System.out.print ('深度优先搜索：')； depthFirstSearch.dfs
(); }}四、算法应用 计算连通分量：假设一个图有多个连通分量（多个子图），我们可以对图中的没有访问顶点进行dfs，如果该顶点没有被访问，那么连通分量计数加1，然后对该顶点进行dfs，这样该顶点所在子图的所有顶点已被访问，继续执行上面算法直至所有顶点已被访问。寻找路径：通过dfs我们可以使用一数组edgeTo记录起点s到任意顶点v的路径，其中edgeTo[w] = v表示访问w时上一次访问的是v顶点，这一巧妙设计 就可以计算出起点s到任意顶点v的路径。
完整实现代码如下：
package graph;import java.util.*;/** * 深度优先搜索 * @author hh */public class DepthFirstSearch { /** * 图对象 */ private Graph graph; /** * 开始顶点编号 */ private int startVer; /** * 标记哪些顶点被访问 */ private boolean[] marked; /** * dfs访问路径记录 */ private int[] edgeTo; /** * 记录每个顶点的连通分量标识 */ private int[] id; /** * 联通分量数量 */ private int cc; /** * 私有构造函数 */ private DepthFirstSearch() { } /** * 公有构造函数 * @param graph * @param startVer */ public DepthFirstSearch(Graph graph, int startVer) { this.graph = graph; this.startVer = startVer; marked = new boolean[graph.getVertices()]; edgeTo = new int[graph.getVertices()]; id = new int[graph.getVertices()]; cc = 0; Arrays.fill(marked,Boolean.FALSE); Arrays.fill(edgeTo,0); Arrays.fill(id,0); } /** * 深度优先搜索 */ public void dfs(){ for(int v = 0; v < graph.getVertices(); v++ ){ if(!isMarked(v)){ //连通分量加1 this.cc ++; this.search(v); } } } /** * 返回当前顶点的连通分量标识 * * @param v ：顶点编号 * @return ：当前顶点的连通分量标识 */ public int id(int v){ return id[v]; } /** * 顶点v和w连通 * * @param v :顶点v编号 * @param w ：顶点w编号 * @return ：true标识连通，false标识不连通 */ public boolean isConnect(int v,int w){ return id(v) == id(w); } /** * * @return : 连通分量数量 */ public int cc(){ return cc; } /** * 查找起点s到w路径集合 * * @param w : 顶点编号 * @return ：起点s到w路径集合 */ public Collection<Integer> pathTo(int w){ return GraphUtils.pathTo(this.edgeTo,this.startVer,w); } /** * 顶点w是否被访问过 * @param w ：顶点编号 * @return ；是否被访问 */ private boolean isMarked(int w){ return this.marked[w]; } /** * 深度优先搜索算法实现 * @param v */ private void search(int v){ System.out.print(v +" "); marked[v] = true; id[v] = cc; for(Integer w : graph.adj(v)){ if(!isMarked(w)){ //记录访问顶点w的前一次访问顶点路径 this.edgeTo[w] = v; search(w); } } }} package graph;import java.util.Collection;import java.util.LinkedList;/** * 图的工具类 * @author hh */public class GraphUtils { /** * 打印图中起点到终点路径 * * @param edgeTo ： 路径数组 * @param s : 起点编号 * @param w : 终点编号 * @return : 路径顶点列表 */ public static Collection<Integer> pathTo(int[] edgeTo, int s, int w){ LinkedList<Integer> path = new LinkedList<>(); path.addFirst(w); int v = edgeTo[w]; while (v != s){ path.addFirst(v); v = edgeTo[v]; } path.addFirst(s); return path; }}