Activités

activité 10.1

Appliquez l'algorithme du parcours en largeur d'abord au graphe ci-dessous. Le 'point de départ' de notre parcours sera le sommet A. Vous noterez les sommets atteints à chaque étape ainsi que les sommets présents dans la file f. Vous pourrez aussi, à chaque étape, donner les changements de couleur des sommets.

activité 10.2

Appliquez l'algorithme du parcours en profondeur d'abord au graphe ci-dessous (d'abord avec l'algorithme récursif puis ensuite avec l'algorithme non récursif). Le 'point de départ' de notre parcours sera le sommet A. Vous noterez les sommets atteints à chaque étape ainsi que les sommets présents dans la pile p. Vous pourrez aussi, à chaque étape, donner les changements de couleur des sommets.

activité 10.3

Appliquez l'algorithme de détection d'un cycle au graphe ci-dessous (vous partirez du sommet de votre choix).

activité 10.4

Appliquez l'algorithme de détection d'un cycle au graphe ci-dessous (vous partirez du sommet de votre choix).

activité 10.5

Appliquez l'algorithme permettant de trouver une chaine entre un noeud de départ (start) et un noeud d'arrivée (end) au graphe ci-dessous (vous choisirez les noeuds de départ et d'arrivée de votre choix).

activité 10.6

1)

Soit le graphe suivant :

Proposez une implémentation de ce graphe en Python (graphe 1 dans la suite de cette activité)

2)

Soit l'algorithme de parcours en largeur d'abord :

VARIABLE
G : un graphe
s : noeud (origine)
u : noeud
v : noeud
f : file (initialement vide)

//On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine
DEBUT
s.couleur ← noir
enfiler (s,f)
tant que f non vide :
    u ← defiler(f)
    pour chaque sommet v adjacent au sommet u :
        si v.couleur n'est pas noir :
            v.couleur ← noir
            enfiler(v,f)
        fin si
    fin pour
fin tant que
FIN

Implémentez cet algorithme en Python. Vous testerez votre programme à l'aide du graphe 1. Il faudra que votre programme fournisse la liste des sommets parcourus en partant du sommet A (il faudra être attentif à l'ordre des sommets dans cette liste)

3)

Soit l'algorithme de parcours en profondeur d'abord (version non récursive):

VARIABLE
s : noeud (origine)
G : un graphe
u : noeud
v : noeud
p : pile (pile vide au départ)
//On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine
DEBUT
empiler(s,p)
tant que p n'est pas vide :
    u ← depiler(p)
    si u.couleur n'est pas noir :
        u.couleur ← noir
        pour chaque sommet v adjacent au sommet u :
            empiler(v,p)
        fin pour
    fin si
fin tant que
FIN

Implémentez cet algorithme en Python. Vous testerez votre programme à l'aide du graphe 1. Il faudra que votre programme fournisse la liste des sommets parcourus en partant du sommet A (il faudra être attentif à l'ordre des sommets dans cette liste)

4)

Soit l'algorithme de parcours en profondeur d'abord (version récursive):

VARIABLE
G : un graphe
u : noeud
v : noeud
//On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine
DEBUT
PARCOURS-PROFONDEUR(G,u) :
    u.couleur ← noir
    pour chaque sommet v adjacent au sommet u :
        si v.couleur n'est pas noir :
            PARCOURS-PROFONDEUR(G,v)
        fin si
    fin pour
FIN

Implémentez cet algorithme en Python. Vous testerez votre programme à l'aide du graphe 1. Il faudra que votre programme fournisse la liste des sommets parcourus en partant du sommet A (il faudra être attentif à l'ordre des sommets dans cette liste)

5)

Soit l'algorithme de détection des cycles :

VARIABLE
s : noeud (noeud quelconque)
G : un graphe
u : noeud
v : noeud
p : pile (vide au départ)
//On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine
DEBUT
CYCLE():
    piler(s,p)
    tant que p n'est pas vide :
        u ← depiler(p)
        pour chaque sommet v adjacent au sommet u :
            si v.couleur n'est pas noir :
                empiler(v,p)
            fin si
        fin pour
        si u est noir :
            renvoie Vrai
        sinon :
            u.couleur ← noir
        fin si
    fin tant que
    renvoie Faux
FIN

Implémentez cet algorithme en Python. Vous testerez votre programme à l'aide du graphe 1 et sur le graphe 2 (voir ci-dessous). Il faudra que votre fonction renvoie True si un cycle est présent et False dans le cas contraire

6)

Soit l'algorithme de recherche de chaine entre 2 sommets :

VARIABLE
G : un graphe
start : noeud (noeud de départ)
end : noeud (noeud d'arrivé)
u : noeud
chaine : ensemble de noeuds (initialement vide)

DEBUT
TROUVE-CHAINE(G, start, end, chaine):
    chaine = chaine ⋃ start //le symbol ⋃ signifie union, il permet d'ajouter le noeud start à l'ensemble chaine
    si start est identique à end :
        renvoie chaine
    fin si
    pour chaque sommet u adjacent au sommet start :
        si u n'appartient pas à chaine :
            nchemin = TROUVE-CHAINE(G, u, end, chaine)
            si nchemin non vide :
                renvoie nchemin
            fin si
        fin si
    fin pour
    renvoie NIL
FIN

Implémentez cet algorithme en Python. Vous testerez votre programme à l'aide du graphe 1 (sommet de départ A, sommet d'arrivée G). Il faudra que votre programme fournisse la liste des sommets qui constituent la chaine.