Connexité
Algo 17
Résumé du cours
À retenir
Un parcours en profondeur avance dans le graphe jusqu’à une extrémité ou un nœud déjà visité. Il revient alors à un sommet précédent qui propose un autre chemin.
Le parcours en profondeur est naturellement récursif. On choisit un nœud de départ pour commencer le parcours, puis:
Si le nœud n’est pas déjà visité:
- faire quelque chose avec le nœud (afficher…)
- le marquer visité,
- pour tous les nœuds voisins:
- effectuer le parcours récursivement depuis le voisin sélectionné.
À retenir
Un graphe est connexe quand tout sommet peut être relié à tout autre par une chaîne.