用Python代码实现广度优先搜索算法

下面是用Python实现广度优先搜索算法的示例代码：# 定义图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}# 定义广度优先搜索函数
def bfs(graph, start):
visited = [] # 已访问节点
queue = [start] # 搜索队列 while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
neighbours = graph[node] for neighbour in neighbours:
queue.append(neighbour) return visited# 调用函数
print(bfs(graph, 'A'))

相关问题

Python迷宫问题广度优先搜索算法求解代码

以下是Python实现的广度优先搜索算法求解迷宫问题的代码示例：

from collections import deque

def bfs(maze, start, end):
    queue = deque([(start, [])])
    visited = set([start])  # 记录已经搜索过的位置

    while queue:
        curr_pos, path = queue.popleft()
        if curr_pos == end:
            return path + [end]

        for direction in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            next_pos = (curr_pos[0]+direction[0], curr_pos[1]+direction[1])
            if 0 <= next_pos[0] < len(maze) and 0 <= next_pos[1] < len(maze[0]) and \
               maze[next_pos[0]][next_pos[1]] == 0 and next_pos not in visited:
                queue.append((next_pos, path+[curr_pos]))
                visited.add(next_pos)

    return None  # 无解

# 示例
maze = [[0, 0, 0, 1, 0],
        [1, 0, 0, 1, 0],
        [0, 0, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 0, 0, 1]]
start, end = (0, 0), (4, 4)
print(bfs(maze, start, end))

该代码使用了队列和集合作为数据结构，其中队列保存了当前正在遍历的节点和到达该节点的路径，集合保存了已经搜索过的节点，避免重复搜索。当搜索到终点时，返回到达该节点的路径，否则返回None表示无解。

python代码实现深度优先

以下是Python代码实现深度优先搜索算法的示例：

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

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

该算法的基本思想是从起始点开始，不断往他的下一层走，直到无法继续为止。然后回溯到上一个节点，再往他的下一层走，直到图中所有节点都被访问完为止。