博客

python实现广度优先搜索过程解析

  • Post category:Python

Python实现广度优先搜索的过程，需要经过以下几个步骤：

步骤一：初始化

广度优先搜索需要一个FIFO (先进先出) 的队列来存储待搜索的节点，需要将起始节点放入队列中，并标记该节点已被访问，同时初始化访问过的节点集合。

start = 'A'
visited = {start}
queue = [start]

步骤二：循环遍历队列

从队列的头部取出一个节点，检查该节点是否为目标节点，如果是，则搜索结束；否则遍历该节点的所有相邻节点，将未被访问过的相邻节点加入队列中，并将其标记为已访问的节点。

while queue:
    node = queue.pop(0)
    if node == goal:
        print("Search success")
        break
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

步骤三：构建图谱

广度优先搜索需要一个图谱表示节点之间的关系，可以用字典结构实现，其中节点是键，值是该节点的所有邻居。

graph = {'A': ['B', 'C'],
         'B': ['D', 'E'],
         'C': ['F', 'G'],
         'D': [],
         'E': ['F'],
         'F': [],
         'G': []}

下面通过两个示例来说明：

示例一

假设有如下无向图：

A -- B -- D
|    |    |
C    E -- F
|         |
G         H

如果我们要从节点A开始搜索到节点F，那么搜索过程如下：

  1. 初始化：将A节点放入队列queue中，并标记为已访问visited
visited = {'A'}
queue = ['A']
  1. 从队列头部取出A；
  2. 查看其所有相邻节点，B和C，将B加入队列queue中，同时将B标记为已访问visited
queue = ['B']
visited = {'A', 'B'}
  1. 从队列头部取出B；
  2. 查看其所有相邻节点，D和E，将D加入队列queue中，同时将D标记为已访问visited
queue = ['C', 'D']
visited = {'A', 'B', 'D'}
  1. 从队列头部取出C；
  2. 查看其所有相邻节点，F和G，将F加入队列queue中，同时将F标记为已访问visited
queue = ['D', 'F']
visited = {'A', 'B', 'D', 'C', 'F'}
  1. 从队列头部取出D；
  2. 查看其所有相邻节点，无，queue不变
queue = ['F']
visited = {'A', 'B', 'D', 'C', 'F'}
  1. 从队列头部取出F；
  2. 查看其所有相邻节点，无，queue不变
queue = []
visited = {'A', 'B', 'D', 'C', 'F'}
  1. 搜索结束，目标节点F已找到

示例二

假设有如下有向图：

start -> A -> B -> D
   |              ^
   v              |
   C -----> E ----/
   |
   v
   goal

如果我们要从节点start开始搜索到节点goal，那么搜索过程如下：

  1. 初始化：将start节点放入队列queue中，并标记为已访问visited
visited = {'start'}
queue = ['start']
  1. 从队列头部取出start；
  2. 查看其所有相邻节点，A和C，将A和C加入队列queue中，同时将A和C标记为已访问visited
queue = ['A', 'C']
visited = {'start', 'A', 'C'}
  1. 从队列头部取出A；
  2. 查看其所有相邻节点，B，将B加入队列queue中，同时将B标记为已访问visited
queue = ['C', 'B']
visited = {'start', 'A', 'C', 'B'}
  1. 从队列头部取出C；
  2. 查看其所有相邻节点，E，将E加入队列queue中，同时将E标记为已访问visited
queue = ['B', 'E']
visited = {'start', 'A', 'C', 'B', 'E'}
  1. 从队列头部取出B；
  2. 查看其所有相邻节点，D，将D加入队列queue中，同时将D标记为已访问visited
queue = ['E', 'D']
visited = {'start', 'A', 'C', 'B', 'E', 'D'}
  1. 从队列头部取出E；
  2. 查看其所有相邻节点，无，queue不变
queue = ['D']
visited = {'start', 'A', 'C', 'B', 'E', 'D'}
  1. 从队列头部取出D；
  2. 查看其所有相邻节点，无，queue不变
queue = []
visited = {'start', 'A', 'C', 'B', 'E', 'D'}
  1. 搜索结束，目标节点goal未被访问到
Tags: ,