使用BFS进行拓扑排序

Question

Can Breadth first Search可用于查找图中顶点和强连通组件的拓扑排序吗？

如果是的话怎么做？如果不是为什么不呢？

我们通常在这些问题中使用深度优先搜索,但如果我尝试使用BFS实现会有什么问题？

这样的代码会起作用吗？

def top_bfs(start_node):
    queue = [start_node]
    stack = []
    while not queue.empty():
        node = queue.dequeue()
        if not node.visited:
            node.visited = True
            stack.push(node)
            for c in node.children:
                queue.enqueue(c) 
    stack.reverse()
    return stack

Answer 1

是的,您可以使用BFS进行拓扑排序.实际上我记得有一次,我的老师告诉我,如果问题可以通过BFS解决,永远不要选择通过DFS解决.因为BFS的逻辑比DFS简单,所以大多数时候您总是希望直接解决问题.

您需要从indegree为0的节点开始,这意味着没有其他节点指向它们.请务必先将这些节点添加到结果中.您可以使用HashMap映射每个节点的indegree,以及一个在BFS中常见的队列,以帮助您进行遍历.当您从队列中轮询节点时,其邻居的indegree需要减少1,这就像从图中删除节点并删除节点与其邻居之间的边缘.每次遇到具有0 indegree的节点时,请将它们提供给队列以便稍后检查其邻居并将它们添加到结果中.

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;
}

Answer 2

它们具有相似的名称这一事实并不会使它们具有相似的方法。

DFS通常是通过LIFO（如果需要的话，是一个堆栈）实现的-后进先出。

BFS通常使用FIFO（如果需要的话，是一个队列）实现-先进先出。

您可以按照任意方式遍历图，最终得出其节点的拓扑顺序。但是，如果您想高效地进行操作，则DFS是最佳选择，因为节点的拓扑顺序实质上反映了它们在图中的深度（当然，“依赖深度”更为准确）。