DFS



前文我们知道了如何创建无向图，分为邻接表和邻接矩阵两种方式，本文通过Java实现经典图的遍历算法-深度优先遍历算法(Depth First Search)

一. DFS介绍

深度优先遍历算法是一种算法，是一种遍历图的方法，在里面可以体会一下递归和回溯的思想。

讲一个寻找路径的小例子，方便理解比如“⾛迷宫”。 假设你站在迷宫的某个岔路⼝，然后想找到出⼝。你随意选择⼀个岔路⼝来⾛，⾛着⾛着发现⾛不通的时候，你就回退到上⼀ 个岔路⼝，重新选择⼀条路继续⾛，直到最终找到出⼝。这种⾛法就是⼀种深度优先搜索策略。

这⾥⾯实线箭头表示遍历，虚线箭头表示回退，从下图可以看到基本的行走路径。

二.代码说明

1. 基本定义

这里我们用邻接矩阵无向图的来做，在原有的基础上新增一个visited数组

public class Graph<T> {
    // 顶点
    private ArrayList<T> vertexs;
    // 边
    private int[][] edge;
    // 已访问
    private boolean[] visited;
}

• visited 用一个数组来记录顶点是否已被访问

2. Kahn算法实现

   public void dfs(int i) {
// 输出访问的节点
       System.out.print(vertexs.get(i).toString() + "=>");
       visited[i] = true;

       //获取i的第一个邻接点
       int w = firstNeighbor(i);
       while (w != -1) {
    // 判断是否访问过
           if (!visited[w]) {
	// 没有访问递归
               dfs(w);
           }
    // 找下个邻接点
           w = nextNeighbor(i, w);
       }

   }

   // 深度优先遍历算法
   public void dfs() {
// 这里对上面dfs(i)方法进行重载，dfs(i)是找一个点的所有邻接点，这里套一层意思就是找所有点的邻接点
       for (int i = 0; i < vertexs.size(); i++) {
           if (!visited[i]) {
               dfs(i);
           }
       }
   }

⼴度优先搜索的时间复杂度是O(V+E)，其中，V表示顶点的个数，E表示边的个数。当然，对于⼀个连通图来说，也就是说⼀个图中的所有顶点都是连通的，E肯定要⼤于等于V-1，所以，⼴度优先搜索的时间复杂度也可以简写为O(E)。

方便大家学习，提供了源代码