Text begins ：

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 .

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 , Breadth first traversal , I'm sure you'll get something .

Depth-first traversal

• Introduction to depth first traversal
• Exercise exercise
• DFS,BFS Applications in search engines

Depth first traversal resume

The main idea is to extract an unreachable vertex from the graph V Start , Go all the way to the end , Then back from the node at the end of the road to the previous node , Start from another road to the end …, Repeat this process recursively , Until all the vertices are traversed , It is characterized by not hitting the south wall and not looking back , Go one way first , Another way to go .

Tree is a special case of graph ( A connected acyclic graph is a tree ), Next let's see how to traverse a tree with depth first .

1、 We're from the root node 1 To traverse the , Its adjacent nodes have 2,3,4, First traverse the nodes 2, Re traversal 2 Child nodes of 5, And I'm going to go through it again 5 Child nodes of 9.

2、 One of the roads in the picture above has come to the end (9 It's a leaf node , No more traversable nodes ), From now on 9 Fallback to previous node 5, Take a look at the nodes 5 Is there anything else besides 9 Other nodes , Didn't go back to 2,2 It's not except 5 Other nodes , Back to 1,1 Division 2 Other nodes 3, So from the node 3 Start depth first traversal , as follows ：

3、 Similarly, from 10 Start going back up to 6, 6 There is no division 10 Other child nodes , Go back up , Find out 3 Division 6 The other way around 7, So it's going to traverse 7.

4、 from 7 Go back to 3, 1, Find out 1 And nodes 4 Not traversing , So this time along 4, 8 Traversal , This completes the traversal .

The complete node traversal order is as follows ( The blue numbers on the nodes represent )：

I believe you can see that this is the pre order traversal of the tree , In fact, whether it's preamble traversal , Or middle order traversal , Or post order traversal , All belong to depth first traversal .

How to implement depth first traversal , There are two expressions of recursion and non recursion , Next, let's take binary tree as an example to see how to implement depth first traversal by recursion and non recursion respectively .

1、 Recursive implementation

Recursive implementation is relatively simple , Because it's preamble traversal , So we traverse the current node in turn , The left node , Right node , For left and right nodes , Just traverse their left and right nodes one by one , Recursion goes on and on , Until the leaf node ( Recursive termination condition ), The code is as follows ：

public class Solution { 
    private static class Node { 
        /** 
         *  Node values  
         */ 
        public int value; 
        /** 
         *  The left node  
         */ 
        public Node left; 
        /** 
         *  Right node  
         */ 
        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; 
        } 
        //  Traversal node  
        process(treeNode) 
        //  Traverse the left node  
        dfs(treeNode.left); 
        //  Traverse the right node  
        dfs(treeNode.right); 
    } 
} 

Recursion is very expressive , And it's easy to understand , But if the hierarchy is too deep , It's easy to cause stack overflow . So let's focus on non recursive implementation .

2、 Non recursive implementation

Carefully observe the characteristics of depth first traversal , For a binary tree , Because it's traversal first ( First traverse the current node , Traverse left node again , Then traverse the right node ), So we have the following ideas ：

For each node , First traverse the current node , Then stack the right node , Press the left node again ( In this way, when you play the stack, you will get the left node to traverse first , Meet the depth first traversal requirements ).

Bomb stack , Get the node at the top of the stack , If the node is not empty , Repeat step 1, If it is empty , End traversal .

Let's take the following binary tree as an example to see how to use stack to achieve DFS.

The overall dynamic diagram is as follows ：

The overall thinking is relatively clear , Use the stack to stack the nodes to be traversed , Then check whether there is any node that has not been traversed after the stack , Some words press the stack , If you don't, keep going back ( Out of the stack ), A train of thought , It is not difficult to write the following binary tree depth first traversal code implemented by stack ：

/** 
 *  Using stacks to implement  dfs 
 * @param root 
 */ 
public static void dfsWithStack(Node root) { 
    if (root == null) { 
        return; 
    } 
 
    Stack<Node> stack = new Stack<>(); 
    //  First stack the root node  
    stack.push(root); 
    while (!stack.isEmpty()) { 
        Node treeNode = stack.pop(); 
        //  Traversal node  
        process(treeNode) 
 
        //  Press the right node first  
        if (treeNode.right != null) { 
            stack.push(treeNode.right); 
        } 
 
        //  Press the left node again  
        if (treeNode.left != null) { 
            stack.push(treeNode.left); 
        } 
    } 
} 

You can see that it is not complicated to use stack to implement depth first traversal , And don't worry about stack overflow caused by too deep recursion .

ending

This is the depth first traversal algorithm I understand , If there's something wrong , Welcome to point out , thank you .