广度优先遍历算法：与深度优先遍历算法比较来看，拿深度优先算法那个例子来说就是：先查4个地方的机票价格再查各个地方的酒店价格，一层一层的查。
1.
# 利用广度优先遍历解决选课的烦恼
def bfs(numcourses, prelist):
prelistcount = [0] * numcourses
for line in prelist:
for i in range(len(line)):
if line[i] == 1:
prelistcount[i] += 1
cantake = []
for i in range(len(prelistcount)):
if prelistcount == 0:
cantake.append(i)
classtake = []
while len(cantake) != 0:
thisclass = cantake[0]
del cantake[0]
classtake.append(thisclass)
for i in range(numcourses):
if prelist[thisclass][i] == 1:
prelistcount[i] -= 1
if prelistcount[i] == 0:
cantake.append(i)
return classtake
# 寻找制高点
def bfs(set, m, n, matrix): # set用来储存可以到达的点
dir = [[0, 1], [0, -1], [1, 0], [-1, 0]] # 四个方向：向左向右向上向下
queue = list(set) # 把元组转换成列表成为队列
while len(queue) > 0:
x, y = queue.pop() # x,y分别是某一点横纵坐标
for d in dir: # 循环遍历4个方向
nx = x + d[0]
ny = y + d[1]
if 0 <= nx and nx < m and 0 <= ny and ny < n: # 确保点在地图上
if matrix[nx][ny] >= matrix[x][y]: # 如果新的点比原来点高则可以走
if (nx, ny) not in set:
queue.append((nx, ny))
set.add((nx, ny))
return set # 可不写这个 为什么？
def solve(matrix):
if not matrix:
return matrix
m = len(matrix) # 二维数组有多少行
n = len(matrix[0]) # 二维数组有多少列
toppoint = set([(0, y) for y in range(n)]) # 上边的点的横坐标为0，纵坐标为0~n-1
leftpoint = set([(x, 0) for x in range(m)]) # 左边的点的横坐标是0~m-1，纵坐标是0
bottompoint = set([(m - 1, y) for y in range(n)]) # 下边的点的横坐标m-1，纵坐标为0~n-1
rightpoint = set([(x, n - 1) for x in range(m)]) # 右边的点的横坐标为0~m-1，纵坐标为n-1
bfs(toppoint, m, n, matrix)
bfs(leftpoint, m, n, matrix)
bfs(bottompoint, m, n, matrix)
bfs(rightpoint, m, n, matrix)
result = toppoint & leftpoint & bottompoint & rightpoint
return result
matrix = [[1, 3, 2, 3, 5],
[3, 4, 5, 6, 3],
[2, 7, 4, 3, 3],
[5, 2, 2, 3, 1]]
s = solve(matrix)
print(s)
#######bfs函数返回的为什么是列表？？？？？？？
3.在一个给定的输入字符串中，移除掉最少量的错误的括号，从而使的这个字符串变为有效的字符串，并且返回所有有效的字符串
# 利用广度优先遍历解决括号合法性问题
def isvalid(str):
count = 0
for c in str:
if c == '(':
count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return count == 0
def bfs(str): # str是第一层的结果
res = [] # 存放最终结果
queue = [str] # 将第一层的数据生成队列
while len(queue) > 0:
for i in range(len(queue)): # 从队列中依次取出字符串进行分析
if isvalid(queue[i]):
res.append(queue[i]) # 发现合法字符串就放到结果集中
if len(res) > 0: # 如果发现合法字符串就结束循环返回结果，并用集合去重
return list(set(res))
# 如果第一层都不合法就查找下一层
# 生成下一层的队列数据
temp = [] # 临时结果集
for s in queue: # 队列中的每个字符串
for i in range(len(s)): # 每个字符串的每个字符
if s[i] == '(' or s[i] == ')':
temp.append(s[:i] + s[i + 1:])
queue = list(set(temp)) # 第二层的队列
return list(set(res))
4.给定一个二叉树，想想你自己站在该二叉树的右侧，去采摘最外层树上的柠檬
# 树的右侧
class treenode(object):
def __init__(self, x):
self.val = x # 二叉树上每个元素的值，这里代表柠檬的编号
self.left = None # 二叉树的每个元素的左子树
self.right = None # 二叉树的每个元素的右子树
def rightside(root):
result = [] # 存放结果数据
queue = [root] # 队列存放待处理数据
while len(queue) > 0:
length = len(queue)
for i in range(length): # 依次处理每一行的节点
node = queue.pop() # 取出队列头的点（也就是从右边看的第一个点）取出后就从queue中消失
if i == length - 1: # 如果这个点是最后一个点
result.append(node.val)
if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)
# 如果不是每一层的最后一个点就会依次从每一层的从左到右留在queue中，每次加入新的一层时，都是加在最后面又是从左向右加的所以每次最右边的数在最后一个，pop弹出弹出想要的值
return result
node1 = treenode(1)
node2 = treenode(2)
node3 = treenode(3)
node1.right = node2
node2.right = node3
print(rightside(node1))