python - 如何在Python上非递归地实现有向图的广度优先搜索

Question

我正在尝试实现一个 BFS 函数，该函数将打印使用广度优先搜索遍历访问的有向图的节点列表。该函数必须以非递归方式实现，并且必须遍历图中的所有节点，因此如果有多棵树，它将按以下方式打印:

树 1:a、b

树 2:d、e、h

树 3:......

我的主要困难是理解如果图有几棵树，如何使 BFS 函数遍历所有节点，而不重新打印以前访问过的节点。

Answer 1

为了简单起见，您可以使用队列非递归地执行 BFS。这里需要两个数据结构。

1. 维护 BFS 顺序的队列。
2. 列出项目哈希表(或集合)以查找重复项。

这是算法:

1. 将图形上的初始点放入队列中，并将哈希表。
2. 如果队列不为空
   1. 从队列中出列。
   2. 将出队元素的所有邻居加入队列，如果集合中尚不存在，则将它们插入集合中。
   3. 打印(/access/process)出列的元素。
3. 重复步骤 2 到 4，直到队列耗尽。

您可以在网上找到很多示例和优化。例如:

https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

https://en.wikipedia.org/wiki/Breadth-first_search