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

  1. 【 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 ...

  2. Challenge the program 2.1.5 Exhaustive search &gt;&gt; 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 ...

  3. 【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> # ...

  4. 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 ...

  5. 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 ...

  6. 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 ...

  7. [ 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) ...

  8. 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 ...

  9. 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

  1. 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 ...

  2. 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 ...

  3. 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 ...

  4. 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 ...

  5. Jquery:jquery Medium DOM operation &lt; One &gt;

    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 ...

  6. 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 ...

  7. 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> ...

  8. 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 ...

  9. 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 ( ...

  10. 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 ...