使用BFS进行拓扑排序

是的,您可以使用 BFS公司 事实上,我记得有一次我的老师告诉我,如果这个问题可以通过 BFS公司 ,永远不要选择通过 分布式系统 。因为 BFS公司 比 分布式系统 ,大多数情况下,您总是想要一个简单的问题解决方案。

您需要从节点开始 不同意,不同意 是 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;
}

事实上,它们有相似的名称并不能使它们的方法相似。

DFS通常使用后进先出(LIFO,如果你愿意的话,是一个堆栈)来实现——后进先出。

BFS通常使用FIFO(如果您愿意,可以使用队列)实现-先进先出。

你可以用你想要的任何方式遍历一个图,最终得到它的节点的拓扑顺序。但如果您想高效地执行此操作,那么DFS是最好的选择,因为节点的拓扑顺序基本上反映了它们在图中的深度(更准确地说是“依赖深度”)。

因此,通常情况下,使用DFS(深度优先搜索)进行拓扑排序的代码要简单得多,您运行它,它会在调用之前的堆栈帧时进行递归赋值,从而进行回溯。BFS不那么直截了当,但仍然很容易理解。

首先,必须计算图形上所有顶点的度数,这是因为必须从度数为0的顶点开始。

    int[] indegree = int[adjList.length];
    for(int i = 0; i < adjList.length; i++){
        for(Edge e = adjList[i]; e != null; e = e.next){
          indegree[e.vertexNum]++;
        }
      }

因此,上面的代码遍历顶点数组,然后遍历单个顶点的边(在本例中是使用链接列表存储的),然后递增边在非顶点数组中指向的顶点。因此,在外循环结束时,您将遍历每个顶点的邻居,并计算每个顶点的度数。

第二,您现在必须使用BFS对该图进行拓扑排序。因此,第一段代码将只对图中度数为0的顶点进行排队。

    Queue<Integer> q = new Queue<>();
    for(int i = 0; i < indegree.length; i++){
      if(indegree[i] == 0){
        q.enqueue(i);
      }
    }

现在,在只对阶数为0的顶点进行排队之后,开始循环以指定拓扑数。

    while(!q.isEmpty()){
      int vertex = q.dequeue();
      System.out.print(vertex);
      for(Edge e = adjList[vertex]; e != null; e = e.next){
        if(--indegree[e.vnum] == 0){
          q.enqueue(e.vnum);
        }
      }

因此,print语句打印出与顶点对应的顶点编号。因此,根据程序的要求,您可以将print语句所在的代码更改为存储顶点编号或名称的代码,或者沿着这些行的代码。除此之外,我希望这有助于回答第一个问题。

第二个问题

至于问题的第二部分,很简单。

1.创建填充了假值的布尔数组,这将表示顶点是否已访问。

2.在adjList数组上迭代创建for循环,在这个循环中,您将调用bfs,在调用bfs之后,您将迭代您创建的布尔数组,检查是否有任何值为false,如果为false,则该图不是强连接的,您可以返回“graph is not strong connected”并结束程序。在外部for循环的每次迭代结束时(但在内部for循环之后),不要忘记再次将布尔数组重置为所有假值。

3.此时,外部for循环完成,您可以返回true,您的任务是实现bfs,它应该采用整数和您创建的访问布尔数组作为参数。