# BFS of AK F.*ing leetcode program

Welcome to pay attention to more wonderful
Pay attention to me, learn common algorithms and data structure, one problem with multiple solutions, dimension reduction.

# 1, Introduction

Breadth first search (BFS) is a graph traversal method, similar to the hierarchical tree traversal.

Graph applications mainly include: 1) the shortest path calculation of 2 points in an unweighted graph; 2) the hierarchical traversal of a graph or tree; 3) some calculations related to connected blocks of a graph, such as judging whether 2 points are connected and how many connected blocks there are.

Extensive search is also suitable for implicit graphs. Implicit graph concept: https://baike.baidu.com/item/%E9%9A%90%E5%BC%8F%E5%9B%BE/7266624?fr=aladdin

The calculation of state reachability and the cost of transition between two states can also be solved by extensive search.

The principle of the algorithm is to traverse all the nodes in the implicit graph hierarchically from the initial state, and all the traversed nodes are both reachable state nodes (the level is the transfer cost).

For example, in the two-dimensional matrix maze, finding the number of steps from a lattice to the exit (if you can walk out) is an application of implicit graph search.

Since extensive search is to traverse all the nodes in the graph, the algorithm is a brute force algorithm. Violent algorithms often have a fixed code framework and problem-solving routines.

The core of extensive search algorithm is to estimate the number of states (nodes in the graph) and the transition condition (the method from one state to another state).

If there are too many states, it is not suitable for extensive search. On the contrary, if the number of States is within a certain controllable range, then the wide search violence algorithm will be a very good choice.

Transfer condition is how to transfer from one node to another. For an ordinary graph, it is the relationship between edges. For an implicit graph, it is the rule of state transition (generally simulated operation). For example, in the above maze, a person's state is the current point (x, y), and the transition is going in four directions. Dir = [] {1,0}, {- 1,0}, {0,1}, {0, - 1}, the transition state is (x+dir[i], y+dir[i])

The complexity of ergodic graph is O(v+e), the number of nodes and edges.

Extensive search is very practical in algorithm problems. Because it traverses all States, the exploration of the answer is very complete (very secure). Once it is analyzed that the state quantity is controllable, it is directly on. It is one of the algorithms that I give priority to in solving problems.

# 2, Conditions and solving steps

Conditions:

• A graph or an implicit graph that defines states
• The number of reachable states is less than one million
• There is a clear method of state transition

Problem solving steps

• Defining data
1. Define state representation
2. Define state transition methods
3. Defining boundary judgment method
• Specific operation

step 1 initialization, the initialization node will be added to the queue q, representing the first layer

step 2 judges whether the queue is empty or not, and if yes, it turns to step 5

Step 3 traverses the current layer node

1. Create a new state,

2. Judge whether the new state is legal (whether it is bounded or reachable)

3. Judge whether the new state has been added to the queue.

4. Join the queue

step 4 to step 2

End of step 5

# 3, Function

Chart application

1. Calculation of 2-point shortest path in weighted graph
2. Hierarchical traversal of graph or tree
3. Graph connected block related calculation, such as judging whether 2 points are connected, there are several connected blocks.

Application of implicit graph

1. Ask whether the target state can be reached from the initial state.
2. Ask the minimum cost from the initial state to the target state.

# 4, Code framework

## BFS hierarchical traversal algorithm

```// Hierarchical traversal algorithm
func BFS(start State) [][]State {
vis // It indicates whether a state has been accessed. It needs to be judged in the case of ring graph, but not in the case of acyclic graph
queue.Enqueue(start)
vis[start]<-true
ans [][]State
while(!queue.Empty()) { // Check whether there are elements in the current layer
l <- queue.Len() // The first 1 elements in the current queue are all elements of the current layer. First record L, and then take l times in a loop
curLevel []State // Current layer traversal result
for i <- 0 to l-1 {
front <-  queue.Dequeu()
curLevel = append(curLevel, front) //Current layer result collection
for child : front.Children() { // Generate transition state
if vis[child] {continue} // It's been traversed
if !Region(child) {continue} // wrongful
queue.Enqueue(child)
}
}

// After traversing the first layer, add it to ans
ans = append(ans, curLevel)
}

return ans
}
```

## BFS algorithm for 2-point shortest path

