算法学习（19）—广度优先遍历BFS

1、什么是广度优先遍历？

①也就是我们说的广度搜索算法

②实现方式：利用队列和递归来实现

③思路：通过队列来实现的，找到一个起点A，并将A相邻的点放入队列中，这时将队首元素B取出，并将B相邻且没有访问过的点放入队列中，不断重复这个操作，直至队列清空，这时候，依次访问的顶点就是遍历的顺序。

④适用场景：寻找最短路径的问题

2、广度优先遍历的原理

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。

3、广度优先遍历的实现

深度优先遍历用的是栈，而广度优先遍历要用队列来实现

public class BfsTree {

    public static void main(String[] args) {
        TreeNode rootNode = buildTree();
        bfs(rootNode);
    }

    public static void bfs(TreeNode node) {
        if (node == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            System.out.print("->" + current.getVal());
            if (current.getLeft() != null) {
                queue.add(current.getLeft());
            }

            if (current.getRight() != null) {
                queue.add(current.getRight());
            }
        }
    }

    public static TreeNode buildTree() {
        TreeNode head = new TreeNode(1);
        TreeNode second = new TreeNode(2);
        TreeNode three = new TreeNode(3);
        TreeNode four = new TreeNode(4);
        TreeNode five = new TreeNode(5);
        TreeNode six = new TreeNode(6);
        TreeNode seven = new TreeNode(7);
        head.right = three;
        head.left = second;
        second.right = five;
        second.left = four;
        three.right = seven;
        three.left = six;
        return head;
    }
}