[Open volume data structure] traversal of graph, wide search and deep search (basic)

Hits: 0

Table of contents

traversal of graph

Breadth-first search

code demo

depth-first search

code demo

[traversal] of graph[]

Q: What is traversal of graph

A: The traversal of the graph refers to starting from a vertex of the graph and visiting all the nodes in the graph along the edges of the graph in a certain search method once and only once.

Because any vertex of the graph may be adjacent to the rest of the vertices, after visiting a vertex, the search may follow a certain path and return to the point. In order to avoid the same vertex being visited multiple times, in the process of traversing the graph, each visited vertex must be recorded. For this purpose, an auxiliary array visited[] can be set to mark whether the vertex has been visited. There are two main types of graph traversal algorithms: breadth-first search and depth-first search.

Breadth-first search

Q: What is breadth-first search?

A: Breadth-first search (BFS) is similar to the level-order traversal algorithm of a binary tree. The basic idea is: first visit the starting vertex v, then start from v, visit each unvisited adjacent vertex w1, w2, … wi of v in turn, and then visit w1, w2, … wi in turn, All unvisited adjacent vertices of . Starting from these visited vertices, visit all their unvisited adjacent vertices until all vertices in the graph have been visited.

If there are still unvisited vertices in the graph at this time, another unvisited vertex in the graph is selected as the starting point, and the above process is repeated until all vertices in the graph are visited.

Breadth-first search is a hierarchical search process . Each step forward may visit a vertex without going back, so it is not a recursive algorithm. In order to achieve layer-by-layer access, the algorithm must use an auxiliary queue to remember the vertices of the next layer of the vertex being accessed.

We perform a breadth-first search on this graph. Assuming that the visit starts from the a node, a is enqueued first. At this time, the queue is not empty, and the head element a of the queue is taken out. Since b and c are adjacent to a and have not been visited, they visit b and c in turn, and enter b and c into the queue in turn. If the queue is not empty, take out the head element b, visit the vertices d and e that are adjacent to b and not visited in turn, and add d and e to the queue ( note: a and b are also adjacent, but a has set the access flag, so it is not visit again). At this time, the queue is not empty, take out the head element c, visit the vertices f, g that are adjacent to c but have not been visited, and put f and g into the queue. At this time, the head element d is taken out, but the vertices adjacent to d and not visited are empty, so no operation is performed. Continue to take out the head element e, and put h into the queue… After the head element h is finally taken out, the queue is empty, so the loop automatically jumps out. The traversal result is abcdefgh.


code demo


bool visited[MAX_VERTEX_NUM]; //Visit the marker array
void BFSTraverse(Graph G){ //Breadth-first traversal of graph G
for (i= 0 ;i<G.vexnum;++i)
visited[i]= FALSE ; //Visit the marker array to initialize
InitQueue(Q); //Initialize the auxiliary queue Q
for (i= 0 ;i<G.vexnum;++i) //Start traversing from vertex 0
if ( !visited[i]) //call BFS once for each connected component
BFS(G,i) ; //v; not visited, start from v: BFS?
)
void BFS(Graph G, int v){ //Starting from vertex v, breadth-first traverse graph G
visit(v); //Visit the initial vertex v
visited[v]= TRUE ; //Mark v as visited
Enqueue( Q,v); //Vertex v into queue Q
while (!isEmpty(Q)){
DeQueue(Q,v); //Vertex v out of the queue
for (w=FirstNeighbor(G,v);w>= 0 ;w=NextNeighbor(G,v))
{ //Detect all adjacent points of v
if (!visited[w]){ //w is the unvisited adjacent vertices of v
visit(w); //visit the vertex w
visited[w]= TRUE ; //do w to w Visited mark
EnQueue(Q, w); // vertex w into the queue
}
}
}

depth-first search

Q: What is depth-first search

A: Depth-first search is similar to pre-order traversal of a tree. As its name implies, the search strategy followed by this search algorithm is to search a graph as “deep” as possible . Its basic idea is as follows: First visit a certain starting vertex v in the graph, then start from v, visit any vertex w1​ that is adjacent to v and not visited, and then visit any vertex that is adjacent to w1 ​and not visited … repeat the above process. When it is no longer possible to continue to visit downwards, return to the most recently visited vertices in turn. If it has adjacent vertices that have not been visited, continue the above search process from this point until all vertices in the graph have been visited.

We perform a depth-first search on this graph. The result of its depth-first traversal is: abdehcfg


code demo


bool visited[MAX_VERTEX_NUM]; //Visit the marker array
//Starting from the vertex, the depth-first traversal of the graph G
void DFS (Graph G, int v) {
int w;
visit(v); //Visit the vertex
visited[v] = TRUE; //Set the visited mark
//FirstNeighbor(G,v): Find the first adjacent point of the vertex v in the graph G, if there is, return the vertex number , otherwise return -1.
//NextNeighbor(G,v,w): Assuming that vertex w in graph G is an adjacent point of vertex v, return vertex v except w
for (w = FirstNeighbor(G, v); w>= 0 ; w=NextNeighor (G, v, w)){
if (!visited[w]){ //w is the unvisited adjacent vertex of u
DFS(G, w);
}
}
}
// Depth-first traversal of the graph
void DFSTraverse (MGraph G) {
int v;
for (v= 0 ; v<G.vexnum; ++v){
visited[v] = FALSE; //Initialize visited tag data
}
for (v= 0 ; v<G.vexnum; ++v){ //traverse from v=0
if (!visited[v]){
DFS(G, v);
}
}
}

You may also like...

Leave a Reply

Your email address will not be published.