Depth first and breadth first Java implementation code examples

In programming life, we always meet tree structure. These days, we just need to operate the tree structure, so we can record our own operation mode and process. Now suppose there is such a tree, (it doesn't matter whether it is a binary tree or not, and the principle is the same)

1. Depth first

The English abbreviation is DFS, namely depth first search

Depth first search is a method that is widely used in the early stage of crawler development. Its purpose is to reach the leaf nodes of the searched structure (that is, those HTML files that do not contain any hyperlink). In an HTML file, when a hyperlink is selected, the linked HTML file will perform a depth first search, that is, a single chain must be completely searched before searching the rest of the hyperlink results. Depth first search follows the hyperlink on the HTML file until it can no longer go deep, then returns to an HTML file, and then continues to select other hyperchains in the HTML file. When there are no other hyperlinks to choose from, the search has ended. In brief, the process is to go deep into every possible branch path, and each node can only access it once. For the above example, the result of depth first traversal is: A, B, D, e, I, C, F, G, H. (suppose to go to the left of the child node first).

Depth first traversal of each node requires the use of the data structure of stack. Stack is characterized by first in and last out. The whole traversal process is as follows:

First, press node a into the reactor, stack (a);

Pop up node a, and press the child nodes C and B of a into the heap. At this time, B is at the top of the heap, stack (B, c);

Pop up node B, and press the child nodes E and D of B into the heap. At this time, D is at the top of the heap, stack (D, c);

Pop up node D and no child nodes are pressed in. At this time, e is at the top of the heap and stack (E, c);

Pop up node E and press the child node i of e into stack (I, c);

... Go down in sequence and finally complete the traversal. The Java code is roughly as follows:

2. Breadth first

The English abbreviation is BFS, that is, bread first search. In terms of process inspection, the nodes of each layer are accessed in turn, and after accessing one layer, they enter the next layer, and each node can only be accessed once. For the above example, the results of breadth first traversal are: A, h, I (assuming that each layer node accesses from left to right).

The breadth first traversal of each node requires the data structure of queue. Queue is characterized by first in first out. In fact, double ended queue can also be used. The difference is that nodes can be inserted and ejected at the first place of the double ended queue. The whole traversal process is as follows:

First, insert node a into the queue, queue (a);

Pop up node a, and insert the child nodes B and C of a into the queue. At this time, B is at the beginning of the queue, C is at the end of the queue, and queue (B, c);

Pop up node B, and insert the child nodes D and e of B into the queue. At this time, C is at the beginning of the queue, e is at the end of the queue, and queue (C, D, e);

Pop up node C, and insert the child nodes F, G and h of C into the queue. At this time, D is at the beginning of the queue, h is at the end of the queue, and the queue (D, e, F, G, H);

Pop up node D. D has no child nodes. At this time, e is at the beginning of the queue, h is at the end of the queue, and queue (E, F, G, H);

... Go down in sequence and finally complete the traversal. The Java code is roughly as follows:

summary

The above is all about the depth first and breadth first Java implementation code examples in this paper. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out. Thank you for your support!