Traversées de graphiques

La profondeur d'abord et la largeur d'abord sont deux manières courantes de parcourir un graphique.
Traversée de graphiqueest le processus consistant à visiter chaque sommet du graphique exactement une fois. Il existe deux manières courantes de parcourir un graphique :parcours en profondeur d'abord(ourecherche en profondeur d'abord) etparcours en largeur d'abord(ourecherche en largeur d'abord). 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 queTreeest une classe interne définie dans la classeAbstractGraph.AbstractGraph.Treeest différent de l'interfaceTreedéfinie dans Recherche d'un élément.AbstractGraph.Treeest une classe spécialisée conçue pour décrire la relation parent-enfant des nœuds, tandis que l'interfaceTreedé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.Treen'est pas défini comme un sous-type deTree.

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

La classeTreedéfinit sept méthodes. La méthodegetRoot()renvoie la racine de l'arbre. Vous pouvez obtenir l'ordre des sommets recherchés en appelant la méthodegetSearchOrder(). Vous pouvez appelergetParent(v)pour trouver le parent du sommetvdans la recherche. L'appel degetNumberOfVerticesFound()renvoie le nombre de sommets recherchés. La méthodegetPath(index)renvoie une liste de sommets depuis l'index de sommet spécifié jusqu'à la racine. L'appel deprintPath(v)affiche un chemin de la racine àv. Vous pouvez afficher toutes les arêtes de l'arborescence en utilisant la méthodeprintTree().

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!