拓扑搜索和广度优先搜索

Question

使用广度优先搜索算法对有向无环图（DAG）进行拓扑排序是否可行？

Cormen的解决方案中使用了深度优先搜索，但使用BFS（广度优先搜索）不是更容易吗？

原因： BFS在访问下一个深度值的节点之前会遍历当前深度的所有节点。这自然意味着，如果我们使用BFS，则父节点将在子节点之前列出。这难道不正是我们需要的拓扑排序吗？

- Karthik N

---

可以的，可以使用BFS进行拓扑排序。 - Number945

相关帖子 - 使用 BFS 进行拓扑排序，使用 BFS 进行拓扑排序 和BFS 与拓扑排序的关系。 - RBT

Answer 1

仅使用BFS算法只足以处理树（或树林），因为在树（林）中，入度最多为1。

现在，看看这个情况：

B → C → D
      ↗
    A

一个BFS，其中队列初始化为A B（其入度为零），将返回A B D C，这不是拓扑排序。这就是为什么您必须维护入度计数，并且只选择计数降至零的节点。 (*)

顺便说一句，这是您“reason”的缺陷：BFS只保证已访问一个父节点，而不是所有父节点。

(*) 换句话说，您将推回入度为零的相邻节点（在此示例中，在处理完A后，将跳过D）。因此，您仍在使用队列，并向通用算法添加了过滤步骤。话虽如此，继续称其为BFS是值得商榷的。

- YvesgereY

Answer 2

即使维基百科描述了一种基于BFS的算法，这也是可能的。

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

- IVlad

Answer 3

在BFS中，您实际走过的所有边都会以正确的方向结束。但是，您不走的所有边（那些在相同深度的节点之间或从较深的节点返回到先前节点的边）将在按BFS顺序布局图形时朝错误的方向移动。

是的，您确实需要使用DFS来完成这个任务。

- Keith Randall

---

看一下这个链接：https://www.quora.com/Can-topological-sorting-be-done-using-BFS - Number945

Answer 4

是的，你可以使用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;
}

- Caiwei Wu