大家好，我是一名計算機專業的大三在校生，自不量力想明年秋招進大廠BATJMZ💪💪💪，由于大學里面荒廢了兩年😔，所以決定從此刻開始改變，希望通過寫博客記錄自己學習和成長的歷程；同時也能夠增長見識，學習到更多的知識，遇見更多志同道合的人🤝🤝🤝，本人目前還只是個青銅，希望和我的讀者朋友們可以共同進步，一起探討，如果我的文章能夠幫到你的話，那實在是我的幸運，也希望我寫的博客內容能夠幫助一些在編程方面有問題的朋友，在這里如果你發現我寫的有哪些不對或不足之處，請您諒解，你可以及時評論或私信來告誡我，我會積極采納改正的，我會努力提升博客文章的質量，如果可以給個三連，那真是十分感謝，🙇?🙇?🙇?
二叉樹的寬度優先遍歷只用到了佇列，不清楚的朋友可以看看這篇文章二叉樹的按層遍歷，但是圖還需要HashSet，因為二叉樹不會有環的問題，二叉樹進行寬度優先遍歷的時候，一個結點不會多次進入佇列，而圖有可能，所以準備一個HashSet，HashSet就是保證每個結點只進一次佇列，
從某個結點出發，假設是X，離X結點最近的一層結點先遍歷，再是遍歷離X距離兩層的結點，接著往下…但是同一層內部具體的遍歷順序沒有要求，佇列彈出的時候，彈出就列印，然后遍歷彈出結點的所有直接鄰居，沒有在HashSetl里的結點才可以加入佇列和HashSet，
注意：佇列和HashSet是同步加入的！！！
package com.harrison.class11;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import com.harrison.class11.Code01_NodeEdgeGraph.Node;
public class Code02_BFS {
// 從node出發，進行寬度優先遍歷，只需要用到點結構
public static void bfs(Node node) {
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
// 在二叉樹進行寬度優先遍歷時不會形成環
// 但圖會形成環，所以必須有個機制來確保每個結點只進一次佇列
HashSet<Node> set = new HashSet<>();
queue.add(node);
set.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
// 遍歷當前結點的所有直接后繼
// 如果set中沒有才加入set和佇列
for (Node next : node.nexts) {
if (!set.contains(next)) {
set.add(next);
queue.add(next);
}
}
}
}
}
寬度優先遍歷只需要用到點結構就可以實作，所以表示圖的方式很重要，這篇文章實作圖的方式就很合適，推薦大家看看——圖結構的實作，從點到邊再到圖，
最后再總結一下，寬度優先遍歷的流程：
1）利用佇列實作
2）從源節點開始依次按照寬度進佇列，然后彈出
3）每彈出一個點，把該節點所有沒有進過佇列的鄰接點放入佇列
4）直到佇列變空
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/387896.html
標籤：其他
下一篇：給你兩個非空的鏈表，表示兩個非負的整數。它們每位數字都是按照逆序的方式存盤的，并且每個節點只能存盤一位數字。請你將兩個數相加，并以相同形式回傳一個表示和的鏈表。