宽度优先搜索（广度优先搜索，BFS）_海港队列与宽搜

如果圈中存在环，则同一个节点可能重复进入队列

特殊情况：

对于有权值且带环的图

一般情况：

重复BFS没有意义：

对于联通块问题，不可能带来新的节点

对于最短路问题，不可能代理最短的路径

使用哈希表去重：

python：dict/set

dict可以存两个值，一个是已经被遍历的节点，另一个是最短距离的值

图包括树（没有环的图）和环，树又包括多叉树

简单图：无向

复杂图：有向；有权；有向有权；两点间有多条边，有自己连自己的点。

N个点，M条边，图上BFS时间复杂度=O（N+M)，说是O（M）问题也不大，因为M一般都比N大，M最大是O（N^2）的级别（任意两个点都有边），所以最坏的可能是O（N^2)。

 一般与BFS有关的总是伴随着图

既然如此就少不了关于图的代码构建这一重点

关于图，有三个特点，分别为权，向，环。

我们可以大致分为

简单图：无向

复杂图：有向；有权；有向有权；两点间有多条边，有自己连自己的点。

一个算法看似知识点单一，其实只是核心单一，但有些知识点也必须要掌握，

我们在遇到BFS的变形题时为什么往往难以下手，我想大概就是只知道核心而不知其它构筑点的使用，对对于BFS的分类，我想也只是在其他知识点上进行修改，而其核心还是没有变的。

 首先我们要了解队列Queue

 先进先出

from queue import Queue  调用

q=Queue(5) 创建

q.put（）入队，放在最后

q.get（）出队，队首先出

q.empty（）判断q是否为空        常用while（！q.empty（））为循环退出条件

我们以几道题来分类知识点

报数 游戏

那如果这个小朋友报的数不是m,那么他还需要继续游戏,他刚报完数,需要等过一圈以后才会再次报数,我们让这个小朋友重新入队。

若m，n=5，7

问最后剩下的小朋友编号为 6

from queue import Queue
q=Queue()
n,m=map(int,input().split())
for i in range(1,n+1):
    q.put(i)
s=0
while(q.empty()==False):
    a=q.get()
    s+=1
    if s==5:
        s=0
    else:
        q.put(a)
print(a)

本题对数据进行加入和删除来模拟循环

广度优先搜索：又称宽度优先搜索,简称bfs。与深度优先搜索不同的是,广度优先搜索会先将与起始点距离较近的点搜索完毕,再继续搜索较远的点,而深搜却是沿着一个分支搜到最后。

        bfs从起点开始,优先搜索离起点最近的点,然后由这个最近的点扩展其他稍近的点,这样一层一层的扩展,就像水波扩散一样。

利用BFS来求迷宫最短路：BFS是将每走n步的所有方案都走完才继续走第n+1步，所以当第一次出现终点时就是最短的路径步数（距离要根据步长进一步判断）。

题型一：迷宫只求最短步数是多少（二维坐标标准型）

输入

5 6
....S*
.**...
.*..*.
*..**.
.T....

输出

7

from queue import Queue
q=Queue()
n,m=map(int,input().split())
mg=[]
for i in range(n):
    l=list(input())
    mg.append(l)
#print(mg)
vis=[[False]*m for i in range(n)]
 
xq=0
yq=0
for i in range(n):
    for j in range(m):
        if mg[i][j]=='S':
            xq=i
            yq=j
 
def bfs(xq,yq):
    q.put([xq,yq,0])
    vis[xq][yq]=True
    while(q.empty()==False):
        now=q.get()
        x,y=now[0],now[1]
        d=now[2]
        for (dx,dy) in [(1,0),(0,1),(-1,0),(0,-1)]:
            x1=dx+x
            y1=dy+y
            if 0<=x1<n and 0<=y1<m and vis[x1][y1]!=True and mg[x1][y1]!='*':
                if mg[x1][y1]=='T':
                    return d+1 #结束bfs
                else:
                    vis[x1][y1]=True
                    q.put([x1,y1,d+1])
    return -1 #没找到rutuen -1 结束bfs
 
