L'objectif de ce TP est de compléter le module de graphe en ajoutant un affichage graphique pour les gaphes, des algorithmes de parcours en largeur et en profondeur et un algorithme de calcul de plus courts chemins.
Appliquer l'algorithme du parcours en largeur
PL(G, s) au graphe F de la figure 1 à partir du sommet
.
Vous donnerez à chaque fois l'ordre d'entrée des sommets dans la file.
Pour rappel, le parcours en largeur est l'algorithme suivant:
PL(G, s)
pour chaque sommet u de X[G] - {s} faire
couleur[u] <- BLANC
d[u] <- infini
pere[u] <- nil
couleur[s] <- GRIS
d[s] <- 0
pere[s] <- nil
Enfiler(F, s)
tant que non vide(F) faire
u <- tete(F)
pour chaque v de Adj(u) faire
si couleur[v] = BLANC
alors couleur[v] <- GRIS
d[v] <- d[u] + 1
pere[v] <- u
Enfiler(F, v)
Defiler(F)
couleur[u] <- NOIR
Implémentez le parcours en largeur.
Calculer les plus courts chemins du graphe $G_1$ à partir du sommet $s_1$.
Implémentez une fonction qui calcule les plus courts chemins à partir d'un sommet donné.
Qu'est-ce que l'accessibilité d'un sommet.
Pour le graphes de la figure 1, calculez les sommets accessibles depuis chaque sommet.
Ajouter à votre module de graphe un fonction permettant de calculer les sommets accéssibles depuis chaque sommet.
Appliquer l'algorithme de parcours en profondeur PP au graphe G de la figure 2.
Nous rappelons que le parcours en profondeur est l'algorithme suivant:
PP(G)
pour chaque sommet u de X faire
couleur[u] <- BLANC
pere[u] <- nil
temps <- 0
pour chaque sommet u de X faire
si couleur[u] = BLANC alors
Visiter_PP(u)
où Visiter_PP est défini par:
Visiter_PP(u)
couleur[u] <- GRIS
d[u] <- temps <- temps + 1
pour chaque v de Adj[u] faire
si couleur[v] = BLANC alors
pere[v] <- u
Visiter_PP(v)
couleur[u] <- NOIR
f[u] <- temps <- temps + 1
Implémentez le parcours en profondeur.
Rapellez la définition d'un cycle.
Est-ce que le graphe de la figure 2 possède un cycle ?
Donnez un algorithme simple pour détecter si un graphe possède un cycle.
Ajouter à votre module de graphe un fonction permettant de dire si un graphe contient un cycle.
Ce TP est inspiré du TD: TD2 et des TDs donnés au Licences Informatiques INF351 de l'Université Bordeaux 1.