1

キーが頂点IDであり、リストにエッジに沿ったすべてのターゲット頂点が含まれる場所としてDAGを表すことを検討しています。Dictionary(Of Integer, List(Of Integer))

この構造は後で次の目的で使用します。

  • 可能なアセンダントパスとディセンダントパスのリストを導き出す
  • 可能な次のパスと可能なソースパスのリストを導き出します
  • リーフノードのリストを導出する
  • 頂点間の提案されたエッジを検証します
  • 頂点をトポロジカルソートする

    私のアプローチに問題はありますか？過去にどのようにそれをしましたか？ありがとう

    編集
    私のアプローチの1つの問題は、頂点へのソースパスを見つけることは、辞書全体を反復する必要があるため、コストのかかる操作であるということです。おそらく、DAGVertexオブジェクトを露出させTargetsてSources

    • 4

    2 に答える 2

    2

    グラフを2つのディクショナリとして表すことができます。1つは入力エッジ用、もう1つは出力エッジ用です。これにより、グラフとメモリ消費を変更する時間が2倍になりますが、特定の頂点に到達するエッジのリストをからに取得する時間の複雑さが軽減さO(V + E)れO(1)ます。

    リーフノードのリストの取得も同様に行うことができます。現在のリーフノードのリスト（またはDictionary(Of Integer, Boolean)）を用意するだけです。リーフノードになるたびにノードを追加し、リーフノードでなくなった場合は削除します。

    于 2011-03-31T19:49:25.917 に答える
    0

    私は自分のノードにエンティティを作成し、アプローチでOOPを使用すると信じています。

    要件が変更されることはなく、それについて完全に確信している場合は、アプローチは問題ないかもしれませんが、たとえばノードと別のノード間のすべてのパスに「重み」を割り当てるなど、要件が変更される可能性がある場合は、難しいかもしれません。それをするために。（次のようなことを行うことでそれを解決します。

    Dictionary<Int32, List<Int32, Dictionary<Int32, Int32>>

    ???）

    私のクラスは少しこのように見えると思います。

    public class GraphNode
{
    private Int32 value;
    public Int32 Value
    {
        get { return this.value; }
    }

    private List<GraphNode> siblings;
    public ReadOnlyCollection<GraphNode> Siblings
    {
        get { return new ReadOnlyCollection<GraphNode>(siblings); }
    }

    public void AddSibling(GraphNode node)
    {
        if (this == node)
            throw new Exception("Can't assing a node to itself as a sibling");

        if (this.siblings.Contains(node))
            throw new Exception("This node is already contained in the siblings list");

        this.siblings.Add(node);
    }

    public GraphNode(Int32 value)
    {
        this.value = value;
        this.siblings = new List<GraphNode>();
    }
}
    于 2011-03-31T19:36:38.400 に答える