Preface

Depth-first traversal (Depth First Search, abbreviation DFS) With breadth first traversal (Breath First Search) Two very important algorithms in graph theory , It is widely used in topological sorting in production , Pathfinding ( Labyrinth ), Search engine , Reptiles, etc , It also appears frequently in leetcode, High frequency interview questions .

This article will talk about depth first traversal from the following aspects. I believe you will gain something after reading it .

Breadth first traversal

• Breadth first traversal profile
• Exercise exercise
• BFS Applications in search engines

Breadth first traversal profile

Breadth first traversal

Breadth first traversal , It refers to starting from an unretraversal node of the graph , First, traverse the adjacent nodes of this node , Then traverse the adjacent nodes of each adjacent node in turn .

The breadth first traversal graph of the tree mentioned above is as follows , The value of each node is their traversal order . So breadth first traversal is also called sequence traversal , First, go through the first layer ( node 1), Go through the second layer ( node 2,3,4), The third level (5,6,7,8), The fourth level (9,10).

Depth first traversal uses stacks , Breadth first traversal is implemented by queues , Let's take the binary tree as an example to see how to implement breadth first traversal with queues .

Diagram below :

I believe I saw the moving picture above , It's not hard to write the following code :

/** 
 *  Using queue implementation  bfs 
 * @param root 
 */ 
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); 
        } 
    } 
} 

Conclusion

Is it obvious that breadth first traversal is much simpler than depth first traversal , I believe you must have a deeper understanding of breadth first traversal . If there is something wrong , Welcome to point out . Thank you. .