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

This article mainly introduces "the ergodic analysis of C language data structure and algorithm graph". In the daily operation, I believe that many people have doubts about the ergodic analysis of C language data structure and algorithm graph. I hope it will be helpful to answer the doubts of "ergodic analysis of C language data structure and algorithm graph". Next, please follow the editor to study!

Introduce

Depth-first search and breadth-first search are common in data structures. Why is it called depth and breadth? In fact, for the traversal of the graph, please take a look at the following figure:

A graph consists of small dots (called vertices) and straight lines (called edges) that connect them.

For example, the image above is composed of five vertices (numbered 1-2-3-4-4) and 5 edges (1-2-1-3-1-4).

Now we start to traverse the graph from vertex 1, which is to visit every vertex of the graph once. Using depth-first search will get the following results.

The number next to each vertex in the graph indicates which vertex is accessed, which we call a timestamp.

Depth first search

The process of traversing this graph using a depth-first search:

Start with an unpassed vertex as the starting vertex, such as vertex 1. Along the edge of vertex 1 to try other vertices it has not gone through, the first thing to find is that vertex 2 has not been passed, so it comes to vertex 2.

Then use vertex 2 as a starting point to continue to try to visit other unreached vertices, which leads to vertex 4.

Then use Vertex 4 as a starting point to continue to try to visit other untraveled vertices. However, there are no other vertices around vertex 4 at this time, so you need to return to vertex 2. After returning to vertex 2, it is found that you can no longer access other unreached points along vertex 2, and you need to return to vertex 1 at this time.

Continuing to try to access other vertices with vertex 1, we come to point 3. And so on, we finally arrived at point 5. At this point, all the vertices have passed, and the traversal is over.

The main idea of depth-first search is:

First, take an unaccessed vertex as the starting vertex, and walk along the edge of the current vertex to the unvisited vertex

When there are no unvisited vertices, go back to the previous vertex and continue to explore other vertices until all the vertices have been accessed.

Obviously, the depth-first search is traversing along one branch of the graph to the end, then backtracking, and then traversing the same path along the other until all the vertices have been accessed.

Code implementation

Row I and column j in the two-dimensional array above indicates whether vertex I to vertex j has edges.

1 means there are edges, x means there are no edges, and 0 means that the vertices come to themselves.

We call this method the adjacency matrix storage method of graphs.

A careful friend may find that this picture is all 0 along the diagonal, because the above graph is undirected.

The so-called undirected graph means that the edges of the graph have no direction. For example, side 1-5 means that vertex 1 can go to vertex 5, and vertex 5 can go to vertex 1.

The next step is to figure out how to traverse with depth-first search:

Void dfs (int cur) / / cur is the current vertex number {printf ("% d", cur); sum++; / / every point visited is sum++ if (sum = = n) return; / / all vertices have visited for (I = 1; I

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.