Algorithmes sur les graphes

Numérique et Sciences Informatiques

donnees

Algorithmes sur les graphes :

Le parcours de graphes est une opération qui consiste à visiter tous les sommets d'un graphe de manière systématique. Il existe deux algorithmes classiques pour le parcours de graphes : le parcours en profondeur (DFS) et le parcours en largeur (BFS).

Différentes solutions sont possibles mais en règle générale celles-ci tiennent à jour deux listes : la liste des sommets rencontrés (« déjà_vus ») et la liste des sommets en cours de traitement (« à_traiter ») et ces méthodes vont différer par la façon dont sont insérés puis retirés les sommets dans cette structure de données.

Coût du parcours

Lors d’un parcours, chaque sommet entre au plus une fois dans la liste des sommets à traiter, et n’en sort donc aussi qu’au plus une fois. Si ces opérations d’entrée et de sortie dans la liste sont de coût constant (ce qui sera effectivement le cas dans la suite), le coût total des manipulations de la liste « àTraiter » est un O(n), avec n = |V|. Chaque liste d’adjacence est parcourue au plus une fois donc le temps total consacré à scruter les listes de voisinage est un O(p) avec p = |E|, à condition de déterminer si un sommet a déjà été vu en coût constant. Dans ce cas, le coût total d’un parcours est un O(n + p).

Parcours en largeur

L’algorithme de parcours en largeur (appelé BFS, pour Breadth First Search) consiste à utiliser une file d’attente pour stocker les sommets à traiter : tous les voisins sont traités avant de parcourir le reste du graphe. Ainsi, sont traités successivement tous les sommets à une distance égale à 1 du sommet initial, puis à une distance égale à 2, etc. Ce type de parcours est donc idéal pour trouver la plus courte distance entre deux sommets du graphe.

graphe
Graphe G

Sur ce graphe G 0-1-3-6-4-8-5-7-2 est un parcours en largeur au départ de 0. 2-5-6-7-0-1-3-4-8 est un parcours en largeur au départ de 2. 

parcours_largeur(G, s):
	    f = file_vide()
	    enfiler(f, s)
	    découverts = {s}   	   			# ou marquer s comme découvert
    tant que f n’est pas vide :
	        s = défiler(f)
	        pour v dans voisins(s):
	                si v n’est pas dans découverts :
                    ajouter v à découverts                   # ou marquer v comme découvert
                    enfiler(f, v)

Entraînement 1 :

Implémenter une fonction pour un parcours en largeur d'un graphe G.

Voir une solution

Parcours en profondeur

L’algorithme de parcours en profondeur (appelé DFS, pour Depth First Search) consiste à utiliser une pile pour stocker les éléments à traiter. Cette fois, on explore chaque chemin jusqu’au bout avant de passer au chemin suivant.
Si on utilise une pile pour S, les sommets enregistrés en dernier vont être visités en premier : on parcourt le graphe en visitant à chaque fois un voisin du dernier sommet, sauf si celui-ci n’a pas de voisin non visité, auquel cas on remonte au dernier sommet ayant un voisin non visité.

Le DFS peut être utilisé pour trouver des cycles dans le graphe ou pour parcourir un arbre.

graphe
Graphe G

Sur le graphe précédent,0-1-4-7-5-2-6-3-8 est un parcours en profondeur au départ de 0. 2-5-6-3-8-0-1-7 est un parcours en profondeur au départ de 2 . 

parcours_profondeur(G, s):
	    p = pile_vide()
	    empiler(p, s)
	    visités = {}
	    Tant que p n’est pas vide :
	        s = depiler(p)
	        si s n’est pas déjà visité :
	            ajouter s à visités       
	            pour v dans voisins(s):
	                si v n’est pas dans visités :
                    	empiler(p, v)

Cycle dans les graphes

Application : Réseau routier

Un réseau routier est représenté par un graphe pondéré, qui peut être orienté s’il y a des sens uniques ou si les temps de trajets ne sont pas les mêmes dans les deux sens.
Les villes sont les sommets du graphe et les arêtes les routes. Les distances sont indiquées sur les arêtes.


graphe
Réseau routier simplifié entre plusieurs villes françaises : Aire-sur-Adour, Bordeaux, Cherbourg-en-Cotentin, Clermont-Ferrand, Lyon, Montpellier, Paris, Strasbourg, Toulouse. Sur les arêtes bleues, la vitesse moyenne est 110 km/h, sur les vertes 95 km/h et sur les rouges 75 km/h.

Entraînement 2 :

Écrire les variables Python représentant les sommets du graphe ci-dessus dans une listesommets

Entraînement 2 :

Représenter le graphe ci-dessus à l'aide d'un dictionnaire avec la liste de successeurs graph

Entraînement 3 :

Représenter le graphe ci-dessus sous forme de matrice d’adjacence matrice

Entraînement 4 :

Écrire la fonction voisins(graph) qui, à partir d’un graphe g représenté par un dictionnaire, renvoie la liste de ses sommets.

Entraînement 5 :

Écrire la fonction voisins(graph, ville1) qui renvoie la liste des voisins du sommet ville1 dans un graphe non orienté g.

Entraînement 6 :

Écrire la fonction sont_voisins(graph, ville1, ville2) qui renvoie True si les deux sommets ville1 et ville2 sont adjacents dans le graphe non orienté g, False sinon.

Entraînement 7 :

Écrire la fonction distance(graph,matrice, ville1, ville2) qui renvoie la distance entre les deux sommets ville1 et ville2 adjacents.

Entraînement 8 :

Écrire la fonctionchemin(graph, ville1, ville2) qui donne la liste des villes à parcourir pour aller de ville1 à ville2. L’utilisation du parcours en profondeur est conseillée.

Entraînement 9 :

Écrire la fonction distance_chemin(graph,matrice, ville1, ville2) qui renvoie la distance entre les deux sommets ville1 et ville2.

Entraînement 10 :

Coder l’algorithme de Dijkstra pour déterminer le plus court chemin entre deux villes sur le graphe du réseau routier (en km ou en temps au choix).



Savoir faire


Fiche de cours