**Breadth-First-Search**

1. And DFS Similarities and differences

The same thing ： Search for all possible states .

Difference ： Search order .

2. BFS Always search the state close to the initial state first , It is according to ： Start state -> All states that can be reached with just one transition -> All states that can be reached with just two transitions ->……

Search for the same state only once , So the complexity is O（ Number of States * Transfer mode ）.

3. DFS Implicit use of the stack , and BFS Using queues , When searching, first queue the initial state , After that, get out of the team , And queue the state that can be transferred to the state that has not been accessed ,

Repeat the process , Until the queue is empty or a solution is found . Looking at the queue, we can see that , All States are traversed from near to far from the initial state .

Here is a classic example ： The shortest path in the maze

description:

Given a size of N*M The maze of . The labyrinth is made up of passages and walls , Each step can move to the adjacent four grid channels . Request the minimum number of steps from the start to the end . Please note that , This problem assumes that you can move from the beginning to the end .

Sample input and output ：

Input ：

Output ：

22

AC Code：

int INF=0x3f3f3f3f;

typedef pair<int,int> P;

int N,M,sx,sy,gx,gy;

char maze[N][M];

int d[N][M];// Record the shortest distance to each position

int dx[]={,,-,},dy={,,,-};

int bfs(){

queue<P> q; q.push(P(sx,sy));

memset(d,INF,sizeof(d));

d[sx][sy]=;

while(！q.empty()){

P p=q.front(); q.pop();

if(p.first ==gx&&p.second ==gy) break;

for(int i=;i<;i++){

int nx=P.first +dx[i],ny=P.second +dy[i];

if(nx>=&&nx<N&&ny>=&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==INF){

q.push(P(nx,ny));

d[nx][ny]=d[p.first ][p.second]+;

}

}

}

return d[gx][gy];

}

## Width first search BFS（Breadth-First-Search） More articles about

- 【 Introduction to algorithm 】 Breadth / Width first search (BFS)
Breadth / Width first search (BFS) [ Introduction to algorithm ] 1. Preface Breadth first search ( Also known as width first search , abbreviation BFS, The following is a broad description of ) It's a traversal strategy for connected graphs . Because its idea is from a summit V0 Start , Radially preferentially traverse its surroundings ...

- Challenge the program 2.1.5 Exhaustive search >> Width first search
Let's make a comparison DFS and BFS Depth-first search DFS Width first search BFS It's obvious that the search order is different . DFS It's searching for a single path to ...

- 【BFS Width first search 】
One . Find all the vertices to s The minimum number of steps for a vertex //BFS Width first search #include<iostream> using namespace std; #include<queue> # ...

- Step by step —— Width first search （BFS）
Problem introduction Let's go back to last time “ Save xiaoha ” Continue to explore , But this time it's a width first search (BFS). notes : The source of the problem can be found here http://www.cnblogs.com/OctoptusLian/p/74296 ...

- BFS Optimization of algorithm Two way width first search
Two way width first search (Bidirectional BFS) The algorithm is suitable for the following scenarios : Undirected graph The length of all sides is 1 Or the length is the same At the same time, the starting point and the ending point are given above 3 When all conditions are met , You can use bidirectional width first ...

- Breadth first search （Breadth First Search, BFS）
Breadth first search (Breadth First Search, BFS) BFS The general idea of algorithm implementation is : // BFS void BFS(int s){ queue<int> q; // Define a ...

- [ Width first search ] FZU-2150 Fire Game
Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns) ...

- Width first search -------- The shortest path problem of maze (dfs)
Width first search uses queues (queue) stay unility Header file Source code #include<iostream>#include<cstdio>#include<queue&g ...

- Width first search （BFS）— 20180909 - 20180917
BFS Several kinds of questions : 1. Graph traversal :a. Level traversal b. From point to face c. A topological sort 2. The shortest path of a simple graph : Simple picture :1. Undirected graph 2. Edge weights are consistent Time complexity of graph : N A little bit ,M side ,M The biggest is N^2, Time complexity O(N+M ...

## Random recommendation

- SQL Server Maintenance plan to achieve database backup （ Strategy, actual combat ）
One . background I wrote an article about backup before :SQL Server Maintenance plan to achieve database backup , The above article uses full backup and differential backup to basically solve the problem of database backup , But to make the data more secure , We need to refine our backup plan again ...

- fir.im Weekly - 600 individual Android Open source project summary
In this issue Weekly Collected some heat resources , contain Android.iOS Development tools and source code sharing , Programmers should also know about product operations . Such design Tips , I hope it helps you . 600 individual Android Open source project summary laborious ...

- AngularJS(12)-BootStrap Integrate
AngularJS The preferred style sheet for is Bootstrap, Bootstrap Is the most popular front-end framework . <!DOCTYPE html> <html lang="en&qu ...

- Reprint ：Ununtu Next Chinese garbled solution
Reprint : Add Chinese character encoding : $sudo vim /var/lib/locales/supported.d/local # Add the following Chinese character set zh_CN.GBK GBK zh_CN.GB2312 GB ...

- Jquery：jquery Medium DOM operation < One >
I studied two days ago Jquery Powerful selector , I learned part of it today Jquery Yes DOM The operation of , Now I will share my achievements with you , Those rookies , Do you need to consolidate what you have learned before ? The first thing you need to know is ,DOM The operation is divided into 3 In terms of :D ...

- Python in Swithch Case The syntax to achieve
and python There is no such thing as switch sentence , The solutions are as follows 3 Kind of :A. Use dictionaryvalues = { value1: do_some_stuff1, value2: do_some_stuff ...

- poj_1679: The Unique MST【 Secondary spanning tree 】
Topic link Reference blog I hope the notes are clear enough .. Welcome to point out the shortcomings ~ #include<cstdio> #include<cstring> #include<algorithm> ...

- JS Basic knowledge points
I found a good thing recently , The nuggets pamphlets , I think the contents are very good , Prepare to read it carefully , Improve yourself . Make a note of , Feel free to impress , The main content comes from the booklet . The original type Primitive types also become basic data types boolean null ...

- git to update Activemq At remote github The source code steps for the specified version on the
First step : Clone the source code according to the address (activemq-5.9) $ git clone https://github.com/apache/activemq.git The second step : Check the version list of remote source code ( ...

- python Learning notes （10）-- Combined data types ( Collection types )
Collection types A set is an unordered combination of elements , Each element is unique , There is no same type , Each element is an immutable type . use {} Express , Elements are separated by commas . Set up a combination type with {}, or set function , If it's an empty set, you have to use set. >>&g ...