d=bfs(xq,yq)
print(d)

题型一：迷宫只求最短步数是多少（一维坐标型）

在一个长度为n的坐标轴上,蒜头君想从A点移动到B点。他的移动规则如下:

1.向前一步,坐标增加1。

2.向后一步,坐标减少1。

3.跳跃一步,使得坐标乘2。

蒜头君不能移动到坐标小于0或大于n的位置。蒜头君想知道从A点移动到B点的最少步数是多少,你能帮他计算出来么?

输入格式

第一行输入三个整数n, A, B,分别代表坐标轴长度,起始点坐标,终点坐标。(0< A, B<n< 5000)

输入

10 2 7

输出

3

from queue import Queue
q=Queue()
n,A,B=map(int,input().split())
vis=[False]*n
def bfs(xq,xz):
    q.put([xq,0])
    vis[xq]=True
    while(q.empty()==False):
        now=q.get()
        x=now[0]
        d=now[1]
        for dx in [1,-1,x]:
            x1=dx+x
            if 0<=x1<n and vis[x1]!=True:
                if x1==xz:
                    return d+1
                else:
                    vis[x1]=True
                    q.put([x1,d+1])
    return -1
print(bfs(A,B))

题型三：四维坐标型

from queue import Queue
q=Queue()
qs=list(map(int,input()))
zd=list(map(int,input()))
 
vis=[[[[0]*10 for i in range(10)] for j in range(10)] for k in range(10)]
 
def bfs(qs,zd):
    qs.append(0)
    q.put(qs)
    vis[qs[0]][qs[1]][qs[2]][qs[3]]=1
    while(q.empty()==False):
        now=q.get()
        if now[0]==zd[0] and now[1]==zd[1] and now[2]==zd[2] and now[3]==zd[3]:
            print(now[4])
            return  #出口
 
        for i in range(4): #-1
            next=now.copy()
            next[i]-=1
            if next[i]==0:
                next[i]=9
            if vis[next[0]][next[1]][next[2]][next[3]] != 1:
                vis[next[0]][next[1]][next[2]][next[3]] = 1
                next[4]+=1
                q.put(next)
                #print(next)
 
 
        for i in range(4): #+1
            next=now.copy()
            next[i]+=1
            if next[i]==10:
                next[i]=1
            if vis[next[0]][next[1]][next[2]][next[3]]!=1:
                vis[next[0]][next[1]][next[2]][next[3]] = 1
                next[4]+=1
                q.put(next)
                #print(next)
 
 
        for i in range(3): #交换
            next = now.copy()
            a=next[i]
            next[i]=next[i+1]
            next[i+1] = a
            if vis[next[0]][next[1]][next[2]][next[3]] != 1:
                vis[next[0]][next[1]][next[2]][next[3]] = 1
                next[4]+=1
                q.put(next)
                #print(next)
    return -1
 
bfs(qs,zd)
 

重点：

四维列表的建立

每一步有11种走法，4个位各加1，4个位各减1，3个交换

1到9的值循环

进阶题型，有些密码不能取，则在if中进行判断即可

题型四：扩散型

乳草的侵占  

armer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿，他在植物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

草地像往常一样，被分割成一个高度为Y(1 <= y <= 100), 宽度尾X(1 <= x <= 100)的直角网格。(1,1)是左下角的格（也就是说坐标排布跟一般的X,Y坐标相同）。乳草一开始占领了格(Mx,My)。每个星期，乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格（包括垂直与水平相邻的和对角线上相邻的格）。1周之后，这些新占领的格又可以把乳草传播到更多的格里面了。

Bessie想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能占领整个草地。如果乳草在0时刻处于格(Mx,My)，那么还在那个时刻它们可以完全占领入侵整片草地呢（对给定的数据总是会发生）？

草地由一个图片表示。"."表示草，而"*"表示大石。比如这个X=4, Y=3的例子。

