一、什么是图的遍历

图的遍历，指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。

二、深度优先遍历（DFS）的基本思想

深度优先遍历（death first search）即DFS，从初始结点出发，初始结点可能会有多个邻接结点，访问完初始结点后，将其标记为已访问，再任意选择一个未被访问的邻接结点，然后再以这个被选择的邻接结点作为初始结点，再任意选择它的下一个未被访问邻接结点，以此类推。大概可以先理解为：每次都在访问完当前结点后首先访问的是未被访问的邻接结点，并任意选择一个邻接结点视为初始结点，继续遍历下去。

想必在这时候，很多小伙伴已经发现问题了。当下一个结点的全部邻接结点都已经被访问过了，该怎么继续遍历下去呢？🤫哈哈，先不用着急！继续往下看吧！

三、深度优先遍历（DFS）的步骤详解

通常dfs选择未被遍历的邻接结点是任意的，在这里的选择原则是利用邻接矩阵按照结点的顺序[A,B,C,D,E]选择邻接结点。

算法步骤：

1. 访问初始结点v，并标记结点v为已访问
2. 查找结点v的第一个邻接结点w
3. 若w存在，且w未被访问则继续执行4；若w存在，且w被访问则继续执行5；如果w不存在，则返回第1步，将从v的下一个邻接结点继续🤫
4. 对w进行深度优先遍历递归（即将w视为初始结点v，进行123的步骤）
5. 查找结点v的邻接结点w的下一个邻接结点（即寻找v的第二个邻接结点，第一个已经被访问了），转到步骤3

四、深度优先遍历（DFS）的代码实现

（在图的遍历过程中，图是以邻接矩阵的形式呈现的，所以在邻接矩阵上进行遍历）
遍历过程的详解：

1. 访问初始结点A，标记A为已访问 isVisited[0] = true，视线放在邻接矩阵的第一行，A存在邻接结点，A的第一个邻接结点是B，显然B是没有被遍历的，B为第一个邻接结点，B成为初始结点。
2. 访问初始结点B，标记B为已访问 isVisited[1] = true，视线放在邻接矩阵的第二行，B存在邻接结点，B的第一个邻接结点是A，由1知A是已被遍历的；退回到B，继续判断它的第二个邻接结点，B的第二个邻接结点是D，显然D是没有被遍历的，D成为初始结点。
3. 访问初始结点D，标记D为已访问 isVisited[3] = true，视线放在邻接矩阵的第四行，D存在邻接结点，D的第一个邻接结点是A，由1知A是已被遍历的；退回到D，继续判断它的第二个邻接结点，D的第二个邻接结点是B，由2知B是已被遍历的；退回到D，继续判断它的第三个邻接结点，D的第三个邻接结点是C，显然C是没有被遍历的，C成为初始结点。
4. 访问初始结点C，标记C为已访问 isVisited[2] = true，视线放在邻接矩阵的第三行，C存在邻接结点，D的第一邻接结点是A，由1知A是已被遍历的；退回到C，继续判断它的第二邻接结点，C的第二个邻接结点是D，由3知D是已被遍历的；退回到C，继续判断它的第三个邻接结点，C的第三个邻接结点时E，显然E是没有被遍历的，E成为初始结点。
5. 访问初始结点E，标记E为已访问 isVisited[4] = true，视线放在邻接矩阵的第五行，E存在邻接结点，E的第一个邻接结点是C，由4知C是已被遍历的；退回到E，继续判断它的第二个邻接结点，E的第二个邻接结点是D，由3知D是已被遍历的；退回到E，发现E的邻接结点已经全被访问过了，然后就退回C-D-B-A继续寻找是否还有未遍历的邻接结点（回溯）。

package com.datou.graph;

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

/**
 * @author datou
 * @data 2020/8/11 - 18:01
 * @target 图的表示
 * 要求：输入结点及结点数，各个边的连接情况，输出邻接矩阵
 */
