本文共 2558 字，大约阅读时间需要 8 分钟。

图的深度优先遍历

1. 定义：从图中某一点出发，访遍图中其余的顶点，且使每一个顶点仅仅被访问一次，这一个过程叫做图的遍历
2. 引入：不同于树的遍历，仅仅只有一个根节点，且是按照固定的方向，而图的遍历就复杂多了，因为顶点都与其他节点相通，路径比较复杂，一般方法是设置一个访问数组，未访问是0，访问是1。常用的遍历方法有：深度优先遍历和广度优先遍历两种方式。

深度优先遍历（Depth First Search）

基本介绍（DFS）

1. 深度优先遍历，从初始访问点出发，初始访问点可能有多个邻接结点，深度优先的遍历的策略是首先访问第一个邻接点，然后再以这个被访问的邻接结点作为初始访问结点，访问它的第一个邻接结点，即每一次访问完当前节点都会首先访问当前节点的第一个邻节点。类似迷宫回溯算法
2. 由此可见，当前的访问策略是优先往纵向挖掘深入，而不是对每一个节点的所有邻接点进行横向访问。

代码实现

具体案例

算法步骤

1. 访问初始节点V，并标记V已经访问
2. 查找结点V的第一个邻接点W
3. 若W存在，说明有关连接点
   • 若W已经被访问过，找下一个作为访问的对象
   • 若W并没有被访问过，那就直接访问第一个
4. 若W不存在，结束当前的方法
5. 查找下一个邻接点V，继续用上述的方法
   第一次循环是以第一个邻接点作为基准点，就已经访问玩所有的与第一个结点相关联的点，完整遍历是为了访问与第一个结点不关联的结点

代码实现

1. 写一个获取某节点第一个邻接节点的方法，在这里不考虑第一个节点是否已经被访问过。

//得到第一个邻接结点的下标    /**     * 结合矩阵来看，传入的始索引，如果有边相连，那就返回对应的索引     * @param index  传给我第一个索引的下标     * @return 如果存在就返回对应的下标，如果没有那就返回-1     */    public int getFirstNeighbour(int index){
           //遍历整个list的索引，然后操作对应的二维数组，如果有关联的边，那就返回对应的索引        for (int i = 0;i < Vertex.size();i ++){
               //传入的索引作为对应的行数，然后在对应的行里继续进行遍历，如果查找到大于0的数，返回对应的            //索引，那就是与当前索引对应的有关联边的结点的索引            if (edges[index][i] > 0){
                   return i;            }        }        return -1;        //遍历完之后还是没有找到，返回-1说明没有找到对应的结点的索引    }

2. 写一个获取当前节点的下一个邻接节点的，根据前一个邻接字节点的下标，来获取下一个邻接子节点，此时是以V1为基准进行参考的，V2是V1已经访问过的邻接结点

//根据前一个邻接点的下标来获取下一个邻接点    /**     * 总共是分为两个结点，第一个节点是当前以此为基准进行遍历的点，     * 另外一个就是基准之外的需要一个一个进行遍历的所有的邻接点     * @param V1 v1是当前节点，在代表边的二维数组上，表示当前的行     * @param V2 V2是当前结点的已经走过的邻接结点     * @return 返回的应该是下一个要走的邻接结点     */    public int getNextNeighbor(int V1,int V2){
           for(int j = V2 + 1;j < Vertex.size();j ++){
               if(edges[V1][j] > 0){
                   return j;            }        }        return -1;    }

3. 根据流程进行访问

//对dfs重载，遍历所有的结点，并进行dfs    public void dfs(){
           //遍历所有的结点，进行回宿        for(int i = 0;i < Vertex.size();i ++){
               if(!isVisited[i]){
                   dfs(isVisited,i);            }        }    }    //深度遍历的方法    //i第一次就是0    public void dfs(boolean[] isVisited,int i){
           //首先访问该节点，输出        System.out.print(getVertexByIndex(i) + ">>");        //将这个节点设置为已经访问过的结点        isVisited[i] = true;        //找到当前节点的第一个邻接结点        //有一疑问，那就是如果每一个结点都是从第一个节点开始访问的，但是在该方法里面        // 你有没有判定该节点是否已经访问的方法        int w = getFirstNeighbour(i);        //判断是否有对应的结点，有就继续访问，没有就退出访问        while (w != -1){
               //w不为-1说明存在相关联的结点，是不为空，然后再判断是否已经访问过了            if (!isVisited[w]){
                   //没有访问过，就进行深入访问,再以当前结点对应的w进行访问                dfs(isVisited,w);            }            //如果w结点已经被访问过，应该查找邻接点的下一个接待你            w = getNextNeighbor(i,w);        }    }

思维导图

转载地址：http://gqgpb.baihongyu.com/