图：深度优先遍历搜索（DFS）（Java实现）

基本思想

对于连通图：从初始访问顶点开始，先访问第一个邻接顶点，再以这个邻接顶点为新的初始顶点，访问它的第一个邻接顶点对于非连通图：对图的连通分量分别进行深度优先遍历这种方式是优先纵向深入这是一个递归的过程

算法实现

邻接矩阵的实现

boolean[] isVisited ; //记录顶点是否已被访问过 void dfs(Graph<?> G) { //开始时所有顶点均未访问 isVisited = new boolean[G.getNumOfVertexes()]; for(int i = 0;i < isVisited.length; i++) isVisited[i] = false; //遍历所有顶点，进行DFS for(int i = 0; i < G.getNumOfVertexes(); i++) if( !isVisited[i]) dfs(G, i); } //DFS递归算法部分 void dfs(Graph<?> G, int i) { //访问该顶点 System.out.println(G.getValueByIndex(i).toString()); //标记为已访问 isVisited[i] = true; //访问下个邻接顶点 int j = 0; for(j = 0; j < G.getNumOfVertexes(); j++) if(G.edges[i][j] != Graph.INFINITY && G.edges[i][j] != 0 && !isVisited[j]) //有边且未被访问 dfs(G, j); }

算法分析

邻接矩阵结构：邻接矩阵是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，所以算法时间复杂度为O(n²)