Traversal grafico C #

Question

Questo algoritmo fa un ottimo lavoro nel percorrere i nodi in un grafico.

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

Posso usarlo per trovare un nodo target nel grafico. La lista di lavoro accoda (o apre) gli elementi mentre la lista di lavoro viene elaborata. Una volta trovata la destinazione, come posso restituire il percorso completo al nodo?

Aggiorna Sto cercando di capire come invertire il percorso verso la radice. Il metodo viene chiamato sul nodo principale, dopodiché i figli possono avere due genitori, quindi non è semplice come chiamare la proprietà padre su ciascun nodo e attraversare il backup.

L'obiettivo del metodo è trovare il percorso, non iterare tutti i nodi o verificare se esiste un nodo.

Answer 1

Tieni traccia dei nodi precedenti. Nell'implementazione più semplice, questo è un dizionario e solitamente indicato come p negli pseudo-codici:

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

Quindi è possibile scorrere questi predecessori per tornare indietro da qualsiasi nodo, ad esempio e :

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

Answer 2

Ho provato a usare questo frammento per ottenere i percorsi alternativi dal vertice (vertici nel mio codice), usando sorgente e destino, ma semplicemente non funziona ...

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;

Fondamentalmente l'operazione è ottenere tutti i bordi marcati (Selecionado = true) e verificare di nuovo se è necessario continuare selezionato ...

In questo esempio, voglio ottenere il percorso più breve dal testo 'N' al vertice 'Q':

Vedi un'immagine di anteprima qui:

Answer 3

È " questo " ;, ovvero, l'istanza corrente, " root " del grafico, se esiste una cosa del genere?

Il grafico è ciclico o aciclico? Temo di non conoscere tutti i termini per la teoria dei grafi.

Ecco cosa mi chiedo davvero:

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

Ecco le mie domande:

• Accadrà?
• Può " questo " nel tuo codice mai iniziare da B?
• Quale sarà il percorso verso F?

Se il grafico non si unisce mai di nuovo quando si è diviso, non contiene cicli e "questo". sarà sempre la radice / inizio del grafico, un semplice dizionario gestirà il percorso.

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

per ogni nodo visitato, aggiungere il nodo adiacente come chiave e il nodo a cui era vicino come valore. Ciò ti permetterà, una volta trovato il nodo di destinazione, di tornare indietro per ottenere il percorso inverso.

In altre parole, il dizionario per il grafico sopra, dopo un attraversamento completo sarebbe:

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

Per trovare il percorso dell'E-node, è sufficiente tornare indietro:

E -> D -> B -> A

Che ti dà il percorso:

A -> B -> D -> E

Answer 4

Dato che non stai monitorando il percorso verso " corrente " nodo in ogni momento dovrai costruirlo quando hai trovato la destinazione. Se la tua classe Node ha una proprietà Parent, puoi facilmente tornare indietro sull'albero per costruire il percorso completo.

Answer 5

Peter ha quasi ragione. Non penso che tu possa memorizzare un collegamento al vertice principale nella classe del nodo, perché cambia in base al vertice in cui inizi la tua prima ricerca. È necessario creare un dizionario principale con le chiavi come nodi e i valori come nodi principali. Man mano che visiti ciascun vertice (ma prima dell'elaborazione) aggiungi i genitori al dizionario. Quindi puoi risalire il percorso principale fino al vertice principale.