Traversal algorithm on the graph
Broadness-first search BFS
concept
Breadth-First SearchIt is a graph traversal algorithm used to access nodes layer by layer in graph or tree. It starts from the source node (starting node), first accesses all directly adjacent nodes of the source node, and then accesses nodes far away from the source node in turn until it traverses the complete graph or reaches the target node.
BFS ensures that nodes are accessed by the shortest path through queue expansion layer by layer, and ensures that the shortest path from the source node to the target node is found in the unauthorized graph. It is suitable for finding the shortest path, connecting components, and solving problems such as hierarchical traversal of the graph.
Time complexity:\(O(V+E)\),in\(V\)is the number of nodes (number of vertices) in the graph,\(E\)It is the number of edges in the graph
Implementation method
BFS adoptionQueueto ensure layer by layer access of nodes. Whenever a node is accessed, all its unvisited adjoining nodes are queued to ensure that the next nodes access in order of the number of layers of the starting node at their distance.
//pseudocode
BFS(graph, start):
Add the starting node start to queue and mark it as accessed
While queue non-empty:
Current node node = popped out of queue
Access node node
traverse all adjacent nodes of node neighbor:
If neighbor has not been visited:
Tag neighbor as visited
Add neighbor to queue//C++ code (adjacent table, maintaining distance array and predecessor node array)
//Q queue, used to store nodes to be accessed
//vis access tag array to record whether each node has been accessed
//d Distance array, record the shortest distance of each node from the starting node
//p array of predecessor nodes, record the predecessor nodes of each node, help restore the path
//head[u] The head node of the adjacency table of node u
//e[i].to target node of edge i
//e[i].nxt Pointer to the next edge of the edge i, used to traverse the adjacency table
void bfs(int u) {
While (!()) ();//Clear the queue
(u);
vis[u] = 1;
d[u] = 0;
p[u] = -1;
while (!()) {
u = ();
();
for (int i = head[u]; i; i = e[i].nxt) {
if (!vis[e[i].to]) {
(e[i].to);
vis[e[i].to] = 1;
d[e[i].to] = d[u] + 1;
p[e[i].to] = u;
}
}
}
}
void restore(int x) {
vector<int> res;
for (int v = x; v != -1; v = p[v]) res.push_back(v);
reverse((), ());
for (int i = 0; i < (); ++i) printf("%d ", res[i]);
}Layer sequence traversal
Example Leetcode 102 Layer sequence traversal of binary trees
Give you the root node of the binary treeroot, return the value of its nodeLayer sequence traversal(That is, access all nodes from left to right layer by layer)
Sample input:
root = [3,9,20,null,null,15,7]
Sample output:
[[3],[9,20],[15,7]]
Key Code:
vector<vector<int>> levelOrder(TreeNode* root) {
vector <vector <int>> ans;
if (!root) return ans;
queue <TreeNode*> q;
(root);
while (!()) {
int size = ();//Number of elements in the queue
ans.push_back(vector <int> ());
for (int i = 1; i <= size; ++i) {
auto node = (); ();
().push_back(node->val);
if (node->left) (node->left);
if (node->right) (node->right);
}
}
return ans;
}Shortest path
Create an array or dictionary to record the shortest path (i.e. distance) of each node.Initially, set the distance of the starting point to0, other nodes are set to -1Indicates that it has not been accessed. When searching for breadth first, for each neighbor node, if it has not been accessed, its shortest path is updated to the shortest path of the current node.+1and add the neighbor node to the queue
Example Luogu P1443 Horse traversal
There is one\(n \times m\)chess board, at a certain point\((x, y)\)There is a horse on it, and you are asked to calculate how many steps it takes to reach any point on the board.
enter:There are only one line of four integers, respectively\(n, m, x, y\)
Output:one\(n \times m\)The matrix means that the horse needs to take at least a few steps to reach a certain point (if it cannot be reached, it will be output\(-1\)）
Sample input:
3 3 1 1
Sample output:
0 3 2
3 -1 1
2 1 4
Key Code:
int vis[N][N],f[N][N];
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={2,1,-1,-2,2,1,-1,-2};//8 directions
f[x][y]=0;//Record steps
(make_pair(x,y));
vis[x][y]=true;
While(!())
{
int xx=().first,yy=().second;
();
for(int i=0;i<8;i++)
{
int u=xx+dx[i],v=yy+dy[i];
if(u<1||u>n||v<1||v>m||vis[u][v])continue;
vis[u][v]=true;(make_pair(u,v));
f[u][v]=f[xx][yy]+1;
}
}Luogu B3625 Labyrinth Way Search
The maze can be regarded as one\(n\times m\)Matrix, each position is either a vacant land or a wall. The Doctor was originally located\((1, 1)\)The location can only be from an open space to an open space above, down, left and right. Ask if you can go to the\((n, m)\)Location
enter:The first line, two positive integers\(n,m\). Next\(n\)Yes, enter this maze. Enter a length of each line\(m\)string,#Indicates a wall,.Indicates empty land
Output:Only one line, one string. If the Doctor can go\((n, m)\), then outputYes; otherwise outputNo
Sample input:
3 5
.##.#
.#...
...#.
Sample output:
Yes
Luogu P1135 Strange elevator
Elevators can be cut off on every floor of the building, and\(i\)Floor (\(1 \le i \le N\)There is a number on )\(K_i\)（\(0 \le K_i \le N\)). There are only four buttons in the elevator: on, off, up, down. The number of upper and lower layers is equal to the number on the current floor. Of course, if the requirements cannot be met, the corresponding button will fail. For example:\(3, 3, 1, 2, 5\)Represents\(K_i\)（\(K_1=3\)，\(K_2=3\),……),from\(1\)The building begins. exist\(1\)Press "up" to get there\(4\)The building, pressing "down" does not work, because there is no\(-2\)building. Then, from\(A\)Arrival\(B\)How many times should I press the button at least?
enter:The first behavior is three positive integers separated by spaces, representing\(N, A, B\)（\(1 \le N \le 200\)，\(1 \le A, B \le N\)). Second behavior\(N\)A non-negative integer separated by spaces, representing\(K_i\)
Output:One line, that is, the minimum number of key presses. If it cannot be reached, the output is-1
Sample input:
5 1 5
3 3 1 2 5
Sample output:
3
Connecting component issues
Connected components in undirected graphs: refers to the largest subset in which all nodes in the graph are connected to each other. For an undirected graph, if you start from one node and access all other nodes through edges in the graph, then these nodes form a connected component. If there are paths connected between nodes within a subset of the graph, the subset is a connected component
Example Leetcode 200 Number of islands
Give you a'1'(Land) and'0'A two-dimensional grid composed of (water), please calculate the number of islands in the grid
Islands are always surrounded by water, and each island can only be formed by adjacent land connections in horizontal and/or vertical directions.
Additionally, you can assume that all four sides of the grid are surrounded by water
Sample input:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Sample output:
3
Key Code:
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; //Four directions
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que;
({x, y});
visited[x][y] = true;
while(!()) {
pair<int ,int> cur = (); ();
int curx = ;
int cury = ;
for (int i = 0; i < 4; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
if (nextx < 0 || nextx >= () || nexty < 0 || nexty >= grid[0].size()) continue;
if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
({nextx, nexty});
visited[nextx][nexty] = true;
}
}
}
}Depth-first search DFS
concept
Depth-First SearchIt is a traversal algorithm for graphs or trees. Its basic idea is: start from a starting node, traverse downward along a path until it cannot continue, then go back to the previous node and continue to explore other unvisited nodes until all nodes have been accessed.
The core idea of DFS is to try to go deeper into each branch, explore the path that there is no more path, and then fall back to the previous layer node for searching for other paths.
Time complexity:\(O(V+E)\)
Implementation method
recursion
The most common method to implement DFS can intuitively use the function call stack to automatically trace backtrack. Recursively access all unreached neighbors of the current node; each recursive call will enter the next node until it is unreachable, and then go back to the previous node to continue to access other unreached neighbors.
int n,path[N];
bool st[N + 1]; // Mark array
void dfs(int u) // Arrange the number of u-th
{
if (u == n)
{
for (int i = 0; i < n; i++)
printf("%5d", path[i]);
printf("\n");
return;
}
for (int i = 1; i <= n; i++)
{
if (!st[i])
{
path[u] = i; // Put i in the current arrangement position
st[i] = true; // Mark i has been used
dfs(u + 1); // Recursively construct the next position of the arrangement
st[i] = false; // Backtrace Uncheck, cancel the selection, cancel the mark of i
}
}
}Stack
Explicitly use the stack to simulate recursive processes. Take out the node from the top of the stack and access it, push all unvisited neighbors of the current node into the stack; when all neighbors are accessed, they are released and traced back to the previous node. Explicit stack avoids the stack overflow problem caused by recursion and is suitable for scenarios that require large depth traversal.
vector<vector<int>> adj; //Address table
vector<bool> vis; //Record whether the node has been traversed or not
void dfs(int s) {
stack<int> st;
(s);
vis[s] = true;
while (!()) {
int u = ();
();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true; //Make sure there are no duplicate elements in the stack
(v);
}
}
}
}Backtracking problem
When recursing to a certain layer, if you find that the current state does not meet the conditions, or a solution has been found, the current operation is cancelled, return to the previous state, and continue to try other options
Example Acwing 843 N Queen's Problem
Will\(n\)A queen placed\(n \times n\)chess board, so that the queens cannot attack each other, that is, neither of the two queens can be in the same row, the same column or the same diagonal line. Now given the integer n, please output all the chess piece arrangement methods that meet the conditions
enter:A total of one row, containing integers\(n\)
Output:Each solution accounts for\(n\)rows, each row outputs a length of\(n\)The string of , used to represent the complete board status. in "\(.\)" means that the square state of a certain position is empty."\(Q\)” means that there is a queen on the grid in a certain position. After each plan output is completed, an empty line is output.
Enter a sample:
4
Output sample:
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
Key Code:
int n;
char g[N][N];// Used to store paths
bool col[N], dg[N], udg[N];//col column, dg diagonal, udg opposition angle, used to determine whether the position is feasible
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
return;
}
int x = u;
for (int y = 0; y < n; y ++ )
if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) {
col[y] = dg[y - x + n] = udg[y + x] = true;
g[x][y] = 'Q';
dfs(x + 1);
g[x][y] = '.';
col[y] = dg[y - x + n] = udg[y + x] = false;
}
}Luogu P1706 Full arrangement problem
Output natural numbers in dictionary order\(1\)arrive\(n\)All non-repetitive arrangements, i.e.\(n\)The full arrangement of the digits requires that no duplicate numbers are allowed in any sequence of generated digits
enter:An integer\(n\)
Output:Depend on\(1 \sim n\)All sequences of non-repetitive numbers are composed, one sequence per row. Each number is retained\(5\)Field width
Sample input:
3
Sample output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Strong connected components
On a directed graph\(G\)If two vertices are\(u\) ，\(v\)There is a one from\(u\)arrive\(v\)Directed path, and there is also a\(v\)arrive\(u\)The directed path is called two verticesStrong connection. If there is a directed graph\(G\)Each two vertices of\(G\)It's oneStrong connection diagram. The extremely powerful connected sub-graph of directed non-strong connected graph is calledStrong connected components
As shown in the picture above,\(\{1,2,3,5\}\)For a strong connected component, because the vertex\(1,2,3,5\)Two-two can reach
Tarjan Algorithm
- DFS is performed starting from each unvisited node. During the DFS process, record the discovery time of the node
DFN, update the earliest reachable ancestor nodeLOW - When a node
LOWThe value is equal to its discovery timeDFNWhen, it means that the node starting from the node (including itself) forms a strong connected component. At this point, all nodes pop up from the stack and mark them as the same strong connected component - Stack
stackIn the algorithm, it is used to save nodes in the current DFS path until a strong connected component is identified, and then pop these nodes from the stack.
//vis[] is used to mark whether the node is in the stack and avoid repeated processing
//stack[] stack, used to store nodes on the current DFS access path
//LOW[] timestamp of the earliest node that node pos can return to
//DFN[] Record the DFS discovery time of the node
//dfs_num DFS counter, used to mark each node with a unique access time stamp
//size[] Record the size of each strongly connected component
//dye[] marks which strong connectivity component each node belongs to
//CN Number of the current strongly connected component
//pre[] and E[] are used to store edges and adjacency tables of graphs, and pre[pos] stores the out edges of pos nodes
void tarjan(int pos){
vis[stack[++index]=pos]=1;//Put on the stack and mark
LOW[pos]=DFN[pos]=++dfs_num;
for(int i=pre[pos];i;i=E[i].next){
if(!DFN[E[i].to]){
tarjan(E[i].to);
LOW[pos]=min(LOW[pos],LOW[E[i].to]);
}
else if(vis[E[i].to]) LOW[pos]=min(LOW[pos],DFN[E[i].to]);
}
if(LOW[pos]==DFN[pos]){
vis[pos]=0;
size[dye[pos]=++CN]++;//Dyeing and recording the size of strongly connected components
while(pos!=stack[index]){
vis[stack[index]]=0;
size[CN]++;//Record size
dye[stack[index--]]=CN;//Pull the stack and dye it
}
index--;
}
}Example Luogu P2341 Popular cow
The cow that is loved by all cows is a celebrity cow. All cows are narcissists, and every cow always likes his own. The "like" between cows can be passed on-if\(A\)like\(B\)，\(B\)like\(C\),So\(A\)Like it too\(C\). There are all in the bullpen\(N\)A cow, given the admiration relationship between some cows, please calculate how many cows can be a celebrity.
enter:The first line is two integers separated by spaces\(N\)and\(M\);Next\(M\)Lines are two integers separated by spaces per line\(A\)and\(B\),express\(A\)like\(B\)
Output:A single integer in a row indicates the number of star cows
Sample input:
3 3
1 2
2 1
2 3
Sample output:
1
Key Code:
void tarjan(int u)
{
low[u]=dfn[u]=++dfn_sum;
stack[top++]=u;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dfn(v))
low[u]=min(low[u],dfn[v]);
else
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
}
if(low[u]==dfn[u])
{
int now=stack[--top];s_sum++;
s[u]+=s_sum;
while(now!=u)
{
s[now]=s_num;
now=s[--top];
}
}
}
Topological sorting
For each directed edge in the graph\(u \to v\), in the sorting result, vertex\(u\)Must be at the top\(v\)Front
Only suitable for directed acyclic graphs, also called topological graphs
The graph topology sequence is\(ABDC\)or\(ADBC\)
Kahn Algorithm
Entry:How many edges point to the node, points with an entry degree of 0 can be ranked first
Output:How many edges does this node point to
First calculate the incoming degree of each node, select all nodes with an incoming degree of 0 as the initial node, and add them to the result list. Remove these nodes and their outgoing edges and update the incoming degrees of adjacent nodes. If the incoming degree of adjacent nodes becomes 0, continue to join the queue until all nodes are processed
//pseudocode
queue <- All points with an entry degree of 0
While queue
{
t <- Team leader
Enumerate all outgoing edges of t->j
Delete t->j,d[j]--;
}Example Luogu B3644 Topological sorting
There is someone whose family is very large and the relationship between generations is very chaotic. Please help me sort out this relationship. Give information about each person's descendants. Output a sequence so that each person's descendants are listed below that person
enter:The\(1\)Line an integer\(N\), indicating the number of people in the family. Next\(N\)OK,\(i\)Line description\(i\)Individual descendants number\(a_{i,j}\),express\(a_{i,j}\)yes\(i\)offspring. The last line is\(0\)Indicates that the description is completed
Output:Output a sequence so that each person's descendants are listed later than that person. If there are multiple different sequences, you can output any one
Sample input:
5
0
4 5 1 0
1 0
5 3 0
3 0
Sample output:
2 4 5 3 1
Key Code:
queue <int> Q;
void toposort() {
for(int i = 1; i <= n; i++) {
if(deg[i] == 0) {
printf("%d ", i);
(i);
}
}
while(()) {
int x = (); ();
for(int i = Head[x]; i; i = Next[i]) {
deg[to[i]]--;
if(deg[to[i]] == 0) {
printf("%d ", to[i]);
(to[i]);
}
}
}
}
Ring detection
ringRefers to the path that can return to the vertex after traversing along the directed/undirected edge of the graph in the figure.
Topological sortingSuitable for directed acyclic graphs. If a directed graph can be topologically sorted, it means that the graph has no rings.If topological sorting is not possible, it means that there is a ring in the figure
Example Leetcode 207 Course Schedule
You must take an elective this semesternumCoursesCourses
Some pre-study courses are required before taking certain courses. Pre-study courses by arrayprerequisitesGiven, whereprerequisites[i] = [ai, bi], means if you want to study the courseaiYou must first learn the coursebi
Please determine whether it is possible to complete all courses? If possible, returntrue; Otherwise, returnfalse
Sample input:
numCourses = 2, prerequisites = [[1,0],[0,1]]
Sample output:
false
Key Code:
bool toposort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
return tt == n - 1;
}