固定端を持つ有向グラフのサイクル依存性を削除する

Question

私は有向循環グラフを持っています。一部のエッジは固定されており、削除できません。他のエッジは、サイクルを壊すために除去することができる。

このグラフのサイクルを削除する最も良い方法は何ですか？ トラバーサルは、できるだけDFSにして、特定のノードから開始する必要があります。

Answer 1

私はすべての固定エッジのグラフで

スタート開始ノードから

を確認としてマークされ、すべての確認エッジを再帰と同様に：私の問題を解決するには、次のアルゴリズムを使用まだ確認されていないもの。しかし、まだ確認されていないエッジを再帰しようとするとき、エッジが行くノードに、確認されたエッジに続いて、現在の探索ツリーのノード（すなわち、訪問フラグが設定されています）。このチェックは確認されたすべてのエッジをたどって再帰的に実行する必要がありますが、これは遅すぎます。これは私のケースの大部分をカバーしますが、時折グラフにサイクルを残します。

上記の手順の後、私はTarjanのアルゴリズムを使用して、グラフに強く接続されたコンポーネントを見つけ出します（これはO（V + E）時間で実行できます）。私の場合、強く接続されたコンポーネントの数は非常に少ないので、強く接続されたコンポーネントを1つずつ抜き取り、1つの取り外し可能なエッジをそれぞれ取り除くだけです。グラフにサイクルがなくなるまで、このステップをやり直します。

これは正常に動作し、十分に速いです。

Answer 2

あなたができることはダイクストラのアルゴリズムを使用することです：固定端だけを含むグラフから始めます。

1. 開始ノードから開始し、開始ノードのコンポーネント内のすべての固定エッジを使用して開始します。これが木であると仮定してください。
2. ツリーに最も近いノードを追加します。
3. また、追加したばかりのノードのコンポーネントにFIXED辺を追加します。
4. すべてのノードがツリーにある場合は、終了します。それ以外の場合は、手順4に進みます。

もちろん、固定エッジのみで構成されるグラフにはサイクルが含まれていないと仮定します。そうであれば、解決策はありません（つまり、エッジのないサブグラフですが、すべての固定エッジが含まれています）。

有向グラフの場合、もう少し複雑です。この場合、FIXED辺のグラフのコンポーネントはツリーでなければなりません。 Dijkstraのようなアルゴリズムでは、これらのノードの根だけが木に追加されるべき候補でなければならない。

Answer 3

あなたが指定していないため、問題は控えめです。グラフを接続したままにする必要がある場合、またはすべてのサイクルを中断させるために「小さな」数の固定されていないエッジを削除したい場合、または削除する非固定エッジの数を実際に最低限必要な場合

グラフを接続したままにする必要がない場合は、すべてのエッジをトラバースして、固定されていないものをすべて削除してください。これにより、修正されたエッジを削除せずに削除できるすべてのサイクルが削除されます。

あなたは純粋DFSでエッジを除去するための簡単な貪欲なアルゴリズムを使用する場合は、グラフを使用して、非固定エッジの一部を削除するときにも接続されて残っている場合は、あなたがこのようなものを使用することができます。

proc recurse(vertex n, vertex_set ns) 
    if (n appers_in ns) // it is a cycle 
    return BREAK_CYCLE 
    else for (e in list_outgoing_edges_from(n)) 
    np = e.destination 
    result = recurse(np, add_to_set(ns, np)) 
    if (result == BREAK_CYCLE) 
     if (e.FIXED) 
     return BREAK_CYCLE 
     else 
     [remove e from the graph] 
     return RETRY 
     else if (result == RETRY) 
     return recurse(n, ns) 
    return FINISHED 

if (recurse (your_initial_node, empty_vertex_set())) 
    [graph contains a cycle through only FIXED edges] 
else 
    [the reachable component from initial_node has no longer cycles]