C# Graphlversal

Question

Questo algoritmo fa un grande lavoro di attraversamento dei 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 usare questo per trovare un nodo di destinazione nel grafico. La lista di lavoro rimuove (o fa scomparire) gli elementi man mano che la lista di lavoro viene elaborata. Una volta trovato l'obiettivo, come posso restituire il percorso completo al nodo?

Aggiornamento Sto cercando di capire come invertire il percorso della radice. Il metodo viene chiamato sul nodo radice, dopo di che, i bambini possono avere due genitori, quindi non è così semplice come chiamare la proprietà genitore su ciascun nodo e attraversare il backup.

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

Answer 1

Tieni traccia dei nodi precedenti.Nel più semplice implementazione, questo è un dizionario, e di solito indicata come π in pseudo-codice:

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 fare marcia indietro il percorso da qualsiasi nodo, diciamo e:

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

Answer 2

"questo", cioè l'istanza corrente, la "radice" del grafico, se esiste una cosa del genere?

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

Ecco quello che mi chiedo:

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

Ecco le mie domande:

• sarà questo si verifica?
• "Questo" nel codice può mai iniziare da B?
• Quale sarà il percorso per F?

Se il grafico non si unisce mai quando è stato 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 che si visita, aggiunge il nodo adiacente come chiave, e il nodo è stato un vicino di casa come valore. Questo 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 per l'E-node, semplicemente marcia indietro:

E -> D -> B -> A 

Quale ti dà il percorso:

A -> B -> D -> E 

Answer 3

Poiché non stai seguendo il percorso del nodo "corrente" in qualsiasi momento costruirlo quando hai trovato il bersaglio. Se la classe Node ha una proprietà Parent, puoi facilmente tornare indietro all'albero per costruire il percorso completo.

Answer 4

Peter è quasi corretto. Non penso che tu possa memorizzare un collegamento al vertice genitore nella classe del nodo, perché cambia a seconda del vertice a cui inizi la tua prima ricerca in ampiezza. È necessario creare un dizionario principale con le chiavi come nodi e i valori come nodi padre. Quando visiti ciascun vertice (ma prima di elaborarlo) aggiungi i genitori al dizionario. Quindi puoi risalire il percorso genitore fino al vertice della radice.

Answer 5

Ho provato utilizzare questo frammento per ottenere i percorsi alternativi da al vertice (vertici nel mio codice), usando la sorgente e il destino, ma semplicemente non lavoro ...

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 contrassegnati bordi (Selecionado = true) e verificare nuovamente se è necessario continuare selezionato ...

In questo esempio, voglio ottenere il percorso più breve da vertext 'N' per il vertice 'Q':

Vedere un'immagine di anteprima qui: