DFS and BFS notes (I) breadth first search based on C language

It is mainly to sort out the teacher's class notes + Refer to the learning notes of the blog .

---

  The search is “ General solutions ”, It plays an important role in the field of algorithms and artificial intelligence . But search has its limitations and flexibility , It is one of the most difficult algorithms to learn and use .

【 Learning goals 】 Facing problems ：l1. Quickly build state space  2. Put forward a reasonable algorithm  3. Simple estimation of spatiotemporal performance

search algorithm It is a method that uses the high performance of computer to enumerate some or all possible cases of a problem purposefully so as to obtain the solution of the problem .

state （state）： It is a mathematical description of the progress of the problem at a certain time .

State shift （state-transition）： The problem goes from one state to another （ Or several ） Operation of status .

The state space （state space）： Search is actually traversing an implicit graph （ Nodes are all States , A directed edge corresponds to a state transition ）. A feasible solution of the search is a path from the starting node to any node in the target state set ; The search process is based on initial conditions and extension rules , The process of constructing a solution tree and finding nodes that match the target state . In this process, the traversal tree formed by traversing the implicit graph also becomes the state space .

Categories of search ：

1 Blind search ：

· Breadth first search （Breadth First Search）

· Depth-first search （Depth First Search）

· Pure random search 、 Repeat search 、 Iteratively deepen the search 、 Iterative widening search 、 Column search ……

2 Heuristic search

BFS Breadth first search

Concept

BFS The pursuit is breadth , Each time it is traversed layer by layer , Each time you traverse the elements of the current layer, you can continue to traverse the next layer .

Breadth first search is a method for Graph search algorithm , It can help answer two kinds of questions .

　　· From the node A set out , Yes, go to the node B The path to ？
　　· From the node A set out , Go to node B Which path is the shortest ？

Search steps

Pictured ：（ picture source https://www.cnblogs.com/tianqizhi/p/9914539.html）

You want to know if anyone knows mango marketers .

Search steps ： you → Whether the first-class relationship friend knows → Whether the secondary relationship friend knows → Level three ……

Every time you search ： If someone knows , Search terminated ; conversely , Add to “ Has searched ” list , Keep going .

in general ： First search in the once relationship , Make sure there is no post , Search in a quadratic relationship . then “ Expand the search circle ”.

Termination conditions ：1- Find the target 2- After traversing all the graphs .

working principle

（ picture source https://www.cnblogs.com/tianqizhi/p/9914539.html）

 

• First put the root node in the queue .
• Take the first node out of the queue , And test if it's a target .
• If you find a target , Then end the search and return the results .
• Otherwise, all its unchecked direct child nodes will be added to the queue .
• If the queue is empty , It means that the whole picture has been checked —— In other words, there is no target to be searched in the figure . End search and return “ Target not found ”.

Define a queue ;

Starting point join the queue ;

while( The queue is not empty )

{

    Take out the head of the team ;

    If it is the desired target state , Out of the loop ;

    otherwise , Extend the child nodes from it , All added to the end of the line ;

}

If the target is found in the loop , Output results ;

Otherwise, the output has no solution ;

Tools needed ：1. queue 2. Adjacency table or adjacency matrix 3. Tag array visited

· It's actually searching in the graph , But you don't have to create a diagram （“ Implicit graph ”）, Search and you will get one Search tree .

·l Number of nodes in the search tree 、 Branch number 、 depth , Determines the efficiency of search .

· There is no backtracking in the search process , Sacrifice space for time . Time complexity ：O(V+E)

The above question （ The code to python3 了 ）

#  source ：https://www.cnblogs.com/tianqizhi/p/9914539.html
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def person_is_seller(name):
    return name[-1] == 'm'

from collections import deque
search_queue = deque()# Create a queue 
search_queue += graph["you"]# Add your neighbors to this search queue 

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = [] # This array is used to record people who have been checked 
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:# Check only when the person has not checked 
             if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
             else:
                search_queue += graph[person]
                searched.append(person)# Mark the person as checked 
    return False

search("you")

example ：Knight Moves

（ The question above the valley of Los Angeles is ：UVA439 The movement of the knight Knight Moves）( So this problem can be solved in Luogu )

Q There is a horse on the chess board , To jump from the starting point to the specified target , At least a few steps ？

（ Add · Horse （N）： Go horizontally or straight one space at a time , And then go out a little bit ; Or take a diagonal first , Finally, take a horizontal or vertical walk outside （ That is to say “ Japan ” word ）. You can go over the baby , There is no Chinese chess “ Poor horse legs ” Limit .）

Implementation steps

Get the start and end of the query .

1. Generate graph G.

python Use a dictionary to achieve ：

· Hash table to represent the graph structure , The key represents a node , Value indicates the one degree relation node corresponding to this node .

· key - The order in which value pairs are added is not very important , Because hash tables are unordered .

2. Define the lookup function .

3. Create a list that has been queried .

4. Define the judgment function .

eg：a1-->e4

Complete code : ( Why don't I C++ Because now I can't )

