Depth and breadth first traversal of trees and graphs

Article directory

DFS
- CODE
- Analysis of ideas
BFS
- CODE
- Analysis of ideas
Summarize
- Tree and graph storage
- - Store template CODE
- DFS
- - Deep search template CODE
  - The role of DFS
  - - Find the template CODE of the node
- BFS
- - BFS level traversal to find the shortest path CODE

Introduce the depth and breadth traversal of trees and graphs. Since trees are acyclic graphs, they are universal. Let’s look at two questions first.

DFS

Board question: Click here.

CODE

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;
int n, a, b;
int e[M], ne[M], h[N], idx;
bool st[N];
int ans = N;

void add(int a, int b){<!-- -->
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx + + ;
}

int dfs(int u){<!-- -->
    st[u] = true;
    
    int size = 0, sum = 0;
    for(int i = h[u]; i != -1; i = ne[i]){<!-- -->
        int j = e[i];
        if(st[j]) continue;
        
        int s = dfs(j);
        size = max(size, s);
        sum + = s;
    }
    
    size = max(size, n - sum - 1);
    ans = min(ans, size);
    
    return sum + 1;
}

int main()
{<!-- -->
    memset(h, -1, sizeof h);
    
    cin >> n;
    for (int i = 0; i < n - 1; i + + ){<!-- -->
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    dfs(1);
    
    cout << ans << endl;
    
}

Analysis of ideas

main() function:

Read
n

?

1

n-1

n?1 edges, and then perform a deep search on the first point.

dfs() function:

Preparation work: We need a tag array st[] to detect whether the node has been traversed, a size variable to store the number of nodes contained in the maximum connectivity, and a The sum variable is used to accumulate the number of nodes and return it as the return value.
Starting from the parameter u (node number) given by dfs(), a path goes to black, traversing all nodes with u as the head node Again, it’s very similar here
B

F

S

BFS

BFS, but with

B

F

S

BFS

The difference with BFS is that when encountering a node that has not been traversed, the node is

D

F

S

DFS

DFS.
Deep search finds how many nodes there are in the subtree with this child node as the root node. This is the number of nodes contained in the remaining connected component when we eliminate the u node. Since u may have more than one subtree, so we use
f

o

r

for

The for loop traverses all subtrees, takes the maximum value of all return values size, and obtains the largest connected component in all subtrees of u, and accumulates all return values to obtain all subtrees The number of all nodes contained sum.
Since except for the subtree under node u, the tree before u is also a connected component, so in the end you need to compare this, take the maximum value, and then the answer variable < Take the minimum value between code>ans and size.
at last
D

F

S

DFS

DFS don’t forget to return the number of nodes, yes

s

u

m

+

1

sum+1

sum + 1 because we also need to bring the u node.

The above connected components

BFS

Board question: Click here.

CODE

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = N;
int n, m;
int e[M], ne[M], h[N], idx;
queue<int> q;
int d[N];

void add(int a, int b){<!-- -->
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx + + ;
}

int bfs(){<!-- -->
    q.push(1);
    memset(d, -1, sizeof d);
    d[1] = 0;
    
    while(q.size()){<!-- -->
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i]){<!-- -->
            int j = e[i];
            if(d[j] == -1){<!-- -->
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    
    return d[n];
}

int main()
{<!-- -->
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i + + ){<!-- -->
        int a, b;
        scanf("%d%d", & amp;a, & amp;b);
        add(a, b);
    }
    
    cout << bfs() << endl;
}

Analysis of ideas

This is a side right.

The shortest path problem of 1, then you can use

BFS

BFS to solve.

main() function:

Read in m edges and store them in the adjacency list.
output
B

F

S

BFS

Results of BFS.

bfs() function:

Preparation work: Use queue q to store nodes, distance record array d[] (needs initialization), mark array st[] (not available here) The array is marked because if the value of the distance record array d[] has not been modified, it means that it has not been traversed).
As long as the queue is not empty, keep traversing. First pop up the head of the queue t, traverse all the next-level nodes of t, if they have not been traversed, push them into the queue, and update d[] The value of is based on t
+

1

+ 1

+1.
finally return
n

n

Example record of n node d[n].

Summary

Storage of trees and graphs

We generally use an adjacency matrix to store a directed graph, which is a row of linked lists. The head node of each linked list is a node, and this node points to each node in the subsequent chain. If it is an undirected graph, then we need to save it twice, namely the directed edge (a, b) and the directed edge (b, a).

