C＃グラフのトラバース

Question

このアルゴリズムは、グラフ内のノードをトラバースする優れた処理を行います。

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つの親を持つことがあるので、各ノードで親プロパティを呼び出してバックアップを実行するだけでは簡単ではありません。

この方法の目的は、すべてのノードを反復しないように、またはノードが存在するかどうかを確認するために、パスを見つけることです。

Answer 1

先行ノードを追跡します。最も簡単な実装では、これは辞書であり、通常の擬似コードでπと表記：

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

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); 
      π.Add(neighbor, node); 
      worklist.Enqueue(neighbor); 
     } 
    } 
} 

次にあなたがeを言って、任意のノードからのパスをバックトラックするには、これらの前任者を反復処理することができます

while (π[e] != null) { 
    Console.WriteLine(e); 
    e = π[e]; 
} 

Answer 2

"this"、つまり、現在のインスタンス、グラフの "ルート"は、このようなことがある場合ですか？

グラフは周期的か非周期的か？私はグラフ理論のすべての用語を知りません。ここで

は、私は本当にについて疑問に思うものです：ここで

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 

Answer 3

「現在の」ノードへのパスを常に追跡しているわけではありません。あなたが目標を見つけたときにそれを構築しなければなりません。 NodeクラスにParentプロパティがある場合は、ツリーを簡単にバックトラックして完全なパスを構築できます。

Answer 4

ピーターはほぼ正しいです。私は、ノードクラスの親頂点へのリンクを保存することはできないと思います。なぜなら、幅優先探索を開始する頂点に応じて変化するからです。キーがノードで、値が親ノードである親ディクショナリを作成する必要があります。各頂点を訪問するとき（ただし、処理する前に）、親を辞書に追加します。次に親ルートをルート頂点まで戻って行くことができます。

Answer 5

私は操作が全てがマークを取得されBasicly

public String EncontrarMenorCaminho(Vertice o, Vertice d) 
     { 
      Dictionary<Vertice, bool> visited = new Dictionary<Vertice, bool>(); 
      Dictionary<Vertice, Vertice> previous = new Dictionary<Vertice, Vertice>(); 
      Queue<Vertice> worklist = new Queue<Vertice>(); 
      String operacao = "Registro de operações realizadas:\r\n\r\n"; 

      visited.Add(o, false); 
      worklist.Enqueue(o); 
      while (worklist.Count != 0) 
      { 
       Vertice v = worklist.Dequeue(); 
       foreach (Vertice neighbor in EncontrarVizinhos(v)) 
       { 
        if (!visited.ContainsKey(neighbor)) 
        { 
         visited.Add(neighbor, false); 
         previous.Add(neighbor, v); 
         worklist.Enqueue(neighbor); 
        } 
       } 
      } 

      if (previous.Count > 0) 
      { 
       for (int p = 0; p < previous.Count; p++) 
       { 
        Vertice v1 = previous.ElementAt(p).Key; 
        Vertice v2 = previous.ElementAt(p).Value; 
        EncontrarAresta(v1, v2).Selecionado = true; 
        EncontrarAresta(v2, v1).Selecionado = true; 
        operacao += v1.Info.ToString() + "x" + v2.Info.ToString() + "\r\n"; 
       } 
      } 

      List<Vertice> grupos = new List<Vertice>(); 

      foreach (Aresta a in ArestasSelecionadas()) 
      { 
       if (!grupos.Contains(a.Origem)) grupos.Add(a.Origem); 
      } 

      foreach (Vertice v in grupos) 
      { 
       int menorpeso = this.infinito; 
       foreach(Vertice vz in EncontrarVizinhos(v)) 
       { 
        Aresta tmp = EncontrarAresta(v,vz); 
        if (tmp.Selecionado == true && tmp.Peso < menorpeso) 
        { 
         menorpeso = tmp.Peso; 
        } 
        else 
        { 
         tmp.Selecionado = false; 
        } 
       } 

      } 




      DesenharMapa(); 

      return operacao; 

...ソースと運命を使用して、頂点への代替パス（私のコードで頂点）を取得するには、このスニペットの使用を試みたが、単にいけない仕事

プレビュー画像を参照してください：エッジ（Selecionado =真）と、選択し続ける必要がある場合は、再度確認してください...このサンプルで

は、私が頂点に「N」「Q」vertextから最短パスを取得したいですここ：