トポロジカル検索と幅優先検索

Question

広範な最初の検索ロジックを使用して、DAGのトポロジカルな並べ替えを実行できますか？ Cormenのソリューションは、Depth first searchを利用していますが、BFSを使用するのは簡単ではありませんか？

理由： BFSは、次の深度値を持つノードにアクセスする前に、特定の深さのすべてのノードを訪問します。それは当然、BFSを行う場合、両親が子供の前にリストされることを意味します。これは正確にトポロジカルなソートに必要なものではありませんか？

Answer 1

BFSでは実際に歩いているエッジはすべて正しい方向になります。しかし、BFSの順序でグラフをレイアウトすると、あなたが歩いていないエッジ（同じ深さにあるノード間のノードや、より深いノードから元のノードに戻るノード）が間違った方向に向かうことになります。

はい、本当にDFSを実行する必要があります。

Answer 2

ウィキペディアでも可能です。describes an algorithm based on BFS。

基本的に、受信エッジのないすべてのノードを挿入するキューを使用します。次に、ノードを抽出すると、すべての送信エッジを削除し、そこから到達可能なノードを挿入し、他の受信エッジがないノードを挿入します。

Answer 3

、木（の森）で中度は、このような場合を見て、今ではほとんど1 であるため、単なるBFSは、ツリー（または木の森）のためだけで十分です：

B → C → D 
     ↗ 
    A 

キューがA B（度数がゼロ）に初期化されるBFSは、A B D Cを返します。これはトポロジカルにソートされません。だからあなたは度数を維持しなければならず、カウントがゼロになったノードだけを選ぶだけです。 （*）

これはあなたの「理由」の欠陥です：BFSは、1人の親が以前に訪問されたことを保証するだけで、すべてではありません。

編集：（*）は、中度（exempleに、Aを処理した後、Dをスキップするであろう）がゼロである隣接ノードを押し戻す言い換えます。したがって、あなたはまだキューを使用しており、一般的なアルゴリズムにフィルタリング・ステップを追加したばかりです。それは、それをBFSと呼ぶことを続けていると疑わしいです。

Answer 4

はい、BFSを使用してトポロジカルソートを行うことができます。実際に私の先生は、問題がBFSで解決できる場合は、DFSで決して解決しないと教えてくれたことを思い出しました。 BFSのロジックはDFSよりも簡単なので、ほとんどの場合、問題の解決方法は常に簡単になります。

YvesgereYとIVladは言及したように、あなたは入次数は彼らに直接他のノードを意味しない、となっているノードで起動する必要があります。最初に結果にこれらのノードを追加してください。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; 
}