0

有向グラフにトポロジカルソートのようなサイクルがあるかどうかを検出する必要がありますが、ビジターパターンを使用したいと思います。アイデアはありますか？ノードの配列リスト、およびエッジまたは他の構造（配列ではない）を使用できます。

4

1 に答える 1

2

ビジターパターンは、そのようなことを最も純粋な形で実現することはできません。

ビジターパターンでは通常、「ビジター」がオブジェクトのウェブを移動しますが、オブジェクトのウェブはビジターを「誘導」することに注意してください。訪問者は事実上パスを認識しないため、特定の種類の破損を防ぎます。

ビジターパターンのウィキペディアの例から（Javaで）

class Car implements CarElement {
    CarElement[] elements;
 
    public Car() {
        //create new Array of elements
        this.elements = new CarElement[] { new Wheel("front left"), 
            new Wheel("front right"), new Wheel("back left") , 
            new Wheel("back right"), new Body(), new Engine() };
    }
 
    public void accept(CarElementVisitor visitor) {     
        for(CarElement elem : elements) {
            elem.accept(visitor);
        }
        visitor.visit(this);    
    }
}

Caracceptメソッドに注意してください。これにより、車のすべてのサブ要素がカバーされ、ナビゲーションがカプセル化されますが、データ構造全体に対して外部機能を適用する機能が公開されます。

コードにはデータ構造がどのように相互に接続されているかについての知識が必要なため、ビジターパターンはタスクにあまり適していません。訪問者が循環データ構造に遭遇した場合、将来の訪問者は同じループでスタックし、一部Visitorのデータにアクセスせず、との間の契約を破りVisitAcceptorsます。

これで、訪問パスに「おそらく循環」リンクがたどられなかった場合、目標をある程度達成できる可能性があります。それでも、訪問パスの他のブランチだけで、グラフのすべてのノードが訪問パスで追跡されていることを確認する必要があります。そうすると、訪問者は基本的に、移動していないバックリンクに見舞われる可能性のあるノードの大規模なコレクションになりますが、このような奇妙なソリューションを実装するまでに、なぜ訪問者の部分に悩まされたのか不思議に思うでしょう。

于 2013-03-24T12:50:22.707 に答える