Elenco di tutti i percorsi disgiunti del bordo in un albero

Question

In un albero generico rappresentato dalla struttura del nodo comune che dispone di indicatori padre e figlio, come si può trovare un elenco di tutti i percorsi che non hanno bordi sovrapposti tra loro e terminano con una foglia nodo.

Ad esempio, in un albero come questo:

  1 
    / | \    
    2 3 4 
    /\ | /\ 
    5 6 7 8 9 

L'output desiderato sarebbe un elenco di percorsi come segue:

1 2 1 1 4 
| | | | | 
2 6 3 4 9 
|   | | 
5   7 8 

O sotto forma di lista:

[[1, 2, 5], [2, 6], [1, 3, 7], [1, 4, 8], [4, 9]] 

Ovviamente il percorso si elenca e il loro ordine può variare in base all'ordine di elaborazione dei rami degli alberi. Ad esempio, la seguente è un'altra possibile soluzione se lasciato processo rami primo:

[[1, 4, 9], [4, 8], [1, 3, 7], [1, 2, 6], [2, 5]] 

fini di questa domanda, non è richiesto alcun ordine specifico.

Answer 1

Per tutti i vertici, se il vertice è foglia (non ha indicatori figli), passare attraverso la catena padre fino a trovare un vertice o vertice segnato senza genitore. Segna tutti i vertici visitati. Raccogli i vertici nell'elenco intermedio, quindi invertilo e aggiungi al risultato.

Se non è possibile aggiungere un contrassegno all'oggetto vertice stesso, è possibile implementare la marcatura come un insieme separato di vertici visitati e considerare tutti i vertici aggiunti all'insieme come contrassegnati.

Answer 2

È possibile utilizzare uno recursive DFS algorithm con alcune modifiche.
Non hai detto quale lingua usi, quindi spero che C# sia OK per te.

Definiamo una classe per il nostro nodo della struttura:

public class Node 
{ 
    public int Id; 
    public bool UsedOnce = false; 
    public bool Visited = false; 
    public Node[] Children; 
} 

Date un'occhiata a UsedOnce variabile - si può guardare piuttosto ambigua.
UsedOnce equivale a true se questo nodo è stato utilizzato una sola volta in un'uscita. Dato che abbiamo un albero, significa anche che un fronte da questo nodo al suo genitore è stato usato una volta in un output (in un albero, ogni nodo ha solo un bordo padre che è il bordo del suo genitore). Leggi attentamente per non diventare confuso in futuro.

Qui abbiamo una semplice implementazione di algoritmo di ricerca in profondità.
Tutta la magia sarà trattata in un metodo di output.

List<Node> currentPath = new List<Node>(); // list of visited nodes 

public void DFS(Node node) 
{ 
    if (node.Children.Length == 0) // if it is a leaf (no children) - output 
    { 
     OutputAndMarkAsUsedOnce(); // Here goes the magic... 
     return; 
    } 

    foreach (var child in node.Children) 
    { 
     if (!child.Visited) // for every not visited children call DFS 
     { 
      child.Visited = true; 
      currentPath.Add(child); 
      DFS(child); 
      currentPath.Remove(child); 
      child.Visited = false; 
     } 
    } 
} 

Se OutputAndMarkedAsUsedOnce solo in output un currentPath contenuti, allora avremmo una potenza pianura DFS in questo modo:

1 2 5 
1 2 6 
1 3 7 
1 4 8 
1 4 9 

