1、定义
连通图的深度优先搜索遍历
从图中某个顶点v0出发，访问此顶点，然后依次从v0的各个未被访问的邻接点出发深度优先搜索遍历图，直到图中所有和v0有路径想通的顶点都被访问到。
非连通图处理方法：
访问完一个连通分量后，再在图中选一个未曾被访问的顶点作为始点继续进行深度优先搜索遍历。
练习1：已知一个图，若从顶点v1出发，写出它的按深度优先搜索进行遍历的遍历序列。
优先深度搜索过程：
练习2：已知一个图，从顶点v0开始遍历，写出它的按深度优先搜索进行遍历的遍历序列。
优先深度搜索过程：
注：深度搜索到末端，进行退回，去另一个分支进行深度搜索
练习3：已知一个图的邻接表存储结构，如下图，若从顶点v1出发，分别写出有向图按深度优先搜索法进行遍历进行遍历得到的顶点序列。
2、性能分析
深度优先搜索遍历图的时间复杂度和广度优先遍历相同，不同之处仅在于对顶点的访问顺序不同。
图的存储结构采用邻接矩阵时，时间复杂度为O(n2)。
图的存储结构采用邻接表时，时间复杂度为O(e)。
3）算法实现
算法核心：递归
public class DTraverser { private static boolean[] visited;// 访问标志数组 // 对图G做深度优先遍历 public static void DFSTraverse(IGraph G) throws Exception { visited = new boolean[G.getVexNum()]; for (int v = 0; v < G.getVexNum(); v++) // 访问标志数组初始化 visited[v] = false; for (int v = 0; v < G.getVexNum(); v++) if (!visited[v])// 对尚未访问的顶点调用DFS DFS(G, v); } // 从第v个顶点出发递归地深度优先遍历图G public static void DFS(IGraph G, int v) throws Exception { visited[v] = true; System.out.print(G.getVex(v).toString() + " ");// 访问第v个顶点 //对顶点v的每一个未被访问的邻接点进行DFS操作 for (int w = G.firstAdjVex(v); w >= 0; w = G.nextAdjVex(v, w)) if (!visited[w])// 对v的尚未访问的邻接顶点w递归调用DFS DFS(G, w); } public static void main(String[] args) throws Exception { ALGraph G = GenerateGraph.generateALGraph(); DTraverser.DFSTraverse(G); } }