Storage template CODE

const int N = XXXX, M = N;
int e[M], ne[M], h[N], idx; // There are m edges, and e[] stores all the edges following the head node, so there are m.
// In the same way as ne[], h[] stores the head node, so it is the number of nodes.
void add(int a, int b){<!-- -->
e[idx] = b;
ne[idx] = h[a];
h[a] = idx + + ;
}
int main(){<!-- -->
cin >> n >> m;
memset(h, -1, sizeof h); // Don’t forget to initialize the head node array
for(int i = 0; i < m; + + i){<!-- --> // Read m edges
int a, b;
scnaf("%d%d", & amp;a, & amp;b);
add(a, b), add(b, a);
}
return 0;
}

DFS

DFS requires a tag array st[], which is consistent with

BFS

BFS is the same, but the ideas are different. In

DFS

In DFS, backtracking is performed when encountering a node that has been traversed, preventing over-recording of the number of nodes and preventing infinite loops (cyclic graphs);

BFS

BFS is to protect the value of the d[] array, that is, the value of the shortest path, because the number of steps traversed first must be the shortest, and the number of steps traversed later must be more, preventing steps The number has been changed, so when the solution is encountered for the first time, it is locked and subsequent operations are prohibited.

Shensou template CODE

int st[N];

int dfs(int u){<!-- --> // Start operating this node
st[u] = true; // mark as traversed
for(int i = h[u]; i != -1; i = ne[i]){<!-- --> // Traverse the numbers of all nodes pointed to by this node!
int j = e[i]; // Get the node corresponding to the number
if(!st[j]){<!-- --> // If you have not been there
dfs(j); // Perform a recursive deep search on this node
}
}
return xxxxx;
}

int main(){<!-- -->
//Read the data and store the data into the adjacency matrix.
memset(h, -1,sizeof h) // Don’t forget to initialize the adjacency table header to a null pointer (-1)
\t
int ans = dfs(1);

return 0;
}

Now I have a new understanding of linked list storage!
e[i]: The node corresponding to the i number is stored. Note that it is node!
ne[i]: What is stored is the number of the next node of the node numbered i! ! !
h[i]: What is stored is the number of the head node! ! !

That’s why we see this sentence inside the loop:

int j = e[i];

Because what was obtained in the previous loop was the node corresponding number idx instead of the node itself, so we need to use e[i] to dereference to get the real value! ! !

Hey hey hey, Master Dao, I’m done!

The role of DFS

After the above questions, we can easily find that

DFS

One function of DFS:Return the number of nodes of the tree (graph)!
Each recursion returns the number of subtree nodes, and finally the number of nodes in the entire structure is obtained.

Find the template CODE of the node

int dfs(int u){<!-- -->
st[u] = true;
int sum = 0;
for(int i = h[u]; i != -1; i = ne[i]){<!-- -->
int j = e[i];
if(!st[j]){<!-- -->
sum + = dfs(j);
}
}
return sum + 1;
}

Pay attention to

DFS

DFS declares the sum variable internally, not outside (global variable).
Because it adds up outside. When I first started processing the j node, I didn’t know how many child nodes you had, so I set it to

0, get the number of nodes of a subtree through recursion, and then for loops to accumulate all subtrees to get the number of all child nodes. When placed globally, there will be a value at the beginning, but this is not what it should be, it should be

0, and finally get the answer through processing.

Although it seems useless, because the questions usually directly give you the number of nodes, but at least summarize it, otherwise I will have nothing to write, so it is really useless.

BFS

BFS can have edge weights as

Find the shortest path in case 1.
Use queues to implement first-in, first-out, and exit one layer before exiting the next layer. The function of the d[] array is to mark whether the node has been traversed and record the minimum path value from the root node to this node.

BFS level traversal to find the shortest path CODE

void bfs(){<!-- -->
queue<int> q;
q.push(1);
memset(d, -1, sizeof d); // Don't forget to initialize the tag array! ! !
d[1] = 0;
\t
while(q.size()){<!-- --> // Keep dequeuing as long as the queue is not empty
int t = q.front(); // Pop up the queue head
q.pop();
\t\t
for(int i = h[t]; i != -1; i = ne[i]){<!-- --> // Traverse child nodes
int j = e[i]; // Get the node corresponding to the number
if(d[j] == -1){<!-- --> // Not visited yet
d[j] = d[t] + 1; // Mark and record the value
q.push(j); // Push to stack
}
}
}
}