# 数据结构｜BFS

> source: 文章/bfs/index.md

# 数据结构｜BFS

题目链接: [99. 岛屿数量](https://kamacoder.com/problempage.php?pid=1171)

这里贴一下我之前自己写的代码

```python
class Queue:
    def __init__(self):
        self.items = []
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        if self.is_empty():
            raise IndexError("队列为空，无法出队")
        return self.items.pop(0)
    def is_empty(self):
        return len(self.items) == 0
    def peek(self):
        if self.is_empty():
            raise IndexError("队列为空，无法出队")
        return self.items[0]
    def size(self):
        return len(self.items)

direction = [ # 上、右、下、左 | 顺时针
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1]
]
def bfs(graph, visited, x, y, que) -> None:
    # 标记初始坐标
    visited[x][y] = True
    
    # 开始寻找附近节点
    for i, j in direction:
        next_x = x + i
        next_y = y + j
        # 边界条件
        if next_x < 0 or next_y < 0 or next_x >= len(graph) or next_y >= len(graph[0]):
            continue
        # 对于符合条件的，加入队列
        if not visited[next_x][next_y] and graph[next_x][next_y] == 1:
            visited[next_x][next_y] = True
            que.enqueue([next_x, next_y])
    
    que.dequeue()
    if que.is_empty():
        return
    new_x, new_y = que.peek()
    bfs(graph, visited, new_x, new_y, que)
    
def main():
    n, m = map(int, input().split())
    graph = []
    for i in range(n):
        graph.append(list(map(int, input().split())))
    visited = [[False for _ in range(m)] for _ in range(n)]

    # bfs作为一种手段来标记一整块陆地
    # 因此我们仍然需要对整个地图进行遍历
    ret = 0
    que = Queue()
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and graph[i][j] == 1:
                visited[i][j] = True
                # 说明找到新陆地
                ret += 1
                # 此时使用bfs标记整块陆地，以免出现重复
                que.enqueue([i, j])
                bfs(graph, visited, i, j, que)
    print(ret)

if __name__ == "__main__":
    main()
```

能用确实是能用，也能跑过测试，但是我的代码里犯了一些原则性错误(也许称不上错误)，导致代码的逻辑不突出，没有体现BFS的核心思想，更像是DFS

我们来理一下逻辑，在BFS函数中，先针对一个节点寻找它的相邻节点，然后加入到队列中，这确实没问题，但是逻辑上我既然都这样写了，为什么不进一步变成DFS呢？我完全可以在循环中添加找到后的递归逻辑，但是我在这里没有这么做，找完了一个节点以后，退出来将一开始的节点出队，然后对邻近的下一个节点依次寻找相邻可用节点

此外，在这里我将`que`作为一个参数传入给了BFS，这其中蕴含的含义是`que`作为一个**共享队列**，让**所有的**BFS调用共用它，而实际上只是这一个BFS在用而已，因此从代码逻辑来分析，我们应该把队列写入BFS里面，即*每发现一块陆地就新建一个BFS队列，只用于这次的BFS*，而之前的操作逻辑上确实每次BFS都将队列清空了，但那从代码逻辑上仍然是一个队列变量分配给很多次BFS使用，这一点需要注意

经过修改后的代码如下，其中还优化了很多细节，队列类和方向变量保持相同，此处省略了

```python
def bfs(graph, visited, x, y) -> None:
    que = Queue()
    que.enqueue((x, y))
    visited[x][y] = True
    
    while not que.is_empty():
        curr_x, curr_y = que.dequeue()
        for dx, dy in direction:
            nx, ny = curr_x + dx, curr_y + dy
            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]):
                if not visited[nx][ny] and graph[nx][ny] == 1:
                    visited[nx][ny] = True
                    que.enqueue((nx, ny))
    
def main():
    n, m = map(int, input().split())
    graph = []
    for _ in range(n):
        graph.append(list(map(int, input().split())))
    visited = [[False] * m for _ in range(n)]

    ret = 0
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and graph[i][j] == 1:
                bfs(graph, visited, i, j)
                ret += 1
    print(ret)

```

可见代码总体来看简洁了不少

如果要形象一点地说的话，之前的我的DFS风格的代码就好像挨个点名寻找共犯，每次要队列里的第一个人供出来他的同伙，然后新的同伙拍到最后

修改后的代码则有一种小丑抛球的感觉，球在空中一直飞个不停，抛着抛着球越变越多，然后又依次抛出
