BFS

谁借莪１个温暖的怀抱￠ 2022-08-03 16:51 149阅读 0赞

### 总体感悟 ###

广搜的话，占内存多，能找到最优解，必须遍历所有分枝. 广优的一个应用就是迪科斯彻单元最短路径算法。BFS在求解最短路径或者最短步数上有很多的应用。应用最多的是在走迷宫上。

### 空间复杂度 ###

因为所有节点都必须被储存，因此BFS的空间复杂度为 O(|V| + |E|)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。

注：另一种说法称BFS的空间复杂度为 ，其中 B 是最大分支系数，而 M 是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。

### 时间复杂度 ###

最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为 O(|V| + |E|)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。（应该不准确）

### 完全性 ###

广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。

### 最佳解 ###

若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，BFS仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS的改良算法[成本一致搜寻法][Link 1]来解决。然而，若非加权图形，则所有边的长度相等，BFS就能找到最近的最佳解。

HDU 1040（简单bfs模板）

#include <iostream>
    #include<stdio.h>
    #include<queue>
    using namespace std;
    
    int sx,sy,sz; //起始坐标
    int ex,ey,ez; //目标坐标
    int ans,n,i,j,k,flag;
    char start[11],en[11];
    char map[11][11][11];  //地图
    int dir[6][3]={
       {0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}}; //三维空间移动
    struct node
    {
    	int x,y,z,step;
    };
    int bfs()
    {
    	queue<node>q;  //建立node型的一个队列
    	node cur,next;
    	flag=0;
    	cur.x=sx;
    	cur.y=sy;
    	cur.z=sz;
    	cur.step=0;
    	map[sz][sx][sy]='X';  //已遍历则将该位置记为‘X’,不再处理该位置
            //root 根节点
    	q.push(cur);         //将cur置入队列
    	while(!q.empty())    //判断队列是否为空，不为空则进入
    	{
    		cur=q.front();  //返回第一个置入的元素,cur赋值为第一个置入的元素
    		q.pop();         //移除该返回的元素
    		for(i=0;i<6;i++)   //遍历cur的下一层
    		{
    			next.x=cur.x+dir[i][0];
    			next.y=cur.y+dir[i][1];
    			next.z=cur.z+dir[i][2];
    			next.step=cur.step + 1;
    			if(next.x>=0&&next.y>=0&&next.z>=0&&next.x<n&&next.y<n
    				&&next.z<n&&map[next.z][next.x][next.y]=='O')
    			{
    				if(next.x==ex&&next.y==ey&&next.z==ez)
    				{
    					flag=1;
    					return next.step;
    				}
    				map[next.z][next.x][next.y]='X';
    				q.push(next);     //将next置入队列中
    			}
    		}
    	}
    	return 0;
    }
    int main() 
    {   
    	while(cin>>start>>n) 
    	{ 
    		for(i=0;i<n;i++)
    		{
    			for(j=0;j<n;j++)
    			{
    				cin>>map[i][j];
    			}
    		}
    		cin>>sx>>sy>>sz;    
    		cin>>ex>>ey>>ez;
    		cin>>en;
    		if(sx==ex&&sy==ey&&sz==ez)
    		{ 
    			cout<<n<<" "<<0<<endl;
    			continue;
    		}
    		ans=bfs(); 
    		if(flag==1)
    			cout<<n<<" "<<ans<<endl;
    		else
    			cout<<"NO ROUTE"<<endl;
    	}
    	return 0; 
    }

[Link 1]: http://zh.wikipedia.org/w/index.php?title=成本一致搜尋法&action=edit&redlink=1