圖深度優先遍歷：先用自己通俗易懂的話描述一下：從某個結點出發的一條路走到不能再走了，就回傳到上一個結點，如果還是沒有路就再回傳到上一個結點，簡稱：一條路走到黑，
準備一個堆疊（記錄深度優先遍歷的路徑）和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;
}
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/389217.html
標籤：其他
上一篇：圖的拓撲排序演算法