C++

C++ – Tree and graph traversal

_Redstone_c_

BFS – breadth-first traversal

A search algorithm implemented using queues. To put it simply, the search process is similar to "throwing a stone into a lake causes ripples." The image is as follows:

In general, the nodes closest to the root node are traversed first, layer by layer.

Program ideas

The function passes in the root node of the tree/graph that needs to be traversed, then puts the root node into the queue and starts the loop operation. As long as the queue is not empty, it takes the head of the queue and puts the point connected to the head element into the queue.

It should be noted that loops may appear in the graph and may fall into an infinite loop, so an array must be defined to record whether the node has been visited.

Implementation method – storage method is point-to-point

Breadth-first traversal, the parameter v is the starting point of the traversal, that is, root
Create a linked list iterator to access the points connected to the points stored in the linked list
Set the currently visited node to one that has already been visited to prevent repeated visits in the future
Create queue
Put the starting point into the queue
If the queue becomes empty during the operation, the traversal has completed
v represents the node of the current operation, which is reset to the head of the team here.
The head of the team has been recorded by v, so it can be thrown away directly.
Use an iterator to access all points connected to v
Determine whether the current point has been visited
Put the starting point into the queue
Set the currently visited node to one that has already been visited to prevent repeated visits in the future.

PS: One-to-one correspondence with the program below

Program example – storage method is point-to-point

bool visited[MAXN] = {};
vector< list<int> > graph; 
void bfs(int v) {
    list<int>::iterator it; 
    visited[v] = true;
    /************Do something************/
    printf("%d ", v);
    /************************************/
    queue<int> q;
    q.push(v);
    while(!q.empty()) {
        v = q.front();
        q.pop();
        for(it = graph[v].begin(); it != graph[v].end(); it++)
            if (!visited[*it]) {
                /************Do something************/
                printf("%d ", *it);
                /************************************/
                q.push(*it);
                visited[*it] = true;
            }
    } 
}

DFS – depth first traversal

It is a search algorithm implemented using recursion. To put it simply, the search process is similar to "don't hit the wall and don't look back". The image is as follows:

Implementation method – storage method is point-to-point

Depth-first traversal, parameter v is the starting point of traversal, that is, root
Create a linked list iterator to access the points connected to the points stored in the linked list
Set the currently visited node to one that has already been visited to prevent repeated visits in the future
Use an iterator to access all points connected to v
Determine whether the current point has been visited
start recursion

PS: One-to-one correspondence with the program below

Program example – storage method is point-to-point

bool visited[MAXN] = {};
vector< list<int> > graph; 
void dfs(int v) {
    list<int>::iterator it;
    visited[v] = true;
    /************Do something************/
    printf("%d ", v);
    /************************************/
    for(it = graph[v].begin(); it != graph[v].end(); it++)<>
        if (!visited[*it])
            dfs(*it);
}

Post Reply