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

先行ノードを追跡します。最も簡単な実装では、これは辞書であり、通常＆＃960;として示されます。擬似コード：

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

このスニペットを使用して、ソースとデスティネーションを使用して頂点（コード内の頂点）への代替パスを取得しようとしましたが、単に機能しません...

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;

基本的に、操作はすべてのマークされたエッジを取得し (Selectionado = true)、必要に応じて再度確認し、選択を継続します...

このサンプルでは、​​頂点 'N' から頂点 'Q' までの最短パスを取得します。

ここでプレビュー画像をご覧ください。

Answer 3

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

グラフは周期的ですか、それとも非周期的ですか？グラフ理論のすべての用語がわからないのではないかと考えています。

私が本当に疑問に思うことは次のとおりです：

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

ここに私の質問があります：

• これは発生しますか？
• 「これ」を＆quot;あなたのコードで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 4

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

Answer 5

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