Python的BFS模板

以下是Python的BFS模板：

from collections import deque

def bfs(start, target):
    queue = deque()
    queue.append(start)
    visited = set()
    visited.add(start)

    step = 0

    while queue:
        size = len(queue)
        for i in range(size):
            cur = queue.popleft()
            if cur == target:
                return step
            for next_node in cur.children():
                if next_node not in visited:
                    queue.append(next_node)
                    visited.add(next_node)
        step += 1

    return -1

这是一个基本的BFS模板，可以用于解决许多问题，包括寻找最短路径等。

相关问题

python BFS算法模板

以下是 Python 中 BFS（广度优先搜索）算法的模板：

def bfs(graph, start):
    visited = set()   # 用集合记录已经访问过的节点
    queue = [start]   # 用队列存储遍历的节点
    while queue:
        node = queue.pop(0)   # 取出队列中的第一个节点
        if node not in visited:
            visited.add(node)
            # 将当前节点的未访问过的邻居节点加入队列
            queue.extend([neighbor for neighbor in graph[node] if neighbor not in visited])
    return visited

其中，`graph` 是一个字典，用于存储图的邻接表。字典的键表示节点，字典的值是与该节点相邻的节点列表。`start` 是起始节点。

该算法使用了集合来记录已经访问过的节点，队列则用于存储遍历的节点。在每一轮迭代中，取出队列中的第一个节点，并将该节点的未访问过的邻居节点加入队列中。如果队列为空，则说明已经遍历完了整张图。最后返回遍历过的节点集合。

python算法模板dfs和bfs

好的，以下是 Python 中 DFS 和 BFS 的代码模板。

DFS 模板：

def dfs(node, visited, graph):
    # 判断当前节点是否已经访问过
    if visited[node]:
        return
    # 标记当前节点为已访问
    visited[node] = True
    # 处理当前节点
    process(node)
    # 遍历当前节点的邻居节点
    for neighbor in graph[node]:
        # 递归访问邻居节点
        dfs(neighbor, visited, graph)

BFS 模板：

from collections import deque

def bfs(start, graph):
    # 创建队列，并将起始节点入队
    queue = deque([start])
    # 创建 visited 数组，用于标记每个节点是否访问过
    visited = [False] * (len(graph) + 1)
    # 标记起始节点为已访问
    visited[start] = True
    # 队列不为空时循环
    while queue:
        # 取出队头节点
        node = queue.popleft()
        # 处理当前节点
        process(node)
        # 遍历当前节点的邻居节点
        for neighbor in graph[node]:
            # 如果邻居节点未被访问过，则将其入队并标记为已访问
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

其中，DFS 和 BFS 的输入参数都是一个图和起始节点。对于 DFS，使用一个 visited 数组记录每个节点是否访问过，在访问节点时递归访问其邻居节点，直到所有连通节点都被访问过为止。对于 BFS，使用一个队列来存储待访问的节点，在访问节点时先处理当前节点，再将其邻居节点加入队列中，并标记为已访问，直到队列为空为止。