Ora, abbiamo bisogno di usare il nostro UsedOnce. Let's trova l'ultimo nodo used-once (che è già stato in un'uscita) nel percorso corrente e restituisce tutto il percorso da questo nodo allo. È garantito che tale nodo esiste perché, almeno l'ultimo nodo in un percorso non è mai stato incontrato prima e non può essere contrassegnato come usato una sola volta.

Ad esempio, se il percorso corrente è "1 2 3 4 5" e 1, 2, 3 sono contrassegnati come utilizzati una volta - quindi output "3 4 5".

Nel tuo esempio:

1. Siamo al "1 2 5". Tutti sono inutilizzati, uscita "1 2 5" e marca 1, 2, 5 come usato una volta
2. Ora, siamo a "1 2 6". 1, 2 sono usati - 2 è l'ultimo. Uscita da 2 in modo inclusivo, "2 6", segnare 2 e 6 come usato.
3. Ora siamo a "1 3 7", 1 è usato, l'unico e l'ultimo. Uscita da 1 compresa, "1 3 7". Segna 1, 3, 7 come usato.
4. Ora siamo a "1 4 8". 1 è usato, l'unico e l'ultimo. Uscita "1 4 8".
5. Ora siamo a "1 4 9". 1, 4 sono usati. Uscita da 4 - "4 9".

Funziona perché in un albero "nodo utilizzato" significa "usato (l'unico genitore) bordo tra esso e il suo genitore". Quindi, in realtà contrassegna i bordi usati e non li emette di nuovo.

Ad esempio, quando si contrassegna 2, 5 come usato, significa che si contrassegnano i bordi 1-2 e 2-5. Quindi, quando usiamo "1 2 6" - non produciamo bordi "1-2" perché sono usati, ma output "2-6".
Il nodo radice di marcatura (nodo 1) utilizzato una volta non influenza l'output perché il suo valore non viene mai verificato. Ha una spiegazione fisica - il nodo radice non ha margini parentali.

Siamo spiacenti per una spiegazione scarsa. È piuttosto difficile spiegare un algoritmo sugli alberi senza disegnare :) Sentiti libero di porre domande sugli algoritmi o C#.

Questo è il funzionamento IDEOne demo.

P.S. Questo codice è, probabilmente, non è un buon codice corretto C# (proprietà automatiche evitate, LINQ evitato) per renderlo comprensibile agli altri codificatori.

Ovviamente, questo algoritmo non è perfetto - possiamo rimuovere currentPath perché in un albero il percorso è facilmente recuperabile; possiamo migliorare l'output; possiamo incapsulare questo algoritmo in una classe. Ho appena provato a mostrare la soluzione comune.

Answer 3

Questo è un albero. Le altre soluzioni probabilmente funzionano ma sono inutilmente complicate. Rappresenta una struttura ad albero in Python.

class Node: 
    def __init__(self, label, children): 
     self.label = label 
     self.children = children 

Poi l'albero

1 
/\ 
2 3 
/\ 
    4 5 

è Node(1, [Node(2, []), Node(3, [Node(4, []), Node(5, [])])]). Effettuare una procedura ricorsiva come segue. Garantiamo che la radice appaia nel primo percorso.

def disjointpaths(node): 
    if node.children: 
     paths = [] 
     for child in node.children: 
      childpaths = disjointpaths(child) 
      childpaths[0].insert(0, node.label) 
      paths.extend(childpaths) 
     return paths 
    else: 
     return [[node.label]] 

Questo può essere ottimizzato (primo obiettivo: interrompere l'inserimento nella parte anteriore di un elenco).

Answer 4

Questo può essere facilmente realizzato utilizzando DFS.

Chiamiamo il DFS da root.

DFS(root,list) 

in cui l'elenco contiene inizialmente

list = {root} 

Ora l'algoritmo è il seguente:

DFS(ptr,list) 
{ 
if(ptr is a leaf) 
    print the list and return 
else 
{ 
    for ith children of ptr do 
    { 
    if(ptr is root) 
    { 
    add the child to list 
    DFS(ith child of ptr,list) 
    remove the added child 
    } 
    else if(i equals 1 that is first child) 
    { 
    add the child to list 
    DFS(ith child of ptr,list) 
    } 
    else 
    { 
    initialize a new empty list list2 
    add ith child and the ptr node to list2 
    DFS(ith child of ptr,list2) 
    } 
    } 
} 
}