如何在python上非递归地实现有向图的广度优先搜索
我正在尝试实现一个BFS函数，它将打印一个使用广度优先搜索遍历访问的有向图的节点列表。该函数必须以非递归方式实现，并且必须遍历图中的所有节点，因此，如果有多个树，它将以下列方式打印:
树1: a，b
树 2：d、e、h
树 3： .....
我的主要困难是理解如果图形有多棵树，如何使BFS函数遍历所有节点，而不重新打印以前访问过的节点。
共有2个答案
BFS通常使用队列完成。当您处理一个节点时，您将其子级推送到队列中。处理完节点后，您处理队列中的下一个。
这本质上是非递归的。
为了简单起见，您可以使用队列来非递归地执行BFS。这里需要两种数据结构。
- 用于维护 BFS 顺序的队列。
- 列表项哈希表（或集）以查找重复项。
这是算法：
- 将图形上的初始点排队到队列中，同时也排入哈希表。
- 如果队列不为空
- 从队列中取消排队。
- 将已取消排队元素的所有邻居排队到队列中，如果它们尚不存在于集合中，则将它们插入到集合中。
- 打印（/访问/处理）已取消排队的元素。
您可以在线找到许多示例和优化。例如：
https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
https://en.wikipedia.org/wiki/Breadth-first_search
-
我正在尝试在有向图上实现BFS。我完全确定我的算法是正确的，但是，下面的代码段返回错误： 图表。CPP文件: 以及在以下方面的实际BFS实施： 因此，除了源节点之外，队列中的其他节点都给出了错误的邻接列表。虽然队列顺序运行良好，但队列中的节点给出了错误的邻接。 我不确定为什么会发生这种情况，虽然我怀疑这是由于按值复制节点而不是引用。 这是我在很长一段时间后的CPP计划，所以如果我错过了什么，请启发
-
在这篇文章中，biziclop为非递归深度优先搜索算法插入了伪代码。 如果我们想使用递归DFS算法来检查节点的适当性，我们可以利用两个变体：pre-order（当一个节点在其子节点之前检查时）和post-order（当子节点在节点之前检查时），加上仅针对二叉树的第三个变体（顺序：左子树，然后节点，然后右子树）。 如果可能的话，我对这三个变体都很感兴趣，所以我试图修改biziclop的伪代码，以便获
-
通过构建图，我们现在可以将注意力转向我们将使用的算法来找到字梯问题的最短解。我们将使用的图算法称为“宽度优先搜索”算法。宽度优先搜索（BFS）是用于搜索图的最简单的算法之一。它也作为几个其他重要的图算法的原型，我们将在以后研究。 给定图 G 和起始顶点 s，广度优先搜索通过探索图中的边以找到 G 中的所有顶点，其中存在从 s 开始的路径。通过广度优先搜索，它找到和 s 相距 k 的所有顶点，然后找
-
在有向图上进行广度优先搜索时，我很难找到一种正确分类边的方法。 在广度优先或深度优先搜索过程中,可以将遇到的边缘分为4类： 树 后退 交叉 转发 但普通循环不起作用： 当最后交叉边eCA时，处理并发现A。所以这个边被错误地标注为十字，是否应该是一个后边。 这两种情况的处理方式确实没有区别，即使这两种边缘有不同的类别。
-
在由具有指向父节点、兄弟节点和第一个/最后一个子节点的节点表示的通用树中，如: 是否可以在不使用任何其他帮助程序结构（如队列）的情况下执行迭代（非递归）广度优先（级别顺序）遍历。 所以基本上：我们可以使用单节点引用进行回溯，但不能保存节点集合。它是否能够完成是理论上的一部分，但更实际的问题是，它是否能够在不回溯大片段的情况下高效地完成。