什么是DFS和BFS?

技术文章 1个月前 完美者
1,344 0

标签:就是   要求   list   oid   ati   vat   pre   ==   优先   

深度优先遍历DFS

1、递归实现

递归实现比较简单。也就是前序遍历,我们依次遍历当前节点,左节点,右节点即可,以此不断递归下去,直到叶节点(终止条件)。

public class Solution {
    private static class Node {
        public int value;
        public Node left;
        public Node right;
    }

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public static void dfs(Node treeNode) {
        if(treeNode == null) {
            return;
        }

        // 遍历节点
        process(treeNode);
        // 遍历左节点
        dfs(treeNode.left);
        // 遍历右节点
        dfs(treeNode.right);
    }
}

递归的表达性很好,也很容易理解,不过如果递归层次过深,则很容易导致栈溢出。

2、非递归实现(使用栈实现)

对于二叉树的先序遍历,我们有以下思路:

1、对于每个节点来说,先遍历当前节点,然后把右节点压栈,再压左节点(这样弹栈的时候会先得到左节点遍历,这是符合深度优先遍历的要求的)

2、弹栈,拿到栈顶的节点,如果节点不为空,重复步骤1,如果为空,结束遍历。

public static void dfsWithStack(Node root) {
    if(root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    // 先把根节点压栈
    stack.push(root);
    while(!stack.isEmpty()) {
        Node treeNode = stack.pop();
        process(treeNode)    // 遍历节点
        if(treeNode.right != null) {
            stack.push(treeNode.right);
        }

        if(treeNode.left != null) [
            stack.push(treeNode.left);
        }
    }
}

广度优先搜索BFS

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

private static void bfs(Node root) {
    if(root == null) {
        return;
    }

    Queue<Node> stack = new LinkedList<>();
    stack.add(root);

    while(!stack.isEmpty()) {
        Node node = stack.poll();
        System.out.println("value = " + node.value);
        Node left = node.left;
        if(left != null) {
            stack.add(left);
        }

        Node right = node.right;
        if(right != null) {
            stack.add(right);
        }
    }
}

 

什么是DFS和BFS?

标签:就是   要求   list   oid   ati   vat   pre   ==   优先   

原文地址:https://www.cnblogs.com/seeyoumiter/p/14163362.html

版权声明:完美者 发表于 2020-12-25 11:53:08。
转载请注明:什么是DFS和BFS? | 完美导航

暂无评论

暂无评论...