广度优先搜寻

习题预习

1. 在一张无向图中，如何找出两个给定节点之间的最短路径？
2. 在一个网格中，如何找到从起点到终点的最短路径，其中障碍物可能会阻挡移动？
3. 如何在一个社交网络中找到关于某个人的直接或间接联系，并计算出与他们之间的距离？
4. 如何从起点到尽可能多的目标节点，而不必找到最短路径？
5. 如何在一个巨大的图形资料库中找到与搜索条件最相符的所有图形，并以最短路径显示它们之间的关系？

说明知识

Breadth-First Search（BFS）是一种搜寻演算法，以广度优先的方式来遍历一个图形或树状结构。

其遍历的顺序是逐层往下，也就是先遍历所有的同一深度节点，再遍历下一深度的节点。在BFS遍历中，使用一个队列来维护已经被广度遍历的节点，以便按层访问下一阶段节点时使用。

举个例子：假设我们有一个有向图如下图所示：

我们从节点1开始进行BFS遍历，首先将节点1加入队列中。接下来，按照节点编号的大小顺序，先遍历节点2和节点3。

然后，把节点2的相邻节点4，7加入队列中，把节点3的相邻节点5，6加入队列中。

再遍历节点4和节点7，因为它们没有相邻节点可加入队列中，所以直接跳过。

最后，遍历节点5和节点6，发现节点5有一个相邻节点8，所以把节点8加入队列中。遍历完节点5和节点6，队列已经空了，此时遍历结束。

这个例子中，我们首先访问距离起点节点最近的节点，然后是次近的节点，然后是更远的节点。这种BFS的访问顺序可以确保我们在最短时间内访问到所有节点。

条列重点

1. 广度优先搜寻演算法（BFS）是一种用来搜索图形或树形结构的技术。

2. BFS从起始节点开始搜寻，然后逐层扩展，直到达到终点或所有节点都被访问为止。

3. BFS适用于找到最短路径和最少操作的问题，因为它保证了先找到的路径长度最短或者操作最少。

4. BFS使用FIFO（先进先出）伫列来保存待处理的节点，这有助于记录搜寻顺序和计算层次。

5. BFS通常需要使用标记访问过的节点，以避免重复访问和死循环。

6. BFS可以用来应对未知的图形和树形结构，并且可以与其他搜寻演算法结合使用。

7. BFS的时间复杂度为O(V+E)，其中V是图形的节点数，E是图形的边数。

知识测验

1. 题目： 给定一个连通无向图，起始节点为S，每个节点都是一个整数，节点间的距离为1。你的任务是从起始节点开始按字典序打印所有节点。输入的图是用邻接矩阵表示的，值为1表示两个节点相连，0表示不连通。 同时输入的起始节点的下标，输出样例中“#”表示空格。

答案：

from queue import Queue

def bfs(n, start_node):
visited = [0] * n
queue = Queue()
queue.put(start_node)
visited[start_node] = 1
while not queue.empty():
node = queue.get()
print(node, end=’ ‘)
for i in range(n):
if adj[node][i] == 1 and visited[i] == 0:
visited[i] = 1
queue.put(i)

n = int(input())
adj = []
for i in range(n):
adj.append(list(map(int, input().split())))

start_node = int(input())

bfs(n, start_node)

2. 题目：有n个物品，每种物品都有自己的重量和价格，在限定的总重量内，选出若干件物品使得物品的总重量不超过总重量且总价格最大。假设背包的容量为C（Capacity），每个物品的重量为w（weight），价值为v（value）。使用BFS求背包问题的最优解。

答案：

from queue import Queue

class Node:
def init(self, level, weight, value, bound):
self.level = level
self.weight = weight
self.value = value
self.bound = bound

def bound(node, max_weight, n, values, weights):
if node.weight >= max_weight:
return 0
result = node.value
j = node.level + 1
total_weight = node.weight
while j < n and total_weight + weights[j] <= max_weight:
total_weight += weights[j]
result += values[j]
j += 1
if j < n:
result += (max_weight - total_weight) * (values[j] / weights[j])
return result

def bfs(n, max_weight, values, weights):
queue = Queue()
root = Node(-1, 0, 0, 0)
queue.put(root)
max_value = 0
while not queue.empty():
node = queue.get()
if node.level == -1:
left = Node(0, 0, 0, 0)
elif node.level == n - 1:
continue
else:
left = Node(node.level + 1, node.weight + weights[node.level + 1], node.value + values[node.level + 1], 0)
left.bound = bound(left, max_weight, n, values, weights)
if left.weight <= max_weight and left.value > max_value:
max_value = left.value
if left.bound > max_value:
queue.put(left)
right = Node(node.level + 1, node.weight, node.value, 0)
right.bound = bound(right, max_weight, n, values, weights)
if right.weight <= max_weight and right.value > max_value:
max_value = right.value
if right.bound > max_value:
queue.put(right)
return max_value

