使用 bfs 的拓扑顺序

Question

在 Sedgewick 和 Wayne 关于 java 算法的书中发现了以下问题：

4.2.19 拓扑排序和BFS。解释为什么下面的算法不一定产生拓扑序：运行 BFS，和label通过增加到各自源的距离来增加顶点。

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

我想证明它，我们需要找到它的源之前出现的顶点，但我找不到。

谁有反例？提前致谢！

PS:这不是作业

@Edit: 我试过像 1 <- 2 <- 0 <- 3 <- 4 这样的汉密尔顿路径，它给出了 0 3 4 2 1，但是改变了0 3 和 4 的位置给了我一个拓扑顺序（但是，按照我获得的顺序，它不是）。那我也不确定这是不是拓扑序

Answer 1

不能使用 BFS，因为等级较高的节点可能有等级较低的入射边。这是一个例子：

假设您在源 (A) 处启动 BFS。

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

Answer 2

反例：

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

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

Answer 3

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

您需要从度数为 0 的节点开始，这意味着没有其他节点指向它们。请务必将这些节点添加到您的结果中 first.You 可以使用 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;
}

使用 bfs 的拓扑顺序

Topological order using bfs

algorithm

breadth-first-search

topological-sort