Actvité 2

Compétences évaluées
Concevoir des solutions algorithmiques
Traduire un algorithme dans un langage de programmation

Tout TP non rendu avant la fin de la séance sera noté zéro.
Merci d'essayer de comprendre ces algorithmes (que nous reverrons en cours)
Tout copié collé de code sur internet sera noté zéro

Graphe orienté : liste d'ajacence¶

Représenter le graphe orienté graphe 1 ci-dessous sous la forme d'une liste d'adjacence.

Parcours en largeur et profondeur¶

Nous allons étudier le parcours en largeur et profondeur d'un graphe.

Parcours en largeur¶

L'idée du parcours en largeur repose sur l'utilisation d'une file de la manière suivante :

1) On part d'un sommet
2) On visite ses voisins directs et on les enfile s'ils ne sont pas déjà présents dans la file
3) On défile (c'est-à-dire qu'on enlève la tête de la file)
4) On recommence à partir du point 2 tant que la file n'est pas vide.

On utilise une file car on cherche à visiter les noeuds les plus proches d'abord.

Implémenter le pseudo-code suivant en Python.
Exécutez et vérifiez votre code sur le graphe graphe 1.

 ParcoursLargeur(Graphe G, Sommet s):
       f = CreerFile();
       f.enfiler(s);
       marquer(s);
       tant que la file est non vide
                s = f.defiler();
                afficher(s);
                pour tout voisin v de s dans G
                         si v non marqué
                                 f.enfiler(v);
                                 marquer(v);

Parcours en profondeur¶

Le parcours en profondeur d’un graphe à partir d’un sommet consiste à suivre les arêtes, en marquant les sommets déjà visités pour ne pas les visiter à nouveau.

Le but est de s'éloigner le plus possible lors du parcours du graphe.

On utilisera une pile cette fois-ci car on s'intéresse aux noeuds les plus éloignés.

Implémenter le pseudo-code suivant en Python.
Exécutez et vérifiez votre code sur le graphe graphe 1.

 parcoursProfondeur(Graphe G, Sommet s):
       p = CreerPile();
       p.empiler(s);
       tant que la pile est non vide
                s = p.depiler();
                si s non marqué
                    afficher(s);
                    marquer(s);
                    pour tout voisin v de s dans G
                        p.empiler(v);