图深度优先遍历:先用自己通俗易懂的话描述一下:从某个结点出发的一条路走到不能再走了,就返回到上一个结点,如果还是没有路就再返回到上一个结点。简称:一条路走到黑。
准备一个栈(记录深度优先遍历的路径)和HashSet(确保每个结点只进一次栈)。
并且打印的时机是进栈的时候,进栈就打印,所以栈弹出的时候就不要打印了。
栈弹出的时候,遍历当前结点的所有直接邻居,如果当前结点的直接邻居没有在HashSet里,就把父结点(当前结点)重新压入栈,直接邻居也压入栈,这个直接邻居也要压入HashSet,然后打印这个直接邻居。如果有不理解直接邻居的,建议先看看这篇文章——图结构的实现,从点到边再到图。这跟实现图的方式有关,跟宽度优先遍历一样,图的深度优先遍历只需要用到点结构。
放上一张图片,再结合核心代码供大家理解:
package com.harrison.class11; import java.util.HashSet; import java.util.Stack; import com.harrison.class11.Code01_NodeEdgeGraph.Node; public class Code03_DFS { public static void dfs(Node node) { if(node==null) { return ; } Stack<Node> stack=new Stack<Node>(); HashSet<Node> set=new HashSet<>(); stack.push(node); set.add(node); System.out.println(node.value); while(!stack.isEmpty()) { Node cur=stack.pop(); for(Node next:cur.nexts) { if(!set.contains(next)) { stack.push(cur); stack.push(next); set.add(next); System.out.println(next.value); break; } } } } }