一、深度优先搜索
深度优先搜索是一个针对图和树的遍历算法。早在19世纪就被用于解决迷宫标题。
对于下面的树而言，DFS方法起首从根节点1开始，其搜索节点序次是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。
DFS的非递归实现方式相比于BFS应该说大同小异，只是把queue换成了stack而已，stack具有后进先出LIFO(Last Input First Output)的特性，DFS的操纵步调如下：
- 1、把起始点放入stack；
- 2、重复下述3步调，直到stack为空为止：
- 从stack中访问栈顶的点；
- 找出与此点毗连的且尚未遍历的点，举行标志，然后全部放入stack中；
- 假云云点没有尚未遍历的毗连点，则将此点从stack中弹出。
二、深度优先遍历(非递归)图文演示
下面团结一个图(graph)的实例，分析DFS的工作过程和原理：
- 1、将起始节点1放入栈stack中，标志为已遍历。
- 2、从stack中访问栈顶的节点1，找出与节点1毗连的节点，有2、9两个节点，我们可以选择此中任何一个，选择规则可以人为设定，这里假设按照节点数字序次由小到大选择，选中的是2，标志为已遍历，然后放入stack中。
- 3、从stack中取出栈顶的节点2，找出与节点2毗连的节点，有1、3、5三个节点，节点1已遍历过，清除；3、5中按照预定的规则选中的是3，标志为已遍历，然后放入stack中。
- 4、从stack中取出栈顶的节点3，找出与节点3毗连的节点，有2、4两个节点，节点2已遍历过，清除；选中的是节点4，标志为已遍历，然后放入stack中。
- 5、从stack中取出栈顶的节点4，找出与节点4毗连的节点，有3、5、6三个节点，节点3已遍历过，清除；选中的是节点5，标志为已遍历，然后放入stack中。
- 6、从stack中取出栈顶的节点5，找出与节点5毗连的节点，有2、4两个节点，节点2、4都已遍历过，因此节点5没有尚未遍历的毗连点，则将此点从stack中弹出。
- 7、当前stack栈顶的节点是4，找出与节点4毗连的节点，有3、5、6三个节点，节点3、5都已遍历过，清除；选中的是节点6，标志为已遍历，然后放入stack中。
- 8、当前stack栈顶的节点是6，找出与节点6毗连的节点，有4、7、8三个节点，4已遍历，按照规则选中的是7，标志为已遍历，然后放入stack中。
- 9、当前stack栈顶的节点是7，找出与节点7毗连的节点，只有节点6，已遍历过，因此没有尚未遍历的毗连点，将节点7从stack中弹出。
- 10、当前stack栈顶的节点是6，找出与节点6毗连的节点，有节点7、8，7已遍历过，因此将节点8放入stack中。
- 11、当前stack栈顶的节点是8，找出与节点8毗连的节点，有节点1、6、9，1、6已遍历过，因此将节点9放入stack中。
- 12、当前stack栈顶的节点是9，没有尚未遍历的毗连点，将节点9弹出，依次类推，栈中剩余节点8、6、4、3、2、1都没有尚未遍历的毗连点，都将弹出，末了栈为空。
- 13、DFS遍历完成。
三、毗连表举行深度优先遍历
3.1 构建数据布局
public class Graph { //顶点个数 private int V; //边的条数 private int E; //领接表的底层存储布局 private TreeSet<Integer>[] adj;}3.2 通过该布局界说，构造一个图(无向图）
/** * @Author: huangyibo * @Date: 2022/3/28 1:02 * @Description: 领接表, 现在只支持无向无权图 */public class Graph { //顶点个数 private int V; //边的条数 private int E; //领接表的底层存储布局 private TreeSet<Integer>[] adj; public Graph(String filename){ File file = new File(filename); try { Scanner scanner = new Scanner(file); V = scanner.nextInt(); if(V < 0){ throw new IllegalArgumentException("V must be non-negative"); } adj = new TreeSet[V]; //初始化领接表 for (int i = 0; i < V; i++) { adj = new TreeSet<>(); } E = scanner.nextInt(); if(E < 0){ throw new IllegalArgumentException("E must be non-negative"); } for (int i = 0; i < E; i++) { int a = scanner.nextInt(); //校验顶点a是否合法 validateVertex(a); int b = scanner.nextInt(); //校验顶点b是否合法 validateVertex(b); //校验是否是自环边 if(a == b){ throw new IllegalArgumentException("Self Loop is Detected!"); } //校验是否是平行边 if(adj[a].contains(b)){ throw new IllegalArgumentException(" arallel Edges are Detected!"); } adj[a].add(b); adj.add(a); } } catch (FileNotFoundException e) { e.printStackTrace(); } } /** * 校验顶点是否合法 * @param v */ private void validateVertex(int v){ if(v < 0 || v >= V){ throw new IllegalArgumentException("vertex " + v + " is invalid"); } } /** * 获取顶点个数 * @return */ public int V(){ return V; } /** * 获取边的条数 * @return */ public int E(){ return E; } /** * 图中是否存在v到w的边 * @param v * @param w * @return */ public boolean hasEdge(int v, int w){ //校验顶点v是否合法 validateVertex(v); //校验顶点w是否合法 validateVertex(w); return adj[v].contains(w); } /** * 返回和v相邻的顶点 * @param v * @return */ public Iterable<Integer> adj(int v){ //校验顶点v是否合法 validateVertex(v); return adj[v]; } /** * 返回顶点v的度 * 顶点v的度（Degree）是指在图中与v干系联的边的条数 * @param v * @return */ public int degree(int v){ //校验顶点v是否合法 validateVertex(v); return adj[v].size(); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append(String.format("V = %d, E = %d\n", V, E)); for (int v = 0; v < V; v++) { sb.append(String.format("%d : ", v)); for (Integer w : adj[v]) { sb.append(String.format("%d ", w)); } sb.append("\n"); } return sb.toString(); }}3.3 毗连表的深度优先算法(非递归)
/** * @Author: huangyibo * @Date: 2022/3/28 1:02 * @Description: 图的深度优先遍历, 非递归方式 */public class GraphDFS { private Graph G; /** * 图的顶点是否已经被遍历过 */ private boolean[] visited; //图的深度优先遍历效果 private List<Integer> order = new ArrayList<>(); public GraphDFS(Graph G){ this.G = G; visited = new boolean[G.V()]; //循环全部顶点, 防止一个图出现多个连通图(连通分量)的情况 for (int v = 0; v < G.V(); v++) { if(!visited[v]){ dfs(v); } } } /** * 图的深度优先遍历, 非递归方式 * @param source */ private void dfs(int source) { Stack<Integer> stack = new Stack<>(); //将源结点压入栈顶 stack.push(source); //标志为已访问 visited[source] = true; //假如栈不为空 while(!stack.isEmpty()){ Integer v = stack.pop(); //当前出栈顶点添加到图的深度优先遍历效果集 order.add(v); //遍历顶点V的相邻顶点 for (Integer w : G.adj((v))) { //假如没有遍历过 if(!visited[w]){ //顶点w压入栈顶 stack.push(w); //标志w为已访问 visited[w] = true; } } } } /** * 图的深度优先遍历效果集 * @return */ public List<Integer> order(){ return order; } public static void main(String[] args) { Graph graph = new Graph("src/main/resources/g1.txt"); GraphDFS graphDFS = new GraphDFS(graph); System.out.println(graphDFS.order()); }}g1.txt
7 60 10 21 31 42 32 6参考：
https://blog.csdn.net/saltriver/article/details/54429068 |