public class Graph {
    //结点
    private ArrayList<String> nodeList;
    //邻接矩阵
    private int[][] arr;
    //boolean数组，记录某个结点是否被访问
    private boolean[] isVisited;

    /**
     * 构造器初始化参数
     * @param n 结点个数
     */
    public Graph(int n){
        nodeList = new ArrayList<String>(n);
        arr = new int[n][n];
        isVisited = new boolean[n];
    }

    /**
     * 插入结点
     * @param nodeValue
     */
    public void insertNode(String nodeValue){
        nodeList.add(nodeValue);
    }

    /**
     * 无向图添加边，连接则为1，否则则为0
     * @param v1 结点1
     * @param v2 结点2
     * @param weight 权值
     */
    public void insertArr(int v1, int v2, int weight){
        arr[v1][v2] = weight;
        arr[v2][v1] = weight;
    }

    /**
     * 显示图
     */
    public void showGraph(){
        for (int[] link : arr){
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 获取第一个邻接结点的下标
     * @param v 初始结点的下标
     * @return 如果存在就返回对应的下标，否则返回-1
     */
    public int getFirstNeighbor(int v){
        for (int i = 0; i < nodeList.size(); i++) {
            if (arr[v][i] > 0){
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据上一个邻接结点来获取下一个邻接结点（即w存在，但是w已经被访问的情况）
     * @param v1 初始结点1下标
     * @param v2 初始结点2下标
     * @return 如果存在就返回对应的下标，否则返回-1
     */
    public int getNextNeighbor(int v1, int v2){
        //即在第一个初始结点的邻接矩阵中，寻找下一个未访问的邻接结点
        //为什么是i是从v2+1起，因为下一个邻接结点在w即v2（存在的第一结点，但是已被遍历）的后面-->按照结点顺序原则选择结点
        for (int i = v2 + 1; i < nodeList.size(); i++) {
            if (arr[v1][i] > 0){
                return i;
            }
        }
        return -1;
    }

    /**
     * 深度优先遍历算法（只是在邻接矩阵的一行中体现）
     * @param isVisited 结点访问数组
     * @param v 初始结点的下标
     */
    public void dfs(boolean[] isVisited, int v){
        //输出第一个初始结点的值
        System.out.print(nodeList.get(v));
        //将初始结点v设置为已访问
        isVisited[v] = true;
        //查找初始结点v的第一个邻接结点w
        int w = getFirstNeighbor(v);
        //说明w存在
        while (w != -1){
            //若w没有被访问过,一直向下递归
            if (!isVisited[w]){
                dfs(isVisited,w);
            }
            //若w被访问过，则退回v继续寻找下一个邻接结点重置w的值
            w = getNextNeighbor(v, w);
        }

    }

    /**
     * 遍历所有结点
     */
    public void dfs(){
        for (int i = 0; i < nodeList.size(); i++) {
            //如果没有被访问过，则进行遍历
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }
    public static void main(String[] args) {
        int n = 5;
        Graph graph = new Graph(n);
        String[] nodeList = {"A","B","C","D","E"};
        for (String nodeValue : nodeList){
            graph.insertNode(nodeValue);
        }
        //A-B A-C A-D B-D C-D C-E D-E
        graph.insertArr(0,1,1);
        graph.insertArr(0,2,1);
        graph.insertArr(0,3,1);
        graph.insertArr(1,3,1);
        graph.insertArr(2,3,1);
        graph.insertArr(2,4,1);
        graph.insertArr(3,4,1);

        graph.showGraph();
        graph.dfs();

    }
}
/**结果：
[0, 1, 1, 1, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 1]
[1, 1, 1, 0, 1]
[0, 0, 1, 1, 0]
ABDCE
**/

教程视频：尚硅谷Java数据结构与算法
😄希望以上的分享对你有所帮助！若有错误，请小伙伴们指出！
理解代码的时候，一边debug一边理解，更加有效哦！