Parcours d'un graphe
Le parcours d'un graphe consiste, comme les arbres, à parcourir l'ensemble des sommets d'un graphe. On doit simplement préciser un sommet de départ.
Fondamental : Concept général
Tous les parcours de graphe sont très similaires.
On découpe le graphe en 3 ensembles de sommets :
Les sommets déjà visités
La coupe : l'ensemble de sommet connus mais non encore visité
Les sommets non encore rencontrés
Il s'agit alors de savoir dans quel ordre on choisit le prochain sommet à visiter dans la coupe.
Par exemple, dans ce parcours, en partant de 1, nous avons :
Les sommet déjà visités : 1
La coupe : 2 et 6
Les sommets non encore rencontrés : 3, 4 et 5
Parcours en largeur - BFS (Breadth-First Search)
Il s'agit du même parcours que pour celui des arbres, on parcours d'abord tout les nœuds à distance 1 de la source, puis 2, et ainsi de suite.
Ce parcours n'est pas unique !
Méthode :
Dans ce cas, la coupe est une file, le premier sommet ajouté à la coupe est le premier à visiter.
Remarque :
Ce parcours n'est pas unique !
Exemple :
En partant de 6 :
6 - 4 - 2 - 1 - 5 - 36 - 1 - 2 - 4 - 3 - 5...
Impossible d'accéder à la ressource audio ou vidéo à l'adresse :
La ressource n'est plus disponible ou vous n'êtes pas autorisé à y accéder. Veuillez vérifier votre accès puis recharger le média.
Parcours en profondeur - DFS (Depth-First Search)
Ce parcours consiste à aller le plus loin possible avant de revenir aux sommets précédents (comme le parcours préfixe des arbres).
Méthode :
Dans ce cas, la coupe est une pile, le dernier sommet ajouté à la coupe est le premier à visiter.
Remarque :
Ce parcours n'est pas unique !
Exemple :
En partant de 6 :
6 - 1 - 2 - 3 - 4 - 56 - 4 - 5 - 3 - 2 - 1...
Impossible d'accéder à la ressource audio ou vidéo à l'adresse :
La ressource n'est plus disponible ou vous n'êtes pas autorisé à y accéder. Veuillez vérifier votre accès puis recharger le média.