大家好，我是一名计算机专业的大三在校生，自不量力想明年秋招进大厂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）直到队列变空
