Cómo imprimir rutas en forma DFS en gráficos

El método PrintAllPath se llamará recursivamente y, en el caso base, imprimirá la ruta.

A medida que hacemos DFS, la lista llamada ruta hará un seguimiento de la ruta actual y necesitamos imprimirla una vez que se alcanza la condición base.

///
/// Imprime todas las rutas en un árbol n-ary
///
clase AllPathInNArayTree
{
///
/// Almacena la ruta a medida que se realiza el recorrido
///
List path = new List ();

///
/// La subrutina recursiva que hace DFS y la condición base es alcanzada
/// una vez que se golpea el nodo hoja.
///
/// vacío PrintAllPath (Nodo n)
{
if (n.Children.Count == 0)
{
// este es un nodo hoja necesitamos imprimir la ruta
ruta.Agregar (n);
PrintPath ();
ruta. Eliminar (n);
regreso;
}
ruta.Agregar (n);
foreach (Nodo hijo en n.Niños)
{
PrintAllPath (hijo);
}
ruta. Eliminar (n);
}

///
/// Imprime la ruta actual hasta el nodo hoja
///
privado vacío PrintPath ()
{
foreach (Nodo n en el camino)
{
Console.Write (“{0} ->”, n.Data);
}
Console.WriteLine ();
}

///
/// Representa el nodo de un árbol n_ary
///
Nodo de clase
{
Datos de char públicos {get; conjunto; }
Lista pública Hijos {get; conjunto; }
Nodo público (datos de char)
{
Datos = datos;
Hijos = nueva Lista ();
}
}

#region TestArea
público estático vacío TestAllPathInNArayTree ()
{
Nodo nodoA = nuevo nodo (‘A’);
Nodo nodoB = nuevo nodo (‘B’);
Nodo nodoC = nuevo nodo (‘C’);
Nodo nodoD = nuevo nodo (‘D’);
Nodo nodoE = nuevo nodo (‘E’);
Nodo nodoF = nuevo nodo (‘F’);
Nodo nodoG = nuevo nodo (‘G’);
Nodo nodoH = nuevo nodo (‘H’);
Nodo nodoI = nuevo nodo (‘I’);
nodeA.Children = new List () {nodeB, nodeC, nodeD};
nodeB.Children = new List () {nodeE, nodeF};
nodeC.Children = new List () {nodeG};
nodeD.Children = new List () {nodeH, nodeI};

AllPathInNArayTree allPath = new AllPathInNArayTree ();
allPath.PrintAllPath (nodeA);

}
#endregion
}

La salida del código anterior es como se muestra a continuación:

A -> B -> E ->

A -> B -> F ->

A -> C -> G ->

A -> D -> H ->

A -> D -> I ->

Espero que esto te ayude.

Por favor agregue la línea 30.

#! / usr / bin / python

Nodo de clase:
def __init __ (self, name):
self.name = name
self.children = []

A = Nodo (‘A’)
B = Nodo (‘B’)
C = Nodo (‘C’)
D = Nodo (‘D’)
E = Nodo (‘E’)
F = Nodo (‘F’)
G = Nodo (‘G’)
H = Nodo (‘H’)
I = Nodo (‘I’)
A.niños = [B, C, D]
B. niños = [E, F]
C.niños = [G]
D. niños = [H, I]

# DFS comienza aquí

def dfs (nodo):
sta.append (nodo)
si no node.children:
print ([nombre.nodo para nodo en sta])
para niño en node.children:
dfs (niño)
sta.pop ()

sta = []
dfs (A)