人工智能宽度优先搜索例题

宽度优先搜索（Breadth-First Search, BFS）是一种用于图遍历的算法。它从图的某一顶点开始，沿着边的宽度方向进行搜索，直到找到目标顶点或搜索完所有可达顶点为止。

下面是一个使用Python实现宽度优先搜索的示例：

```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)

print(vertex, end=" ")

for neighbor in graph[vertex]:

if neighbor not in visited:

queue.append(neighbor)

# 示例图

graph = {

'A': ['B', 'C'],

'B': ['D', 'E'],

'C': ['F'],

'D': [],

'E': ['F'],

'F': []

}

bfs(graph, 'A')

```

在这个示例中，我们首先定义了一个名为`bfs`的函数，它接受一个图（表示为邻接表）和一个起始顶点作为输入。我们使用一个集合`visited`来记录已访问过的顶点，以防止重复访问。我们还使用一个双端队列`queue`来存储待访问的顶点。

接下来，我们使用一个循环来执行宽度优先搜索。在每次迭代中，我们从队列中弹出一个顶点，并检查它是否已经被访问过。如果没有被访问过，我们将它添加到`visited`集合中，并打印出它的所有邻居。然后，我们将未访问的邻居添加到队列中。

最后，我们使用一个示例图来测试我们的宽度优先搜索函数。在这个图中，顶点A连接到顶点B、C和F，顶点B连接到顶点D和E，顶点C只连接到顶点F，而顶点D和E都没有其他连接。运行这段代码将输出以下结果：

```

A B C F

A B D E

```

这表明我们已经成功地找到了从顶点A出发的所有可达顶点。