Traversées de graphiques

La profondeur d'abord et la largeur d'abord sont deux manières courantes de parcourir un graphique.
Le Traversée du graphique est le processus consistant à visiter chaque sommet du graphique exactement une fois. Il existe deux manières courantes de parcourir un graphique : le parcours en profondeur d'abord (ou recherche en profondeur d'abord) et le parcours en largeur d'abord (ou parcours en largeur -première recherche). Les deux parcours aboutissent à un arbre couvrant, qui peut être modélisé à l'aide d'une classe, comme le montre la figure ci-dessous. Notez que Tree est une classe interne définie dans la classe AbstractGraph. AbstractGraph.Tree est différent de l'interface Tree définie dans Recherche d'un élément. AbstractGraph.Tree est une classe spécialisée conçue pour décrire la relation parent-enfant des nœuds, tandis que l'interface Tree définit des opérations courantes telles que la recherche, l'insertion et la suppression dans un arbre. Puisqu'il n'est pas nécessaire d'effectuer ces opérations pour un arbre couvrant, AbstractGraph.Tree n'est pas défini comme un sous-type de Tree.

La classe Tree est définie comme une classe interne dans la classe AbstractGraph aux lignes 226 à 293 de AbstractGraph.java. Le constructeur crée un arbre avec la racine, les arêtes et un ordre de recherche.

La classe Tree définit sept méthodes. La méthode getRoot() renvoie la racine de l'arbre. Vous pouvez obtenir l'ordre des sommets recherchés en appelant la méthode getSearchOrder(). Vous pouvez appeler getParent(v) pour trouver le parent du sommet v dans la recherche. L’appel de getNumberOfVerticesFound() renvoie le nombre de sommets recherchés. La méthode getPath(index) renvoie une liste de sommets depuis l'index de sommet spécifié jusqu'à la racine. L'appel de printPath(v) affiche un chemin de la racine à v. Vous pouvez afficher toutes les arêtes de l'arborescence en utilisant la méthode printTree().

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!