n = int(input())
max_weight = int(input())
values = list(map(int, input().split()))
weights = list(map(int, input().split()))

max_value = bfs(n, max_weight, values, weights)

print(max_value)

3. 题目：在一个NxN的网格中，1代表通路，0代表墙，从左上方的格子开始走，每次只能向右或向下走，走到右下角的格子后结束，寻找一条最短的路径。

答案：

from queue import Queue

class Node:
def init(self, row, col, steps):
self.row = row
self.col = col
self.steps = steps

def bfs(n, grid):
directions = [(1, 0), (0, 1)]
visited = [[False for _ in range(n)] for _ in range(n)]
queue = Queue()
start = Node(0, 0, 0)
queue.put(start)
visited[0][0] = True
while not queue.empty():
currentNode = queue.get()
if currentNode.row == n - 1 and currentNode.col == n - 1:
return currentNode.steps
for dir in directions:
newRow = currentNode.row + dir[0]
newCol = currentNode.col + dir[1]

		if newRow >= 0 and newRow < n and newCol >= 0 and newCol < n and grid[newRow][newCol] == 1 and not visited[newRow][newCol]:
			queue.put(Node(newRow, newCol, currentNode.steps + 1))
			visited[newRow][newCol] = True
return -1

n = int(input())
grid = []
for i in range(n):
grid.append(list(map(int, input().split())))

print(bfs(n, grid))

4. 题目： 给定一个大小为n的矩阵，每个位置的值代表该位置的魔法值，每次可以进行一次魔法转换，将以该位置为起始点的行和列值全部加1。求将整个矩阵的魔法值加到X需要进行最少多少次魔法转换。

答案：

from queue import Queue

class Node:
def init(self, i, j, value, steps):
self.i = i
self.j = j
self.value = value
self.steps = steps

def bfs(n, grid, x):
visited_row = [False for _ in range(n)]
visited_col = [False for _ in range(n)]
queue = Queue()
start = Node(0, 0, grid[0][0], 0)
visited_row[0] = True
visited_col[0] = True
queue.put(start)
count = 0
while not queue.empty():
node = queue.get()
if node.value >= x:
count = node.steps
break
if not visited_row[node.i]:
for j in range(n):
newValue = node.value + grid[node.i][j]
queue.put(Node(node.i, j, newValue, node.steps + 1))
visited_row[node.i] = True
if not visited_col[node.j]:
for i in range(n):
newValue = node.value + grid[i][node.j]
queue.put(Node(i, node.j, newValue, node.steps + 1))
visited_col[node.j] = True
return count

n = int(input())
grid = []
for i in range(n):
grid.append(list(map(int, input().split())))

x = int(input())

print(bfs(n, grid, x))

5. 题目：将一个由字符串s1转换为字符串s2，可以进行三种操作：插入一个字符、删除一个字符、替换一个字符。求最小的操作次数。

答案：

from queue import Queue

class Node:
def init(self, s, steps):
self.s = s
self.steps = steps

def bfs(s1, s2):
if s1 == s2:
return 0
queue = Queue()
visited = set()
queue.put(Node(s1, 0))
visited.add(s1)
while not queue.empty():
node = queue.get()
for i in range(len(s1)):
for j in range(26):
newChar = chr(ord(‘a’) + j)
if newChar != node.s[i]:
newStr = node.s[:i] + newChar + node.s[i+1:]
if newStr == s2:
return node.steps + 1
if newStr not in visited:
queue.put(Node(newStr, node.steps + 1))
visited.add(newStr)
if len(node.s) < len(s2):
newStr = node.s + ‘a’
if newStr == s2:
return node.steps + 1
if newStr not in visited:
queue.put(Node(newStr, node.steps + 1))
visited.add(newStr)

		newStr = 'a' + node.s
		if newStr == s2:
			return node.steps + 1
		if newStr not in visited:
			queue.put(Node(newStr, node.steps + 1))
			visited.add(newStr)
		
	elif len(node.s) > len(s2):
		for i in range(len(node.s)):
			newStr = node.s[:i] + node.s[i+1:]
			if newStr == s2:
				return node.steps + 1
			if newStr not in visited:
				queue.put(Node(newStr, node.steps + 1))
				visited.add(newStr)
return -1

s1 = input()
s2 = input()

print(bfs(s1, s2))