固定エッジを持つ有向グラフのサイクル依存関係を削除する

StackOverflow https://stackoverflow.com/questions/1006071

質問

有向巡回グラフがあります。一部のエッジは固定されており、削除できない場合があります。サイクルを中断するために、他のエッジを削除できます。

このグラフのサイクルを削除する最良の方法は何ですか？ トラバーサルは可能な限りDFSで、指定されたノードから開始する必要があります。

役に立ちましたか？

解決 3

次のアルゴリズムを使用して問題を解決しました：

確認済み

としてマークされたすべての固定エッジのグラフから始めます

開始ノードから、未確認のエッジだけでなく、確認済みのすべてのエッジを再帰処理します。しかし、まだ確認されていないエッジを再帰しようとしている場合、最初に、確認されたエッジをたどって、現在の検索ツリーのノード（つまり、< em> visiting フラグが設定されています）。この確認は、確認されたすべてのエッジを追跡することによって再帰的に実行する必要がありますが、これは私にとって遅すぎるので、ここでノードが訪問しているか、または接続が確認されたノードのいずれかが訪問しているかどうかを確認します。これは私のケースのほとんどをカバーしますが、グラフにサイクルを残すことがあります。

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

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

他のヒント

できることは、ダイクストラのアルゴリズムを使用することです。FIXEDエッジのみを含むグラフから始めます。次に、すでに持っているグラフから始めて、アルゴリズムの適応を適用します。

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

もちろん、これは、FIXEDエッジのみで構成されるグラフにサイクルが含まれていないことを前提としています。存在する場合、解決策はありません（つまり、エッジのないサブグラフですが、すべての修正されたエッジを含みます）。

有向グラフの場合、もう少し複雑です。この場合、FIXEDエッジのグラフのコンポーネントはツリーでなければなりません。ダイクストラのようなアルゴリズムでは、これらのノードのルートのみがツリーに追加される候補になります。

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

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

単純な欲張りアルゴリズムで純粋な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]
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top