有向グラフ:「入口」が1つしかないエリアを見つけるアルゴリズムの高速化

c#
有向グラフ:「入口」が1つしかないエリアを見つけるアルゴリズムの高速化

私は、それぞれが指しているオブジェクトとそれが指しているオブジェクト(m:n)を知っているオブジェクトで構成される有向グラフを持っています。 開始ノードの1つのオブジェクトがあります。 入り口が1つしかないエリアを検索しています。 これらの領域には、ループや分岐などが含まれる場合があります。 唯一の条件は、1つの特定のノードを渡すことなく、外部からこれらのエリアに入ることができないということです。

この問題を解決する簡単なアルゴリズムを開発しました。

foreachノードがブランチにビーイング+ \ {+現在のノードから到達可能なすべてのノードにマークを付けます+マークされたノードがマークされていないすべてのノードをマーク解除します。

問題は、実際には非常に遅くなり、多くのブランチを持つ1000以上のノードがあるため、プログラムが数秒間ほどフリーズし、デバッガを使用して停止すると、この特定のアルゴリズムが常に実行されます。 これは特別な場合に問題になりますが、自動化するため、高速にしたいです。

5ノードの後に​​再結合する開始時にブランチがある場合、最初の995ノードがマークされ、990が再びマーク解除されるため、パフォーマンスの低下はそれほど驚くことではありません。 :(しかし、私はより良い考えを持っていません。

この問題をより速く解決する方法はありますか?

グラフについての情報:ほとんどのノード(約80%)は、ちょうど1つの先行ノードと1つの後続ノードを持つ単なるリンクですが、後で必要になるため、これらを破棄することは非常に悪い考えです。 また、メモリ内のオブジェクトを使用しているため、若干の変更(リンクノードの交換、削除、追加)があります。

  1  2


ベストアンサー

私があなたの状況を正しく理解していれば、グラフ理論でhttp://en.wikipedia.org/wiki/Articulation_point[articulation point]または_cut vertex_と呼ばれるものを探しています。 リンクされているウィキペディアのページでは、このようなポイントを検出するための非常に効率的なアルゴリズムについて説明しています。 アルゴリズムはhttp://en.wikipedia.org/wiki/Depth-first_search[depth-first search]に基づいていることに注意してください。アルゴリズムを実装する場合は、十分に理解する必要があります。 また、グラフに数千のノードが含まれている場合、再帰的ではなくスタックを使用して深さ優先検索を繰り返し実装する必要があります(これは標準的な実装方法です)-そうでない場合、プログラムはおそらくスタックオーバーフローを引き起こします大きなグラフが与えられた。

1


タイトルとURLをコピーしました