#include<stdio.h>
#include<string.h>
#include <stdlib.h>
typedef struct QNode{
    int x;
    int y;
    struct QNode * next;
}QNode;
// A chained queue creation function 
QNode * initQueue(){
    // Create a head node 
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    // Initialize the header node 
    queue->next=NULL;
    return queue;
}
// The team  
QNode* enQueue(QNode * rear,int x,int y){  
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->x=x;enElem->y=y;
    enElem->next=NULL;//1、 Wrap queued elements with nodes 
    rear->next=enElem;//2、 New nodes and rear Nodes establish logical relationships 
    rear=enElem;//3、rear Point to a new node 
    // Return to new rear, Prepare for new elements to join the team 
    return rear;
}
// Out of the team 
void DeQueue(QNode * top){
    if (top->next==NULL) {
        printf(" The queue is empty \n");
        return ;
    }
    QNode * p=top->next;
    //printf("%d %d\n",p->x,p->y);
    top->next=p->next;
    free(p);
} 
// Every time you enter the queue  
QNode* input(QNode *rear,int x,int y,int chess[9][9],int count)
{
	//8 In line  
    if(x-2>0&&y-1>0&&chess[x-2][y-1]==0)
    {
    	rear=enQueue(rear,x-2,y-1);//1	
    	chess[x-2][y-1]=count;//( Tag array  )
	}		
	if(x-2>0&&y+1<9&&chess[x-2][y+1]==0)
	{
		rear=enQueue(rear,x-2,y+1);	//2
		chess[x-2][y+1]=count; 
	}	
	if(x+2<9&&y-1>0&&chess[x+2][y-1]==0)
	{
		rear=enQueue(rear,x+2,y-1);//3
		chess[x+2][y-1]=count;
	}
	if(x+2<9&&y+1<9&&chess[x+2][y+1]==0)
	{
		rear=enQueue(rear,x+2,y+1);	//4
		chess[x+2][y+1]=count;
	}		
	if(x-1>0&&y-2>0&&chess[x-1][y-2]==0)
	{
		chess[x-1][y-2]=count;
		rear=enQueue(rear,x-1,y-2);//5
	}	
	if(x-1>0&&y+2<9&&chess[x-1][y+2]==0)
	{
		chess[x-1][y+2]=count;
		rear=enQueue(rear,x-1,y+2);	//6
	}			
	if(x+1<9&&y-2>0&&chess[x+1][y-2]==0)
	{
		chess[x+1][y-2]=count;
		rear=enQueue(rear,x+1,y-2);//7
	}			
	if(x+1<9&&y+2<9&&chess[x+1][y+2]==0)
	{
		chess[x+1][y+2]=count;
		rear=enQueue(rear,x+1,y+2);	//8
	}	
	return rear;
}

int main()
{
	//1 Create a chart ： Array 
	int chess[9][9]={0};
	//2. Get start and end conditions .
	char order1[2]={0},order2[2]={0};
	scanf("%s%s",order1,order2);
	
	if(strcmp(order1,order2)==0)
	{
		printf("To get from %s to %s takes 0 knight moves.",order1,order2);
		return 0;
	}
	
	int x,y,m,n;
	int endx=order2[0]-'a'+1,endy=order2[1]-'0';
	//printf("end%d %d\n",endx,endy);
	x=order1[0]-'a'+1;y=order1[1]-'0';
	chess[x][y]=-1;// It's just a marker , Don't go any further  
	//3.BFS Search for 
	// Because this question 8*8 You can always reach it  
	QNode * queue,*top,*rear;// Create a header node 
	// Add nodes to the chain queue , Add while using tail interpolation , The end of line pointer needs to point to the last element of the linked list 
    queue=initQueue();
    top=queue;rear=queue;
    rear=input(rear,x,y,chess,1);
	int count=1;
	while(1)
	 {// First in first out queue , last in last out  
	 	QNode * p=top->next;// View the first element in the queue at this time  
	 	m=p->x;n=p->y;
	 	//printf(" %d: %d %d\n",chess[m][n],m,n);
	 	if(chess[m][n]!=count)
	 		count++;// Number of update rounds  
	 	if(m==endx&&n==endy)
	 	{// End  
	 		printf("To get from %s to %s takes %d knight moves.",order1,order2,chess[m][n]);
			 return 0;
		 }	
		 rear=input(rear,m,n,chess,count+1);
		 DeQueue(top);
		
	 }
	return 0;
} 

this is it . Good night, .

PLUS： Some related algorithm exercises on the Internet

lzju 1091《Knight Moves》

lzju 1047《Image Perimeters》

lzju 1103《Hike on a Graph》

lzju 1649《Rescue 》

lzju 1310《Robot》

lzju 1136《Multiple》

lzju 1530《Find The Multiple》

lzju 1301《The New Villa》

---

https://blog.csdn.net/t11383/article/details/91129812

https://blog.csdn.net/weixin_44585839/article/details/96478163

https://www.cnblogs.com/tianqizhi/p/9914539.html

https://blog.csdn.net/akyna/article/details/113786003

https://blog.csdn.net/weixin_44441131/article/details/106629327

---

The search algorithm needs to search for a solution with specific properties in the exponential order of complex optional objects , and , There seems to be no shortcut to solve these problems .——《 Introduction to algorithms 》