深度优先遍历（DFS）是一种用于遍历或搜索图的算法。以下是对它的详细介绍：
1. 定义
基本思想：从图中某个起始顶点出发，沿着一条路径尽可能深地访问图中的顶点，直到无法继续前进（即到达一个没有未访问邻接顶点的顶点），然后回溯到上一个顶点，沿另一条未访问过的路径继续深入访问，重复此过程，直到所有顶点都被访问过。
遍历方式：在遍历过程中，每次访问一个顶点后，会先将该顶点标记为已访问，然后递归地访问其所有未被访问的邻接顶点。当一个顶点的所有邻接顶点都被访问过时，算法会回溯到前一个顶点，继续探索其他未访问的分支。
2. 特点
深度优先：尽可能地向深处探索，优先访问未被访问的子节点，直到达到最远的顶点。
回溯机制：当在某个分支上无法继续前进时，会回溯到上一个顶点，寻找其他未访问的分支。
不保证最短路径：由于是深度优先搜索，所以找到的路径不一定是最短路径，但它可以遍历到图中的所有可达顶点。
3. 适用场景
迷宫求解：可以用来寻找迷宫中的一条路径，从起点开始，沿着一条路径一直走到尽头，如果走不通就回溯，尝试其他路径，直到找到出口。
连通性问题：判断图中的两个顶点是否连通，可以通过深度优先遍历从一个顶点出发，看能否访问到另一个顶点来确定。
拓扑排序：对有向无环图进行拓扑排序，可以先对图进行深度优先遍历，然后在遍历过程中记录每个顶点的完成时间，最后按照完成时间的逆序输出顶点，即可得到拓扑排序。
4. 实现方式
递归实现：使用递归函数来实现深度优先遍历是比较直观的方式。递归函数会不断地调用自身来访问当前顶点的邻接顶点，直到所有顶点都被访问过。
非递归实现：为了避免递归带来的栈溢出问题，也可以使用栈数据结构来实现非递归的深度优先遍历。将起始顶点放入栈中，然后进入循环，在循环中弹出栈顶元素作为当前顶点，访问它并将其所有未被访问的邻接顶点按顺序压入栈中，重复此过程直到栈为空。
5.算法示例
1.图数据定义,邻接表实现
public class Node {//节点位置int data;//下一个节点Node nextNode;//节点默认空值Node() {};//节点变量Node(int val){data=val;}//节点初始化Node(int val,Node node){data=val;nextNode=node;}
}
2.dfs算法实现
import java.util.ArrayList;
import java.util.List;public class GraphTest {//创建领接表//顶点 A B C D E F//边 AB AC BD DF EFpublic static void creatGraph(){//创建顶点List<Character> vList=new ArrayList<>();for(int i=0;i<6;i++){vList.add((char)('A'+i));}//创建空列表存储空节点,表示相互领接关系List<Node> vNodeList=new ArrayList<>();for(int i=0;i<vList.size();i++){vNodeList.add(null);}//插入领接关系//A->B 0-1insert(0,1,vNodeList);//A->C 0-2insert(0,2,vNodeList);//B->D 1-3insert(1,3,vNodeList);//D->F 3-5insert(3,5,vNodeList);//E->F 4-5insert(4,5,vNodeList);//领接表打印for(int i=0;i<vNodeList.size();i++){System.out.print(vList.get(i));System.out.print("-->");Node curNode=vNodeList.get(i);while (curNode!=null){System.out.print(vList.get(curNode.data));System.out.print(" ");System.out.print(curNode.data);System.out.print(" ");curNode=curNode.nextNode;}System.out.println();}//DFS深度优先遍历//标记数组,默认值为false,不做处理boolean [] flagArr=new boolean[6];System.out.print("深度优先遍历邻接表顺序为:");dfsSearch(vNodeList,0,flagArr);System.out.println();System.out.print("未访问到的孤点为:");for(int i=0;i<flagArr.length;i++){if(flagArr[i]==false){System.out.print(vList.get(i));}}}//DFS算法static void dfsSearch(List<Node> nodeList,int v,boolean [] flagArr){//访问操作System.out.print((char) (v+'A'));System.out.print(" ");//改标记flagArr[v]=true;//访问邻居Node curP=nodeList.get(v);while (curP!=null){//判断是否存在边，并且没有被访问过if(flagArr[curP.data]==false){dfsSearch(nodeList, curP.data, flagArr);}//如果递归进行不下去会回退到上一个节点去访问其它的节点curP=curP.nextNode;}}//头插入法插入相互领接数据//v1为顶点位置，v2为相互领接顶点的位置public static void insert(int v1,int v2,List<Node> list){//创建一个节点Node newNode=new Node(v2);//新的节点指向列表里的节点newNode.nextNode=list.get(v1);//存储当前节点在列表里list.set(v1,newNode);}public static void main(String[] args) {creatGraph();}
}
3.遍历结果打印，如果不是起始点，孤点和没有入度的点不能够被访问到
