java数据结构和算法——图的深度优先（DFS）遍历

一、图的遍历介绍

• 所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，
• 一般有两种访问策略: (1)深度优先遍历； (2)广度优先遍历。

二、图的深度优先搜索(Depth First Search)

• 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
• 这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
• 深度优先搜索是一个递归的过程。

三、图的深度优先遍历算法步骤

1. 访问初始结点v，并标记结点v为已访问。
2. 查找结点v的第一个邻接结点w。
3. 若w存在，则继续执行步骤4，如果w不存在，则回到步骤1，将从v的下一个结点继续。
4. 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤1、2、3）。
5. 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。

四、图的深度优先遍历示例需求

对下图进行深度优先搜索, 从A 开始遍历.

五、图的深度优先遍历代码示例

1、定义一个图 类

package com.rf.springboot01.dataStructure.graph;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @description: 定义一个图 类
 * @author: xiaozhi
 * @create: 2020-10-28 21:58
 */
public class Graph {
    private ArrayList vertexList;//存储顶点集合
    private int[][] edges;//存储图所对应的邻接矩阵
    private int numEdges;//表示边的数量
    private boolean[] isVisited;//定义一个boolean类型的数组,记录某个节点是否被访问

    //构造方法 n表示有多少个顶点
    public Graph(int n){
        //初始化
        vertexList=new ArrayList(n);
        edges =new int[n][n];
        numEdges=0;
        isVisited=new boolean[5];
    }
    
    /** 
    * @Description: 得到第一个邻接结点的下标 w
    * @param  index
    * @Author: xz
    * @return: 如果存在就返回对应的下标，否则返回-1
    * @Date: 2020/10/28 22:27  
    */
    public int getFirstNodeIndex(int index){
        for(int j=0;j 0){
                return j;
            }
        }
        return -1;
    }
    /** 
    * @Description: 根据前一个邻接结点的下标来获取下一个邻接结点
    * @Author: xz
    * @return: 如果存在就返回对应的下标，否则返回-1
    * @Date: 2020/10/28 22:38
    */
    public int getNextNodeIndex(int v1,int v2){
        for(int j=v2+1; j 0){
                return j;
            }
        }
        return -1;
    }
    /** 
    * @Description: 深度优先遍历算法
    * @param i          第一次就是 0
     *        isVisited  某个节点是否被访问
    * @Author: xz
    * @Date: 2020/10/28 22:42
    */
    public void dfsMethods(boolean[] isVisited,int i){
        //1、输出该节点
        System.out.print(getValueByIndex(i)+"->");
        //2、将节点设置为已访问
        isVisited[i] = true;
        //3、查找结点i的第一个邻接结点w
        int w = getFirstNodeIndex(i);
        if(w != -1){//说明存在邻接结点w
            if(!isVisited[w]){//邻接结点w未被访问过
                dfsMethods(isVisited,w);//递归
            }
            //如果邻接结点w已经被访问过
            w = getNextNodeIndex(i,w);
        }
    }
    /**
    * @Description: 重载dfsMethods方法
    * @Author: xz
    * @Date: 2020/10/28 22:47
    */
    public void dfsMethods() {
        isVisited = new boolean[vertexList.size()];
        //遍历所有的结点，进行dfs[回溯]
        for(int i=0;i"A" 1->"B" 2->"C"
    * @Author: xz
    * @Date: 2020/10/28 22:31
    */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    /**
    * @Description: 返回v1和v2的权值
    * v1 表示点对应的的下标
    * v2 表示第二个顶点对应的下标
    * @Author: xz
    * @Date: 2020/10/28 22:34
    */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }
    
    /** 
    * @Description: 显示图对应的矩阵
    * @Author: xz
    * @Date: 2020/10/28 22:44
    */
    public void showGraph(){
        for(int[] link : edges) {
            System.err.println(Arrays.toString(link));
        }
    }

}

2、定义图的测试类

package com.rf.springboot01.dataStructure.graph;

/**
 * @description: 创建图的测试类
 * @author: xiaozhi
 * @create: 2020-10-28 22:48
 */
public class GraphTest {
    public static void main(String[] args) {
        int n =5;//节点个数
        String vertexs[] ={"A","B","C","D","E"};//定义5个节点
        //1、创建图对象
        Graph graph = new Graph(n);
        //2、循环添加顶点
        for(String vertex : vertexs){
            graph.insertVertex(vertex);
        }
        //3、添加边 A-B A-C B-C B-D B-E
        graph.insertEdge(0, 1, 1);//A-B
        graph.insertEdge(0, 2, 1); //A-C
		graph.insertEdge(1, 2, 1); //B-C
	    graph.insertEdge(1, 3, 1); //B-D
		graph.insertEdge(1, 4, 1); //B-E

       /* System.out.println("显示邻结矩阵============");
        graph.showGraph();*/


        System.out.println("深度优先遍历+++++++++++++++++");
        graph.dfsMethods();
    }
}

3、运行测试类，输出结果如下：