拓扑为了使用BFS

以下问题在塞奇威克和韦恩本书算法被发现在Java中：拓扑为了使用BFS

4.2.19拓扑排序和BFS。解释为什么以下算法不一定会产生拓扑顺序：运行BFS，并通过增加到它们各自源的距离来标记顶点。

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

我认为要证明这一点，我们需要找到一个其来源之前的顶点，但我不能。

任何人都有反例吗？提前致谢！

PS：这不是功课

@Edit：我试图样1 <的哈密尔顿路径 - 2 < - 0 < - 3 < - 4，它给出0 3 4 2 1 ，但改变0 3和4的位置给了我一个拓扑顺序（但是，按照我得到的顺序，它不是）。那么我不确定这是否是一种拓扑顺序。

来源

2015-06-16 Giiovanna

您不能使用BFS，因为具有较高排名的节点可能具有较低排名的事件边缘。这里有一个例子：

假设你在源（A）处启动BFS。 DAG

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

来源

2015-06-16 14:16:24 adao7000

rank是什么定义？我只知道树木的等级。而且，如果D出现在A的邻接列表上，那么D可能会出现在C之前，对吗？ – Giiovanna

Rank可以被认为是一个节点在BFS中处理的“级别”。 A会有1级，B和D会有2级，等等。 – adao7000

好的，非常感谢！ – Giiovanna

-2

反例：

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

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

来源

2015-06-16 14:17:14

是的，你可以做拓扑排序使用BFS。其实我记得有一次我的老师告诉我，如果问题可以通过BFS解决，千万别选择通过DFS解决。因为BFS的逻辑比DFS简单，大多数情况下您总是需要一个直接解决问题的方法。

你需要开始与节点其中入度是，这意味着没有其他节点直接到他们。请务必首先将这些节点添加到结果中。您可以使用HashMap将每个节点与它的indegree进行映射，并使用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; 
}

来源

2017-07-08 13:04:29

拓扑为了使用BFS

回答

相关问题