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][0], y+dir[i][1])
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
- Define state representation
- Define state transition methods
- 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
- Calculation of 2-point shortest path in weighted graph
- Hierarchical traversal of graph or tree
- Graph connected block related calculation, such as judging whether 2 points are connected, there are several connected blocks.
Application of implicit graph
- Ask whether the target state can be reached from the initial state.
- 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[0] // 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
Topic link https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
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:
[
[3],
[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[0] // 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
Title Link: https://leetcode-cn.com/problems/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[0]*1000+state[1]
}
func numIslands(grid [][]byte) int {
n, m := len(grid), len(grid[0])
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[0]][start[1]]=='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[0]
queue = queue[1:]
// state transition
for _, d:=range dir {
nx, ny := front[0]+d[0], front[1]+d[1] // 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
Title Link: https://leetcode-cn.com/problems/word-ladder/
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[0]
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].
*/
func getLinksV1(wordList []string) map[string][]string{
links := map[string][]string{}
for _, s1 := range wordList {
for _, s2 := range wordList {
// Judge whether s1 to s2 can be changed by one letter
// links[s1] = append(links[s1], s2)
}
}
return links
}
/*
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.
*/
func getLinksV2(wordList []string) map[string][]string{
var wordMap map[string]bool // Stores whether a word is in the wordList
links := map[string][]string{}
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
// links[s1] = append(links[s1], newStr)
}
}
}
return links
}
/*
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
}
links := map[string][]string{}
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)] {
links[s] = append(links[s], string(bs))
}
}
}
}
return links
}
/*
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
// fmt.Println(links)
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[0]
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
Main contents:
-
Extensive search algorithm is a kind of violent algorithm, which is suitable for graph search problem with small state complete set.
-
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.
-
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.
- Hierarchical traversal application topic link https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
- Connected block application topic link https://leetcode-cn.com/problems/number-of-islands/
- Shortest path application topic link https://leetcode-cn.com/problems/word-ladder/
AK leetcode
leetcode related topics are in the following, take up arms and roll call one by one.
https://leetcode-cn.com/tag/breadth-first-search/problemset/ Binary search question list
The above topics are too many, you can choose appropriately, and there are advanced topics below.
Great God advanced
hdu
- http://acm.hdu.edu.cn/showproblem.php?pid=1026
- http://acm.hdu.edu.cn/showproblem.php?pid=1035
- http://acm.hdu.edu.cn/showproblem.php?pid=1043
- http://acm.hdu.edu.cn/showproblem.php?pid=1072
- http://acm.hdu.edu.cn/showproblem.php?pid=1195
- http://acm.hdu.edu.cn/showproblem.php?pid=1226
- http://acm.hdu.edu.cn/showproblem.php?pid=1241
- http://acm.hdu.edu.cn/showproblem.php?pid=1242
- http://acm.hdu.edu.cn/showproblem.php?pid=1252
- http://acm.hdu.edu.cn/showproblem.php?pid=1253
- http://acm.hdu.edu.cn/showproblem.php?pid=1312
- http://acm.hdu.edu.cn/showproblem.php?pid=1372
- http://acm.hdu.edu.cn/showproblem.php?pid=1426
- http://acm.hdu.edu.cn/showproblem.php?pid=1495
- http://acm.hdu.edu.cn/showproblem.php?pid=1547
- http://acm.hdu.edu.cn/showproblem.php?pid=1548
- http://acm.hdu.edu.cn/showproblem.php?pid=1885
- http://acm.hdu.edu.cn/showproblem.php?pid=2128
- http://acm.hdu.edu.cn/showproblem.php?pid=2416
- http://acm.hdu.edu.cn/showproblem.php?pid=2605
- http://acm.hdu.edu.cn/showproblem.php?pid=2612
- http://acm.hdu.edu.cn/showproblem.php?pid=2614
- http://acm.hdu.edu.cn/showproblem.php?pid=2616
- http://acm.hdu.edu.cn/showproblem.php?pid=2717
- http://acm.hdu.edu.cn/showproblem.php?pid=2821
- http://acm.hdu.edu.cn/showproblem.php?pid=2952
- http://acm.hdu.edu.cn/showproblem.php?pid=2977
- http://acm.hdu.edu.cn/showproblem.php?pid=4394
poj
- http://poj.org/problem?id=1475
- http://poj.org/problem?id=1915
- http://poj.org/problem?id=1979
- http://poj.org/problem?id=2046
- http://poj.org/problem?id=2110
- http://poj.org/problem?id=3126
- http://poj.org/problem?id=3271
- http://poj.org/problem?id=3278
- http://poj.org/problem?id=3669
- http://poj.org/problem?id=3984
I hope that through my own sharing, we can learn computer knowledge more easily.