```// BFS algorithm for 2-point shortest path
// Unable to reach return - 1
func BFS(start State, target State) int {
vis // It indicates whether a state has been accessed. It needs to be judged in the case of ring graph, but not in the case of acyclic graph
queue.Enqueue(start)
step <- 0 // The initial step was 0
vis[start]<-true
while(!queue.Empty()) { // Check whether there are elements in the current layer
l <- queue.Len() // The first 1 elements in the current queue are all elements of the current layer. First record L, and then take l times in a loop
curLevel []State // Current layer traversal result
for i <- 0 to l-1 {
front <-  queue.Dequeu()
if front == target { // At the end of the current step, you will reach the destination and return the result directly
return step
}
for child : front.Children() { // Generate transition state
if vis[child] {continue} // It's been traversed
if !Region(child) {continue} // wrongful
queue.Enqueue(child)
}
}

// If you can't reach this step, the number of steps will be + 1
step <- step+1
}

return -1 //All the results can not find the end
}
```

## go to implement tree level traversal template

Queue in go language can be realized by slice feature.

```/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
ans := [][]int{}
if root==nil {
return ans
}
queue := []*TreeNode{root}
for len(queue)>0 { // Determine whether there are elements in the current queue
curLevel := []int{}
for i, l:=0, len(queue);i<l;i++ { //Take the first 1 element as the current layer element
front := queue // Get header
queue = queue[1:] // Remove header from queue
curLevel = append(curLevel, front.Val) // Add to current layer

// View child status
if front.Left!=nil {
queue = append(queue, front.Left)
}
if front.Right!=nil {
queue = append(queue, front.Right)
}
}

ans  = append(ans, curLevel)
}

return ans
}
```

# 5, A trial of the ox knife

## Exercise 1 level traversal application Sequence traversal of binary tree

### Main idea of the title

