1

グラフに対して深さ優先検索を実行しながら、ダイヤモンドの依存関係を確認する方法について誰かがいくつかの指針を提供できるかどうか疑問に思っていました...次のグラフがありますA -> B, A -> F, B -> C, B-> E, C -> D, E -> D。

指定されたグラフを表すコンテナーの階層構造を構築しようとしていますが、ダイヤモンドの依存関係に到達したときに何をすべきかわかりません。たとえば、私のグラフでは、CとEは両方とも の子コンテナでありB、 を解決するときにDと を参照する必要がCありEます。ダイヤモンドの依存関係を検出し、結合CしEて 1 つのコンテナーにすることはできますか?

4

6 に答える 6

3

色を使用してグラフ アルゴリズムを考えるのが最も簡単だと思います。

すべてのノードは白から始まります。

処理中のノードはグレーで表示されます。

ノードが処理されると、黒く色付けされます。

ノードに遭遇するとすぐにノードを灰色にします。

子の処理が終了したら、ノードを黒くします。

黒いノードに遭遇した場合は、ダイヤモンドの依存関係にヒットしています。

于 2009-03-10T04:06:00.423 に答える
1

ローハン、私は時々アルゴリズムとデータ構造を教えているので、偏見があるかもしれませんが、グラフアルゴリズムの本を調べる必要があると思います. これが示唆しているように見えることを行うにはさまざまな方法がありますが、実際に何をしようとしているのかは完全には明らかではありません。はい、この場合、同じノード (ここでは (B,E),(B,C) (C,D), (E,D)) との間の着信エッジと発信エッジを持つ 2 つのノードがあります。 2 つのノード C と E を「C,E」ノードに結合することは正当です。D を D 1に分割し、D 2でこれを DAG ではなくツリーにすることも合法です。

つまり、問題によってはそうすることが合法です。

于 2009-03-10T04:29:16.077 に答える
0

グラフのノードをどのように定義しているかわかりません。ノードを表す1つの方法は次のとおりです-

public interface Node {
            int getValue();
            List<Node> getChildren();
        }

このような実装の問題は、1 つのノードの親がわからないことです。あるノードの親が誰であるかを知る方法があれば、ダイヤモンドの依存関係を把握できます。

たとえば、あなたの場合、ツリーの一番下から開始する必要があります.Dには2つのParenetがあり、Bから来ていることがわかります. . 次に、1 回のパスで、複数の親を持つノード (D のように) と、それらの親 (C と E) が同じ親 (B) を持つかどうかを調べます。

于 2009-03-10T04:05:18.553 に答える
0

何をしようとしているのかよくわかりませんが、遅くともグラフにサイクルが含まれている場合は、検索中に繰り返し見つかったノードを検出する必要があります。通常、これはノードの処理中に何らかの方法でノードをマークすることによって行われます。これにより、以前にアクセスしたことがあるかどうかを後で確認できます。あなたのケースでこれがどれだけうまく機能するかは、実装とこれらのノードがどのように見えるかによって異なります...

于 2009-03-10T04:12:13.263 に答える
-1

グラフ理論は、非常に大きく複雑な数学の分野です。これは、ちょっとした知識が危険なことの 1 つです :) また、グラフ理論の基本的なアプリケーションでさえ、簡単な説明を見つけるのが難しい場合があります。グラフで遭遇する可能性が高いものはすべて打ちのめされており、問題に取り組んだときに想像していたよりも 5 倍多くの落とし穴や落とし穴がある可能性が非常に高いです。

ここでいくつかの非常に合理的な提案が表示され、少し後にそれらが部分的または大部分間違っていると識別されると思います。慎重に踏みます。

于 2009-03-10T04:09:32.210 に答える