12

このアルゴリズムは、グラフ内のノードをトラバースするのに最適です。

Dictionary<Node, bool> visited = new Dictionary<Node, bool>();

Queue<Node> worklist = new Queue<Node>();

visited.Add(this, false);

worklist.Enqueue(this);

while (worklist.Count != 0)
{
    Node node = worklist.Dequeue();

    foreach (Node neighbor in node.Neighbors)
    {
        if (!visited.ContainsKey(neighbor))
        {
            visited.Add(neighbor, false);
            worklist.Enqueue(neighbor);
        }
    }
}

これを使用して、グラフ内のターゲットノードを見つけることができます。ワークリストは、ワークリストが処理されるときにアイテムをデキュー（またはポップ）します。ターゲットを見つけたら、どうすればノードへのフルパスを返すことができますか？

更新 ルートへのパスを逆にする方法を理解しようとしています。このメソッドはルートノードで呼び出されます。その後、子には2つの親が存在する可能性があるため、各ノードで親プロパティを呼び出して元に戻すほど簡単ではありません。

このメソッドの目的は、パスを見つけることであり、すべてのノードを反復することではなく、ノードが存在するかどうかを確認することです。

4

4 に答える 4

0

「これ」、つまり現在のインスタンス、グラフの「ルート」は、そのようなものがある場合ですか？

グラフは循環的ですか、それとも非循環的ですか？グラフ理論のすべての用語を知っているわけではないのではないかと思います。

これが私が本当に疑問に思っていることです：

A -> B -> C ------> F
     B -> D -> E -> F

これが私の質問です：

  • これは起こりますか？
  • コードの「これ」をBから始めることはできますか？
  • Fへの道はどうなるでしょうか？

グラフが分割され、サイクルが含まれておらず、「これ」が常にグラフのルート/開始である場合、グラフが結合されない場合は、単純な辞書がパスを処理します。

Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>();

アクセスするノードごとに、隣接ノードをキーとして追加し、隣接ノードが隣接していたノードを値として追加します。これにより、ターゲットノードを見つけたら、逆方向のパスを取得するためにバックトラックすることができます。

言い換えると、完全なトラバーサル後の上のグラフの辞書は次のようになります。

B: A
C: B
D: B
E: D
F: C (or E, or both?)

Eノードへのパスを見つけるには、単にバックトラックします。

E -> D -> B -> A

それはあなたに道を与えます：

A -> B -> D -> E
于 2009-03-05T15:20:03.483 に答える
0

ピーターはほぼ正しいです。幅優先探索を開始する頂点によって変わるため、ノードクラスに親頂点へのリンクを格納できるとは思いません。キーがノードで、値が親ノードである親ディクショナリを作成する必要があります。各頂点にアクセスするたびに (処理前に)、親をディクショナリに追加します。次に、親パスをルート頂点に戻ることができます。

于 2009-03-05T15:36:36.280 に答える
0

「現在の」ノードへのパスを常に追跡しているわけではないため、ターゲットを見つけたときにそれを構築する必要があります。Node クラスに Parent プロパティがある場合、ツリーを簡単にさかのぼって完全なパスを作成できます。

于 2009-03-05T15:23:21.353 に答える