....

..*.

.**.

如果乳草一开始在左下角（第1排，第1列），那么草地的地图将会以如下态势发展：

 乳草会在4星期后占领整片土地。

输入

*第一行: 四个由空格隔开的整数: X, Y, Mx, My 
*第2到第Y+1行: 数据的第y+1行由X个字符（"."表示草地，"*"表示大石），描述草地的第(Y+2-y)行。

输出

 一个单独的整数表示最后一个不是大石块的格子被乳草占领的星期数。

样例输入

4 3 1 1
....
..*.
.**.

样例输出

4 

from queue import Queue
X,Y,Mx,My=map(int,input().split())
cd=[]
vid=[[0]*X for i in range(Y)]
for i in range(Y):
    l=list(input())
    cd.append(l)
q=Queue()
def bfs(xq,yq):
    q.put([xq,yq])
    cd[xq][yq]='*'
    vid[xq][yq]=1
    d=1
    ma=0
    while(q.empty()==False):
        # for i in range(len(cd)):
        #     print(cd[i])
        # print()
        now=q.get()
        x,y=now[0],now[1]
        for (dx,dy) in [(1,0),(1,1),(0,1),(-1,0),(0,-1),(-1,-1),(-1,1),(1,-1)]:
            x1=dx+x
            y1=dy+y
            if 0<=x1<Y and 0<=y1<X and cd[x1][y1]!='*' and vid[x1][y1]!=1:
                cd[x1][y1]='*'
                vid[x1][y1] =vid[x][y]+1
                q.put([x1,y1])
                ma=max(ma,vid[x1][y1])
        d+=1
    return ma-1
print(bfs(Y-Mx,My-1))

题型五：状态压缩bfs

一维跳棋

一维跳棋是一种在1×(2N+1) 的棋盘上玩的游戏。一共有N个棋子，其中N 个是黑的，N 个是白的。游戏开始前，N 个白棋子被放在一头，N 个黑棋子被放在另一头，中间的格子空着。

在这个游戏里有两种移动方法是允许的：你可以把一个棋子移到与它相邻的空格；你可以把一个棋子跳过一个（仅一个）与它不同色的棋子到达空格。

对于N=3 的情况，棋盘状态依次为：

 1 WWW BBB
 2 WW WBBB
 3 WWBW BB
 4 WWBWB B
 5 WWB BWB
 6 W BWBWB
 7 WBWBWB
 8 BW WBWB
 9 BWBW WB
10 BWBWBW
11 BWBWB W
12 BWB BWW
13 B BWBWW
14 BB WBWW
15 BBBW WW
16 BBB WWW

对应的空格所在的位置（从左数）为：3 5 6 4 2 1 3 5 7 6 4 2 3 5 4。

输入格式

输入仅一个整数，表示针对N(1≤N≤10) 的取值。

输出格式

依次输出空格所在棋盘的位置，每个整数间用空格分隔，每行5 个数（每行结尾无空格，最后一行可以不满5 个数；如果有多组移动步数最小的解，输出第一个数最小的解）

样例输入

4 

样例输出

4 6 7 5 3
2 4 6 8 9
7 5 3 1 2
4 6 8 7 5
3 4 6 5

 pyrhon 队列建议使用deque不建议使用Queue（涉及多线程加锁会更慢）

from collections import deque
#step 1 初始化
#把初始节点放到deque里，如果有多个就都放进去
#并标记初始节点的距离为0，记录distance的dict里
#distance有两个作用，一是判断是否已经访问过，二是记录节点到起点的距离
queue=collections.deque([node])
distance={node:0}
#step2：不断访问队列
#while 循环+每次pop队列中的一个点出来
while queue:
    node=queue.popleft()
    #step 3:拓展相邻节点
    #pop出的节点的相邻节点，加入队列并再distance中存储距离
    for neighbor in node.get_neighbors():
        if neighbor in distance:
            continue
        distance[neighbor]=distance[node]+1
        queue.append(neighbor)