Python itératives Profondeur Première recherche de la table

Question

je la table de données suivantes:

child_pid parent_pid 
     1  -1 
     2   1 
     6  -1 
     7   6 
     8   7 
     9   8 
     21  -1 
     22  21 
     24  -1 
     25  24 
     26  25 
     27  26 
     28  27 
     29  28 
     99  6 
     107  99 
     108  -1 
     109  108 
     222  109 
     1000  7 
     1001  1000 

Je veux écrire un python en profondeur d'abord itérative recherche qui génère le résultat suivant:

('final: ', 
    [[u'1', u'2'], 
    [u'6', u'7', u'8', u'9'], 
    [u'6', u'7', u'1000', u'1001'], 
    [u'6', u'99', u'107'], 
    [u'21', u'22'], 
    [u'24', u'25', u'26', u'27', u'28', u'29'], 
    [u'108', u'109', u'222']]) 

ci-dessus la sortie a été générée en utilisant une approche récursive. Nous pouvons voir que toutes les relations enfant/parent sont préservées de manière appropriée.

J'ai utilisé la logique suivante d'un autre tutoriel dans ma tentative de tirer une approche itérative:

def dfs_iterative(graph, start): 
    stack, path = [start], [] 

    while stack: 
     vertex = stack.pop() 
     if vertex in path: 
      continue 
     path.append(vertex) 
     for neighbor in graph[vertex]: 
      stack.append(neighbor) 

    return path 

qui se traduit par:

('final: ', 
    [[u'1', u'2'], 
    [u'6', u'99', u'107', u'7', u'1000', u'1001', u'8', u'9'], 
    [u'21', u'22'], 
    [u'24', u'25', u'26', u'27', u'28', u'29'], 
    [u'108', u'109', u'222']]) 

Nous pouvons voir que les résultats sont presque identiques sauf lorsqu'un noeud a plus d'un enfant. Plus précisément, le nœud 6 a les relations suivantes:

6->7->8->9 
6->7->1000->1001 
6->99->107 

Dans la sortie récursive ci-dessus, on voit que le noeud 6 est convenablement réparti en ses relations de bon chemin. Dans ma tentative itérative, tous les «descendants» du nœud 6 sont regroupés dans une liste. Vous cherchez un moyen de générer la sortie récursive, mais avec une approche itérative en python. Pensées? J'apprécie l'aide!

Answer 1

Le problème ici est que votre "équivalent" itératif n'est pas: votre algorithme trouve la fermeture du graphique. Le résultat que vous voulez est de trouver des chemins individuels dans un arbre. Lorsque vous utilisez le mauvais outil, vous obtenez un résultat différent.

Votre approche semble démarrer à un nœud donné (ostensiblement l'un des nœuds racine), et accumule des nœuds individuels dans un ordre indéfini de voisins. Au lieu de cela, essayez cette

• pop haut partial_path de la pile
• sommet < = dernier élément de partial_path
• si sommet n'a pas d'enfant:
  • append partial_path pour aboutir.
• autre
  • pour chaque enfant de sommet
  • add (ajouter ou pousser) [partial_path + enfant] pour empiler

Est-ce que gérer votre problème?