BFS与拓扑排序的关系 [英] Relationship between BFS and topological sort

问题描述

拓扑排序可以使用 DFS(边缘反转)和队列来完成.BFS 也可以使用队列来完成.使用队列进行 BFS 时元素的存储和检索方式与使用队列进行拓扑排序时的元素存储和检索方式之间是否存在任何关系.澄清会有所帮助.谢谢.

Topological sort can be done using both a DFS(having edges reversed) and also using a queue . A BFS can also be done using a queue . Is there any relationship between the way elements are stored and retrieved while using queue for a BFS to that when used a queue for topological sorting . Clarification will be helpful . Thanks.

推荐答案

BFS 从源节点开始逐层遍历，使得节点按照离源的距离的顺序出现，这也意味着父节点出现在子节点之前位于下一级的节点.

The level by level traversal of BFS from a source node makes the nodes appear in the order of their distance from source which also means that parent nodes appear before their children nodes which are in the next level.

这可能看起来像我们在拓扑排序中需要的东西，但是，请留在我身边.上一句中的 next level 是关键，因为如果一个节点和它的子节点与源处于同一级别，那么 BFS 在遍历它们时不强制执行任何顺序，这意味着它可能在它自己之前呈现节点的子节点这将直接违反拓扑排序规则，当我们想要拓扑排序时，排序确实很重要.

This might appear like what we need in a topological sort, however, stay with me. The next level in the previous sentence is the key, because if a node and its child are in the same level from source, then BFS enforces no order in traversing them meaning it may present the node's child before itself and this will be a direct violation to the rule of topological sort and the ordering is indeed important when we want a topological sort.

虽然看起来BFS和拓扑排序之间有关系，但关系很弱.

Although it seems like there is a relationship between BFS and topological sort, it is rather weak.

这篇关于BFS与拓扑排序的关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！