使用BFS进行拓扑排序

Question

以下问题来自Sedgewick和Wayne关于Java算法的书籍：

4.2.19 拓扑排序和BFS。

解释为什么以下算法不一定产生拓扑排序：运行BFS，并按照到各自源点的距离递增标记顶点。

我试图通过寻找反例来证明它。但是，每次尝试时，我都得到一个拓扑排序。 我的意思是，我不明白为什么这样不起作用：如果顶点的源在它之前，为什么我们没有拓扑排序？

我认为为了证明它，我们需要找到一个源在其之前的顶点，但我找不到。

有人有反例吗？谢谢！

注：这不是作业

@编辑：我尝试了一个类似哈密顿路径的1 <- 2 <- 0 <- 3 <- 4，这给出了0 3 4 2 1，但改变0 3和4的位置会给我一个拓扑排序（但按照我得到的顺序，它不是）。 我不确定这是否是拓扑排序。

- Giiovanna

---

相关帖子 - 使用BFS进行拓扑排序，拓扑搜索和广度优先搜索以及BFS和拓扑排序之间的关系。 - RBT

Answer 1

你不能使用BFS，因为一个排名更高的节点可能与一个排名更低的节点存在关联边。这里有一个例子：

假设你从源点（A）开始BFS。

按照你提出的算法，节点D会在节点C之前出现，这显然不是一个拓扑排序。你真的必须使用DFS。

- adao7000

---

什么是rank的定义？我只知道树的rank。而且，如果D首先出现在A的邻接表中，它可以排在C之前，对吗？ - Giiovanna

排名可以被视为 BFS 中处理节点的“层级”。A 的排名为 1，B 和 D 的排名为 2，依此类推。 - adao7000

@Giiovanna 如果这个解决方案对您有用，请接受答案。这样其他人就会知道答案是正确的。 - adao7000

Answer 2

反例：

A -> B
A -> C
B -> C

从A开始的BFS可以按顺序找到节点A-B-C或A-C-B，但只有其中一个是拓扑排序。

- Peter Taylor

Answer 3

是的，你可以使用BFS进行拓扑排序。实际上我记得我的老师曾经告诉过我，如果问题可以通过BFS解决，永远不要选择用DFS来解决它。因为BFS的逻辑比DFS简单，大多数情况下你总是想要一个直接的解决方案。

你需要从入度为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