是否可以使用广度优先搜索逻辑来进行拓扑排序的DAG？Cormen的解决方案使用深度优先搜索,但使用BFS会更容易吗？
原因:BFS在访问具有下一个深度值的节点之前访问特定深度的所有节点.这自然意味着如果我们做BFS,父母将被列在孩子面前.这不是我们拓扑排序所需要的吗？
Can Breadth first Search可用于查找图中顶点和强连通组件的拓扑排序吗？
如果是的话怎么做？如果不是为什么不呢？
我们通常在这些问题中使用深度优先搜索,但如果我尝试使用BFS实现会有什么问题？
这样的代码会起作用吗？
def top_bfs(start_node):
queue = [start_node]
stack = []
while not queue.empty():
node = queue.dequeue()
if not node.visited:
node.visited = True
stack.push(node)
for c in node.children:
queue.enqueue(c)
stack.reverse()
return stack
在 Sedgewick 和 Wayne 关于 java 算法的书中发现了以下问题：
4.2.19 拓扑排序和 BFS。解释为什么以下算法不一定会产生拓扑顺序：运行 BFS，并通过增加与各自源的距离来标记顶点。
我试图证明它找到一个反例。但是，每次我尝试时，都会得到一个拓扑顺序。我的意思是，我不明白为什么这不起作用：如果顶点的源在它之前，为什么我们没有拓扑顺序？
我想为了证明它，我们需要找到一个它的来源之前出现的顶点，但我不能。
有人有反例吗？提前致谢！
PS：这不是作业
@Edit：我尝试过像 1 <- 2 <- 0 <- 3 <- 4 这样的汉密尔顿路径，它给出 0 3 4 2 1，但是改变 0 3 和 4 的位置给了我一个拓扑顺序（但是，按照我获得的顺序，它不是）。我不确定这是否是拓扑顺序。