12

是否可以使用广度优先搜索逻辑来进行 DAG 的拓扑排序？Cormen 中的解决方案使用深度优先搜索，但使用 BFS 会不会更容易？

原因：BFS 在访问具有下一个深度值的节点之前，先访问特定深度的所有节点。这自然意味着如果我们做 BFS，父母会排在孩子之前。这不正是我们对拓扑排序所需要的吗？

4

4 回答 4

8

仅仅 BFS 仅对一棵树（或森林的森林）就足够了，因为在树的森林中，入度最多为 1。现在，看看这个案例：

B → C → D
      ↗
    A

队列初始化为A B（入度为零）的 BFS 将返回A B D C未进行拓扑排序的 BFS。这就是为什么您必须保持入度计数，并且只选择计数已降至零的节点。(*)

顺便说一句，这是你的“原因”的缺陷：BFS 只保证之前拜访过一位父母，而不是全部。

编辑：（*）换句话说，您推回度数为零的相邻节点（在示例中，在处理之后A，D将被跳过）。因此，您仍在使用队列，并且刚刚在通用算法中添加了过滤步骤。话虽如此，继续称它为 BFS 是有问题的。

于 2016-02-17T13:33:46.713 回答
4

有可能，甚至维基百科都描述了一种基于 BFS 的算法。

基本上，您使用一个队列，在其中插入所有没有传入边的节点。然后，当您提取一个节点时，您删除它的所有出边并插入从它可到达且没有其他入边的节点。

于 2013-02-16T10:41:51.973 回答
3

在 BFS 中，您实际行走的所有边缘最终都会朝着正确的方向。但是，如果您按 BFS 顺序布置图形，那么您不走的所有边（位于相同深度的节点之间的边，或从较深节点返回到较早节点的边）最终都会走错路。

是的，你真的需要 DFS 来做到这一点。

于 2013-02-16T06:51:45.303 回答
0

是的，您可以使用BFS进行拓扑排序。其实我记得有一次我的老师告诉我，如果问题可以通过BFS解决，永远不要选择通过DFS解决。因为BFS的逻辑比DFS更简单，所以大多数时候你总是想要一个简单的解决方案来解决问题。

正如 YvesgereY 和IVlad所提到的，您需要从入度为0的节点开始，这意味着没有其他节点直接指向它们。请务必先将这些节点添加到您的结果中。您可以使用 HashMap 来映射每个节点及其入度，并使用 BFS 中非常常见的队列来帮助您遍历。当您从队列中轮询一个节点时，其邻居的入度需要减少 1，这就像从图中删除该节点并删除该节点与其邻居之间的边一样。每次遇到度数为 0 的节点时，将它们提供给队列以便稍后检查其邻居并将它们添加到结果中。

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {

    ArrayList<DirectedGraphNode> result = new ArrayList<>();
    if (graph == null || graph.size() == 0) {
        return result;
    }
    Map<DirectedGraphNode, Integer> indegree = new HashMap<DirectedGraphNode, Integer>();
    Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();

    //mapping node to its indegree to the HashMap, however these nodes
    //have to be directed to by one other node, nodes whose indegree == 0
    //would not be mapped.
    for (DirectedGraphNode DAGNode : graph){
        for (DirectedGraphNode nei : DAGNode.neighbors){
            if(indegree.containsKey(nei)){
                indegree.put(nei, indegree.get(nei) + 1);
            } else {
                indegree.put(nei, 1);
            }
        }
    }


    //find all nodes with indegree == 0. They should be at starting positon in the result
    for (DirectedGraphNode GraphNode : graph) {
        if (!indegree.containsKey(GraphNode)){
            queue.offer(GraphNode);
            result.add(GraphNode);
        }
    }


    //everytime we poll out a node from the queue, it means we delete it from the 
    //graph, we will minus its neighbors indegree by one, this is the same meaning 
    //as we delete the edge from the node to its neighbors.
    while (!queue.isEmpty()) {
        DirectedGraphNode temp = queue.poll();
        for (DirectedGraphNode neighbor : temp.neighbors){
            indegree.put(neighbor, indegree.get(neighbor) - 1);
            if (indegree.get(neighbor) == 0){
                result.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    return result;
}
于 2017-07-08T12:52:15.457 回答