图论——BFS搜索模板（python）

思路：

使用队列完成BFS搜索。使用标记数组标记元素是否被使用过。

from collections import deque q=deque() res=[] visited=[[0]*n for _ in range(m)] #m行n列的网格，初始化标记数组为全0 q.append([start_x,start_y]) #初始节点坐标入队 如q=[(5,3)] visited[start_x][start_y]=1 dirs=[(0,1),(0,-1),(1,0),(-1,0)] #定义四个方向 def bfs(start_x,start_y): while q: #当队列不为空时执行 x,y=q.popleft() #出队 res.append(grid[x][y]) #记录出队的元素 for dx,dy in dirs: nx=x+dx ny=y+dy if 0<=nx<m and 0<=ny<n: #如果没有越界 if visited[nx][ny]==0: #如果没有使用 visited[nx][ny]=1 #标记为使用后入队 q.append([nx,ny]) print(res) return res