Hello, I am Xiao Huang, a Java development engineer of Unicorn Enterprise. Thank you for meeting us in the vast sea of people. As the saying goes: When your talent and ability are not enough to support your dream, please calm down and study. I hope you can study with me and work hard together to realize your own dream.

One, foreword

In the last article, we talked about the visual description of the graph. I don’t know if you still remember. If you have no impression, you can look at the content of the previous period

For graphs, there are no more than two search methods, depth first search (DFS) and breadth first search (BFS)

The two search algorithms are not quite the same, so today we’re going to look at them

Depth-first search

When we think of depth-first search, recursion is the first thing that comes to mind

Yes, deep search is a search that relies on recursive methods. Let’s look at an example:For the figure above, the depth-first search route is:0 -> 3 -> 2 -> 4 -> 5 -> 1

For those of you who don’t know deep search, read this article: Deep First Search

Recursive version:

	/** * depth-first search **@param node
     * @param set
     */
	public void DFS(Node node, Set<Node> set) {
        if (node == null) {
            return;
        }
        if(! set.contains(node)) { set.add(node); System.out.print(node.value +"");
            for(Node node1 : node.nexts) { DFS(node1, set); }}}Copy the code

Iteration version:

	/** * depth-first search **@param node
     */
	public void DFS(Node node) {
        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();
        stack.add(node);
        set.add(node);
        System.out.print(node.value + "");
        while(! stack.isEmpty()) { Node cur = stack.pop();for (Node next : cur.nexts) {
                if(! set.contains(next)) { stack.add(cur);// It is used for memorization
                    stack.add(next);
                    System.out.print(next.value + "");
                    set.add(next);
                    break; }}}}Copy the code

Test results:

Iteration version:0 3 2 4 5 1Recursive version:0 3 2 4 5 1 
Copy the code

Third, breadth first search

For breadth-first search, simply go round and round like a map

Let’s look at an example:For the figure above, the depth-first search route is:0 -> 1 -> 2 -> 4 -> 5

For those of you who don’t know much about search, check out this article: Breadth-first Search

	/** ** breadth first search **@param node
     */
    public static void BFS(Node node) {
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        // Indicates whether it is in use
        Set<Node> set = new HashSet<>();
        queue.add(node);
        set.add(node);
        while(! queue.isEmpty()) { Node cur = queue.poll(); System.out.print(cur.value +"");
            for (Node next : cur.nexts) {
                if(! set.contains(next)) { queue.add(next); set.add(next); }}}}Copy the code

Four, conclusion

This depth-first search and breadth-first search are relatively simple

To give you an idea of graph search, the next few installments will cover some real algorithms

In algorithmic problems, they don’t just ask you to do deep and broad searches, they often come up with things like minimum spanning trees

This period of content is here, algorithm source code can be in wechat public number reply: algorithm source code, you can get the link, the next period will be about topological sorting algorithm

I am a Java development engineer of a unicorn enterprise. I hope you can pay attention to it. If you have any questions, you can leave a message or add a private message to my wechat.