L'algorithme de profondeur en profondeur implémenté dans la bibliothèque de boosters ne visite chaque sommet qu'une seule fois.algorithme de recherche en profondeur en profondeur
Est-il possible de désactiver cette option. Je veux que les vertex puissent être visités chaque fois qu'il y a une branche dans un sommet quelconque.
toute suggestion ...
EDIT: Le graphique est acyclique.
Si vous voulez énumérer tous les chemins dans un graphe acyclique, alors je ne pense pas que vous puissiez facilement modifier la profondeur d'abord pour faire cela. Il existe des algorithmes spécialement conçus à cet effet, en particulier: Rubin, F .; , "Enumérant tous les chemins simples dans un graphique", Circuits et systèmes, Transactions IEEE sur, vol.25, n ° 8, pp. 641- 642, août 1978.
Si vous connaissez l'algorithme Floyd-Warshall, vous peut facilement le modifier pour calculer une liste de chemins dans chaque élément de la matrice, au lieu de la distance min, qui fera le travail. L'article ci-dessus utilise quelques opérations de bits pour rendre cette exécution un peu plus rapide.
veulent que les vertex peuvent visiter chaque fois qu'il ya une branche dans tout sommet .
Que proposez-vous qu'un itérateur fasse quand il atteint une branche à un sommet?
Profondeur La première recherche est juste une réponse à cette question. Here sont quelques autres.
Mais vous devez choisir quelque chose. Il ne s'agit pas d'éteindre DFS.
Je pense que c'est impossible par conception. Parce que si votre graphe contient des cycles (et vous les avez là, quand vous dites que le sommet peut être visité plus d'une fois), l'algorithme se terminera en boucle sans fin.
Le graphique est acyclique. Le but est de calculer le nombre de chemins. – sa11
Pouvez-vous donner un exemple? c'est-à-dire une situation où un sommet serait visité plus d'une fois? –
Cela pourrait tourner à jamais si le graphique a des cycles. Pouvez-vous être plus précis sur votre condition de terminaison? – templatetypedef