Traverser un graphe Vs Traverser un arbre

Question

Une fonction qui traversait un graphe fonctionnerait-elle aussi bien pour traverser un arbre?

Answer 1

Eh bien, un arbre est juste un type particulier de graphe appelé un graphe acyclique dirigé, alors oui ... La première traversée et la première traversée de profondeur fonctionnent toutes deux sur un arbre.

Je pourrais écrire une explication détaillée des différences entre les traversées de largeur et de profondeur en premier, mais je me trompe probablement (je ne suis pas encore un comp-sci lourd). Il suffit de dire que la seule différence entre la largeur et la profondeur de la première traversée est l'ordre dans lequel vous traitez les vertices. En premier lieu, vous pouvez envisager d'ajouter des sommets à une file d'attente «à traiter». La profondeur d'abord vous pouvez penser à ajouter les sommets à une pile «à traiter». Quand vient le temps de traiter les sommets (après qu'ils ont été ajoutés à leurs structures de données respectives), vous devez dequeue ou pop la pile pour obtenir le prochain sommet à traiter. Les versions intelligentes de la première traversée de profondeur utilisent la récursivité pour traiter les sommets au lieu de les ajouter à une pile.

Je ne sais pas si cela a été utile ou non ...

Une recherche rapide Google (je ne sais pas si elle était étendue ou la profondeur d'abord) trouve this qui semble assez bon pour décrire les différences entre BFS et DFS. Je peux également recommander The Algorithm Design Manual de Steve Skiena si vous voulez obtenir une lecture plus en profondeur.

Answer 2

Une fonction qui pourrait traverser un graphe général peut être trop lourde pour traverser une arborescence, car dans un arbre pur, il n'est pas nécessaire de vérifier les cycles. Cela fonctionnerait donc, mais il en serait de même pour quelque chose de plus simple.