Shulou(Shulou.com)06/02 Report--

How to carry out the depth-priority search of the map of the data structure, many novices are not very clear about this. In order to help you solve this problem, the following editor will explain it in detail. People with this need can come and learn. I hope you can get something.

Ergodic principles:

Starting from a specified vertex v in the graph, visit v first, and then conduct a depth-first search from the adjacent vertex w, which has not been accessed, until all the vertices in the graph that are connected with v are visited, which is equivalent to completing a traversal of the connected component of vertex v in the graph. If there are vertices in the graph that have not yet been traversed, repeat the process from another unaccessed vertex until all the vertices in the graph are traversed.

Obviously, the depth-first search algorithm is a recursive algorithm.

Analysis:

Suppose you have a picture, as shown in the following figure.

The adjacency table of the graph is:

If you do a depth-first search on the graph, the steps are as follows:

STEP1: do a depth-first search from vertex A. First visit vertex An and mark An as visited (yellow in the figure), then find the first adjacency point of vertex A, and search for the next adjacency point of vertex An if the first adjacency point has been accessed. Obviously, the first adjacent point of vertex An is vertex B, and B is not accessed.

STEP3: visit vertex C and mark C as visited (orange in the figure), looking for the first adjacency point B of C, because B has already been accessed, so finding the next adjacency point DJE D has not been visited.

STEP5: visit vertex E, and mark E as visited state (red in the figure), visit the first adjacency point D of E, find that D has been visited, then go to the next adjacency point of E, and find that there is no adjacency point, then return to the upper layer, that is, STEP4.

STEP7: look for the unaccessed adjacency point of vertex D and find that there is no such adjacency point, return the STEP3 layer; look for the unaccessed adjacency point of vertex C, and find that there is no such adjacency point, return the STEP2 layer; look for the unaccessed adjacency point of vertex B, and find that there is no such adjacency point, then return the STEP1 layer Look for the unvisited adjacency point of vertex An and find that there is no such adjacency point, then exit the program. At this point, the access to each vertex in the graph is over.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.