To give you a binary tree, please return the node value obtained by traversing it in sequence( That is, access all nodes from left to right layer by layer.

Example:
Binary tree: [3,9,20,null,null,15,7],

​ 3
/
9 20
​ /
15 7
Return the sequence traversal result:

[
,
[9,20],
[15,7]
]

### Topic analysis

Each layer is collected by layer traversal, and the results of the current layer are put into the overall results after the end of one layer.

### AC code

```/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
ans := [][]int{}
if root==nil {
return ans
}
queue := []*TreeNode{root}
for len(queue)>0 {
curLevel := []int{}
for i, l:=0, len(queue);i<l;i++ {
front := queue // Get header
queue = queue[1:] // Remove header from queue
curLevel = append(curLevel, front.Val) // Add to current layer

// View child status
if front.Left!=nil {
queue = append(queue, front.Left)
}
if front.Right!=nil {
queue = append(queue, front.Right)
}
}

ans  = append(ans, curLevel)
}

return ans
}
```

## Exercise 2 connected block application Number of islands

### Main idea of the title

Here is a two-dimensional grid composed of '1' (land) and '0' (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 links in the horizontal and / or vertical directions.

In addition, you can assume that all four sides of the mesh are surrounded by water.

Example 1:

Input: grid =[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:

Input: grid =[
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Tips:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
The value of grid[i][j] is' 0 'or' 1 '

### Topic analysis

Regarding a matrix as a graph, the number of islands required by the topic is to find how many connected blocks there are in the graph. We can use extensive search to find connected blocks.

The specific method is as follows: starting from each point (if it has been searched, it will be omitted, indicating that it is connected with the previous point), if it has not been searched, it will be a new island (number of islands + 1), and all the interlinked points will be searched.

### AC code

```func getInd(state []int) int {
return state*1000+state
}

func numIslands(grid [][]byte) int {
n, m := len(grid), len(grid)
vis := map[int]bool{} // Has the tag been searched
sum := 0 // Total Islands
dir := [][]int{{0,1},{0,-1},{-1,0},{1,0}} // Up, down, left and right
var bfs = func(start []int) int {// Search all the land composed of start, return 1 if there is land, otherwise return 0
if grid[start][start]=='0' {return 0} // Non land
if vis[getInd(start)] {return 0} //It's been searched
queue := [][]int{start}

for len(queue)>0 {
// There is no need to know the specific situation of a certain layer. As long as there is something in the queue, it will be taken out, and then the transition state will be added to the queue
front := queue
queue = queue[1:]

// state transition
for _, d:=range dir {
nx, ny := front+d, front+d // New state

// Start judging legitimacy
if nx<0 || nx>=n || ny<0 || ny>=m { // It's out of line
continue
}

if grid[nx][ny]=='0' { //Non land
continue
}

//Check to see if it has been traversed
newState := []int{nx, ny}
if vis[getInd(newState)]  {continue}
vis[getInd(newState)] = true// Mark traversed
queue = append(queue, newState)
}
}

return 1
}

for i, row := range grid {
for j:=range row {
sum += bfs([]int{i,j})
}
}

return sum
}
/*
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
[["0"]]
*/
```

## Exercise 3 shortest path application Word Chain

### Main idea of the title

The conversion sequence from beginWord to endWord in the dictionary wordList is a sequence formed according to the following specifications:

The first word in the sequence is beginWord.
The last word in the sequence is endWord.
Only one letter can be changed at a time.
The intermediate words in the conversion process must be words in the dictionary wordList.
Give you two words beginWord and endWord and a dictionary wordList to find the number of words in the shortest conversion sequence from beginWord to endWord. If there is no such conversion sequence, return 0.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5
Explanation: a shortest transformation sequence is "hit" - > "hot" - > "dot" - > "dog" - > "cog", which returns its len gt h of 5.
Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log"]
Output: 0
Explanation: endWord "cog" is not in the dictionary, so it cannot be converted.

Tips:

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord and wordList[i] are composed of lowercase English letters
beginWord != endWord
All strings in the wordList are different from each other

### Topic analysis

This is a typical implicit graph search topic.

Step is the current level, and the initial value is 1.

beginWord is the starting state and endWord is the target state. The state transition method is to change a letter in the word each time, ask how many times the state transition can reach the target state at least, and output 0 without solution.

Simple proof, why traverse to the target state in a certain layer, the answer is the current step

To the contrary, suppose endWord is found at level x, which means that the answer can't be < X. if there is, then endWord can be traversed before level X.

### Thinking and optimization

```/*
According to the shortest path template, the following search template is given
*/
func bfs(beginWord string, endWord string) int {
vis := map[string]bool{}
queue := []string{beginWord}
vis[beginWord]=true
step :=1 // According to the meaning of the question, the initial include oneself is 1
for len(queue)>0 {
for i,l:=0, len(queue);i<l;i++ {
front := queue
queue=queue[1:]
if front == endWord{ //We got the target.
return step
}

for _, child := range getChild(front) {
if vis[child]{continue}
vis[child]=true
queue=append(queue, child)
}
}
step++
}

return 0
}

/*
In the above code, getChild(word) is used to get all the strings that appear in the wordList by changing a letter. Obviously, for a fixed word, the result of getChild(word) is fixed, so it can be calculated at the beginning and stored in map links[word].
*/

for _, s1 := range wordList {
for _, s2 := range wordList {
// Judge whether s1 to s2 can be changed by one letter
}
}
}
/*
The complexity of the above code is 10*O(n^2), n = 5000, the overall complexity is 25 * 10 ^ 7, the complexity is too large.
The optimization is as follows.
*/

var  wordMap map[string]bool // Stores whether a word is in the wordList
for _, s1 := range wordList {
for i:=0;i<len(s1);i++ { //For each bit, replace it with a-z
for c:='a';c<='z';c++ {
// Check whether the new word newStr is in the wordMap
}
}
}
}
/*
The complexity of the above code is O(n) * 10 * 26, about 10 ^ 6, which is acceptable.
*/

```

### AC code

The starting word may not be in the worldlist, but also the child

```func getLinksV2(wordList []string) map[string][]string {
wordMap := map[string]bool{} // Stores whether a word is in the wordList
for _, s := range wordList {
wordMap[s] = true
}

for _, s := range wordList {
for i := 0; i < len(s); i++ { //For each bit, replace it with a-z
bs := []byte(s)
for c := 'a'; c <= 'z'; c++ {
bs[i] = byte(c)
if string(bs) == s {
continue
}
// Check whether the new word newStr is in the wordMap
if wordMap[string(bs)] {
}
}
}
}
}

/*
The complexity of the above code is O(n) * 10 * 26, about 10 ^ 6, which is acceptable.
*/
func ladderLength(beginWord string, endWord string, wordList []string) int {
links := getLinksV2(append(wordList, beginWord)) // The starting word may not be in the worldlist, but also the child
var bfs = func(beginWord string, endWord string) int {
vis := map[string]bool{}
queue := []string{beginWord}
vis[beginWord] = true
step := 1 // According to the meaning of the question, the initial include oneself is 1
for len(queue) > 0 {
for i, l := 0, len(queue); i < l; i++ {
front := queue
queue = queue[1:]
if front == endWord { //We got the target.
return step
}

for _, child := range links[front] {
if vis[child] {
continue
}
vis[child] = true
queue = append(queue, child)
}
}
step++
}

return 0
}

return bfs(beginWord, endWord)
}
```

# 6, Summary

1. Extensive search algorithm is a kind of violent algorithm, which is suitable for graph search problem with small state complete set.

2. Functions: graph applications mainly include: 1) calculation of the shortest path of 2 points in an unweighted graph; 2) hierarchical traversal of a graph or tree; 3) calculation related to connected blocks of a graph, such as judging whether 2 points are connected and how many connected blocks there are.

The calculation of state reachability and the cost of transition between two states can also be solved by extensive search.

3. The basic framework of problem solving is relatively fixed, and the key lies in the definition of state and the construction of state transition method.

The author's level is limited. I hope you can point out that I will try my best to improve it.

Now I carefully prepared several topics on popular websites (first AK F.*ing leetcode), and prepared some topics for you to practice and reference. F. * ing.

# 7, Actual combat training

## Code basic training questions

Just say that you don't practice the fake handgrip. After you've learned it, you should practice it. Use the example A quickly.

1. Hierarchical traversal application topic link https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
2. Connected block application topic link https://leetcode-cn.com/problems/number-of-islands/

## AK leetcode

leetcode related topics are in the following, take up arms and roll call one by one.

The above topics are too many, you can choose appropriately, and there are advanced topics below.

hdu

1. http://acm.hdu.edu.cn/showproblem.php?pid=1026
2. http://acm.hdu.edu.cn/showproblem.php?pid=1035
3. http://acm.hdu.edu.cn/showproblem.php?pid=1043
4. http://acm.hdu.edu.cn/showproblem.php?pid=1072
5. http://acm.hdu.edu.cn/showproblem.php?pid=1195
6. http://acm.hdu.edu.cn/showproblem.php?pid=1226
7. http://acm.hdu.edu.cn/showproblem.php?pid=1241
8. http://acm.hdu.edu.cn/showproblem.php?pid=1242
9. http://acm.hdu.edu.cn/showproblem.php?pid=1252
10. http://acm.hdu.edu.cn/showproblem.php?pid=1253
11. http://acm.hdu.edu.cn/showproblem.php?pid=1312
12. http://acm.hdu.edu.cn/showproblem.php?pid=1372
13. http://acm.hdu.edu.cn/showproblem.php?pid=1426
14. http://acm.hdu.edu.cn/showproblem.php?pid=1495
15. http://acm.hdu.edu.cn/showproblem.php?pid=1547
16. http://acm.hdu.edu.cn/showproblem.php?pid=1548
17. http://acm.hdu.edu.cn/showproblem.php?pid=1885
18. http://acm.hdu.edu.cn/showproblem.php?pid=2128
19. http://acm.hdu.edu.cn/showproblem.php?pid=2416
20. http://acm.hdu.edu.cn/showproblem.php?pid=2605
21. http://acm.hdu.edu.cn/showproblem.php?pid=2612
22. http://acm.hdu.edu.cn/showproblem.php?pid=2614
23. http://acm.hdu.edu.cn/showproblem.php?pid=2616
24. http://acm.hdu.edu.cn/showproblem.php?pid=2717
25. http://acm.hdu.edu.cn/showproblem.php?pid=2821
26. http://acm.hdu.edu.cn/showproblem.php?pid=2952
27. http://acm.hdu.edu.cn/showproblem.php?pid=2977
28. http://acm.hdu.edu.cn/showproblem.php?pid=4394

poj

1. http://poj.org/problem?id=1475
2. http://poj.org/problem?id=1915
3. http://poj.org/problem?id=1979
4. http://poj.org/problem?id=2046
5. http://poj.org/problem?id=2110
6. http://poj.org/problem?id=3126
7. http://poj.org/problem?id=3271
8. http://poj.org/problem?id=3278
9. http://poj.org/problem?id=3669
10. http://poj.org/problem?id=3984

I hope that through my own sharing, we can learn computer knowledge more easily. Tags: Algorithm leetcode bfs

Posted by funguse on Sun, 23 May 2021 07:24:02 +0930