2

データベース内のテーブル間のいくつかの依存関係をソートするソース削除アルゴリズムを作成しましたが、サイクルがあることがわかりました。簡単にするために、テーブル A、B、C、および D があるとします。エッジは次のようになります。

(A, B)
(B, A)
(B, C)
(C, D)
(D, A)

ご覧のとおり、ここには 2 つのサイクルがあります。1 つは A と B の間にあり、もう 1 つは 4 つすべての間にあります。このタイプの並べ替えは、常に最大のサイクルで停止しますか? それとも必ずしもそうとは限りませんか？

4

2 に答える 2

5

ソースの削除とは、各ステップで入力エッジのないノードを削除することを意味すると思います。

あなたが求めているのは、グラフの最大のオイラーツアーを見つけることです（つまり、ノードを繰り返すことができる一方で、固有のエッジを持つサイクル）。

明らかに、サイクル内の頂点を削除することはできません（サイクル内の頂点がゼロの入力エッジを持つことはありません）ので、このアルゴリズムは確かにすべてのサイクル（および最大）を保持しますが、それでも、残りの部分を見つけるのに役立ちませんエッジがサイクルの一部であるとは限りません（説明するアルゴリズムがすべてのエッジを保持する例を簡単に作成できますが、最大のサイクルはサイズ2であるため、後者を見つけるのにあまり役立ちません）。

代わりにこれを行う方法は次のとおりです。

バックエッジ、つまりトラバーサルで、訪問先ノードの祖先（訪問先ノードのエッジによって初めて誘導されるDFSツリー内）を指すエッジを認識することに関心があります。たとえば、DFSスタックにノード[A-> B-> C-> D]があり、Dを探索しているときに、エッジD-> Bが見つかった場合、それはバックエッジです。各バックエッジはサイクルを定義します。

さらに重要なことに、バックエッジによって引き起こされるサイクルは、グラフの基本的なサイクルのセットです。「サイクルの基本セット」：基本セットのサイクルをUNIONおよびXORするだけで、グラフのすべてのサイクルを作成できます。たとえば、[A1-> A2->A3->A1]および[A2->B1->B2->B3->A2]のサイクルについて考えてみます。それらを次のサイクルに結合できます：[A1-> A2-> B1-> B2-> B3-> A2->A3->A1]。最大のサイクルが必要なので、XORを考慮する必要はありません。

  • ノードで交差するすべての基本サイクルをUNIONすることにより、最大サイクルを構築します。（注意深く行うと、これも線形の時間計算量になるはずです）。

一方、頂点を繰り返さない最大サイクルが必要な場合は、線形よりもはるかに困難になります:)

于 2010-04-06T22:19:50.250 に答える
0

ソース削除アルゴリズム (ディミトリスのように、依存関係のないノードを一度に 1 つずつ削除することを意味すると思います) は、どのサイクルでも停止します。実際、アルゴリズムはサイクルに依存しないすべてのノードを削除し、残ったノードはサイクルの一部であるか、サイクルの一部であるノードに依存します。

これらのサイクルは強連結成分とも呼ばれ、各サイクルを単一のノードに置き換えると、DAG になります。

于 2010-11-11T18:47:32.753 に答える