C # Graph Traversal

Question

Este algoritmo faz um ótimo trabalho de percorrer os nós em um gráfico.

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);
        }
    }
}

Eu posso usar isso para encontrar um nó de destino no gráfico. Os Retiradas da fila lista de trabalho (ou pops) os itens como lista de trabalho é processada. Uma vez que eu encontrar o alvo como posso retornar o caminho completo para o nó?

Atualizar Eu estou tentando descobrir como reverter o caminho para a raiz. O método é chamado no nó raiz, depois disso, as crianças podem ter dois pais, por isso não é tão simples como chamar a propriedade pai em cada nó e atravessando de volta.

O objetivo do método é encontrar o caminho, não para iterate todos os nós, ou para verificar se um nó existe.

Answer 1

Mantenha o controle dos nós antecessor. Na implementação mais fácil, este é um dicionário, e, geralmente indicado como p em pseudo-código:

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);
        }
    }
}

Em seguida, você pode iterar através desses antecessores para recuar o caminho a partir de qualquer nó, dizem e:

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

Answer 2

Eu tentei usar esse trecho para obter os caminhos alternativos a partir de vértice (vértices no meu código), usando fonte e do destino, mas o trabalho simplesmente não ...

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;

Basicamente a operação é obter todas as arestas marcadas (selecionado = true) e verificar novamente se é necessário continuar selecionado ...

Neste exemplo, eu quero pegar o caminho mais curto de vertext 'N' ao vértice 'Q':

Veja uma imagem de visualização aqui:

Answer 3

é "isto", ou seja, a instância atual, a "raiz" do gráfico, se existe tal coisa um?

É o cíclica gráfico ou acíclico? Eu tenho medo Eu não sei todos os termos de teoria dos grafos.

Aqui está o que eu realmente me pergunto sobre: ??

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

Aqui estão as minhas perguntas:

• Será que isso ocorre?
• Can "isto" em seu código já começam em B?
• Qual será o caminho para a F ser?

Se o gráfico não se junta novamente juntos quando ele se separou, não contém ciclos, e "este" será sempre a raiz / start do gráfico, um dicionário simples irá lidar com o caminho.

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

para cada nó que você visita, adicione o nó vizinho como chave, e o nó que era um vizinho de como o valor. Isto irá permitir que você, uma vez que você encontrar o nó de destino, a recuar de volta para obter o caminho inverso.

Em outras palavras, o dicionário para o gráfico acima, depois de um percurso completo seria:

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

Para encontrar o caminho para o E-nó, simplesmente backtrack:

E -> D -> B -> A

O que dá-lhe o caminho:

A -> B -> D -> E

Answer 4

Uma vez que você não está seguindo o caminho para o nó "atual" em todos os momentos você terá que construir que depois de ter encontrado o alvo. Se sua classe Node tem uma propriedade Parent você poderia facilmente recuar até a árvore para construir o caminho completo.

Answer 5

Peter é quase correta. Eu não acho que você pode armazenar um link para o vértice pai na classe nó, porque muda dependendo do vértice em que você começar a sua busca em largura. Você precisa criar um dicionário do pai com as chaves sendo nós e os valores sendo nós pai. Como você visitar cada vértice (mas antes do processamento) você adicionar os pais ao dicionário. Então você pode caminhar até a parte de trás caminho pai para o vértice raiz.