bfs算法python

好的，以下是BFS算法的Python实现：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

其中，`graph`是一个字典，表示图的邻接表；`start`是起始节点。

相关问题

bfs算法python迷宫问题

以下是使用BFS算法解决Python迷宫问题的代码示例：

from queue import Queue

# 定义迷宫地图
maze = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 1, 1, 1, 0, 1, 0],
    [0, 1, 1, 0, 1, 1, 1, 0, 1, 0],
    [0, 1, 1, 1, 1, 0, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    [0, 1, 1, 1, 0, 1, 1, 1, 1, 0],
    [0, 1, 0, 1, 1, 1, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 1, 0, 0, 1, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

# 定义四个方向
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# 定义BFS算法
def bfs(maze, start, end):
    queue = Queue()
    queue.put(start)
    visited = set()
    visited.add(start)
    prev = dict()

    while not queue.empty():
        cur = queue.get()
        if cur == end:
            print_path(prev, start, end)
            return
        for direction in directions:
            next_pos = (cur[0] + direction[0], cur[1] + direction[1])
            if is_valid(maze, next_pos) and next_pos not in visited:
                queue.put(next_pos)
                visited.add(next_pos)
                prev[next_pos] = cur

# 判断下一个位置是否合法
def is_valid(maze, pos):
    if pos[0] < 0 or pos[0] >= len(maze) or pos[1] < 0 or pos[1] >= len(maze[0]):
        return False
    if maze[pos[0]][pos[1]] == 0:
        return False
    return True

# 输出路径
def print_path(prev, start, end):
    ltmp = []
    node = end
    while node != start:
        ltmp.append(node)
        node = prev[node]
    ltmp.append(start)
    t_print(ltmp)

# 输出函数
def t_print(ltmp):
    node = ltmp[-1]
    ltmp_s = []
    while node in prev:
        ltmp_s.append(node)
        node = prev[node]
    ltmp_s.append(node)
    ltmp_s.reverse()
    for i in ltmp_s:
        print(i)

# 测试
start = (1, 1)
end = (8, 8)
bfs(maze, start, end)

请给出bfs算法Python代码

以下是BFS算法的Python代码：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

其中，`graph`是图的邻接表表示，`start`是起始节点。`visited`用于记录已访问过的节点，`queue`则是用于存储待访问的节点的队列。在每次循环中，从队列的左侧取出一个节点，如果该节点没有被访问过，则将其标记为已访问，并将其未访问过的邻居节点加入到队列中。最后返回已访问过的所有节点。