Algorithmes sur les graphes

I/ Matrice d'adjacence

Dans cette partie, on considère le même graphe orienté que dans le chapitre précédent :

graphe = { 'A': ['B','C'],    
	   'B': ['A'],        
	   'C': ['A','B'] }
%3 A A B B A->B C C A->C B->A C->A C->B

1) Calcul de la matrice

def matrice(graphe):
	M = []
	sommets = graphe.keys()
	for i in sommets:
		ligne = [int(j in graphe[i]) for j in sommets]
		M.append(ligne)
	return M

Remarque : pour afficher la matrice, plutôt que

print(matrice)

il vaut mieux faire

for ligne in matrice:
    print(ligne)

qui affiche les lignes de la matrice l'une en-dessous de l'autre.

Remarque : l'ordre dans lequel les clés du dictionnaire sont ordonnées par la méthode keys n'est pas toujours le même. Ce n'est pas important lorsqu'il s'agit de graphes, mais on peut de toute façon y remédier en utilisant un orderedDict.

2) Calcul du graphe

def grapheor(matrice):
	g = {}
	N = len(matrice)
	for i in range(N):
		g[chr(65+i)] = []
	for i in range(N):
		adjlist = []
		for j in range(N):
			if matrice[i][j]==1:
				g[chr(65+i)].append(chr(65+j))
	return g

Pour engendrer automatiquement les noms des sommets, on utilise la fonction chr qui code l'Ascii. On rappelle que le code 65 représente un "A" (ici associé à la ligne 0 de la matrice).

II/ Graphes non orientés

Dans cette partie on considère des graphes non orientés. On prendra comme exemple, le graphe de Moser :

%3 A A B B A--B C C A--C D D A--D B--C F F B--F C--D E E D--E G G D--G E--F E--G F--G

Ce graphe peut être décrit par cette structure :

{'A': ['B', 'C', 'D'], 
 'B': ['A', 'C', 'F'], 
 'C': ['A', 'B', 'D'], 
 'D': ['A', 'C', 'E', 'G'], 
 'E': ['D', 'F', 'G'],
 'F': ['B', 'E', 'G'], 
 'G': ['D', 'E', 'F']}

1) Parcours

Un parcours de graphe est un ordre d'énumération de ses sommets.

a) Parcours en largeur (Konrad Zuse, 1945)

En partant du sommet A, qu'on colorie en vert pour se rappeler qu'on l'a déjà vu :

%3 A A B B A--B C C A--C D D A--D B--C F F B--F C--D E E D--E G G D--G E--F E--G F--G

On construit la liste des sommets déjà visités. Tout d'abord on ajoute à la liste (contenant déjà A), tous les voisins de A (coloriés en cyan) :

%3 A A B B A--B C C A--C D D A--D B--C F F B--F C--D E E D--E G G D--G E--F E--G F--G

Puis on ajoute les voisins des voisins (mais pas A puisqu'il a déjà été visité). Le seul voisin de B non encore visité est F :

%3 A A B B A--B C C A--C D D A--D B--C F F B--F C--D E E D--E G G D--G F--G E--F E--G

Tous les voisins de C ont déjà été visités. On colorie donc les voisins de D (en magenta):

%3 A A B B A--B C C A--C D D A--D B--C F F B--F C--D E E D--E G G D--G F--G E--F E--G

En Python, on a donc besoin de deux listes : visités qui est la liste des sommets déjà visités (ou coloriés), et à_voir qui contient la liste des sommets encore à voir.

def en_largeur(graphe):
	visités = []
	à_voir = list(graphe.keys())
	while à_voir:
		S = à_voir.pop(0)
		if S not in visités:
			visités.append(S)
		for T in graphe[S]:
			if T not in visités:
				à_voir.append(T)
	return visités

L'instruction S = à_voir.pop(0) fait que le prochain sommet qu'on va examiner est celui qui est au début de la liste, donc le moins récent puisque à_voir.append(T) fait que la tâche la plus récente est au contraire reléguée à la fin de la liste. La structure ainsi simulée est une file qu'on verra plus tard.

Le parcours du graphe de Moser en largeur est ABCDFEG.

b) Parcours en profondeur

Au lieu de traiter d'abord le plus ancien sommet de la liste à_faire, on peut aussi traiter au contraire le sommet le plus récent d'abord. On verra dans le chapitre sur les arbres que cela revient à aller en priorité vers les régions les plus profondes de l'arbre.

def en_profondeur(graphe):
	visités = []
	à_voir = list(graphe.keys())
	while à_voir:
		S = à_voir.pop()
		if S not in visités:
			for T in graphe[S]:
				if T not in visités:
					à_voir.append(T)
			visités.append(S)
	return visités

La structure simulée avec à_voir.append(T) et S = à_voir.pop() est une pile qui l'on verra également plus tard.

Le parcours en profondeur du graphe de Moser est ABFGEDC.

c) Version récursive

Pour effectuer un parcours du graphe en profondeur à partir d'un sommet, on peut, pour chacun des sommets qui lui sont adjacents et pas encore visités, effectuer un parcours en profondeur du graphe à partir de ce nouveau sommet :

def parcours(graphe,sommet,visités=[]):
	visités.append(sommet)
	for voisin in graphe[sommet]:
		if voisin not in visités:
			visités = parcours(graphe,voisin,visités)
	return visités

On remarque que la liste visités est passée en argument à chaque appel de la fonction. On dit qu'elle a été mémoïsée. Cet algorithme est un exemple de programmation dynamique : pour trouver un parcours en profondeur de tout le graphe, on utilise les parcours en profondeur des successeurs du sommet de départ.

Les parcours en largeur et en profondeur sont tous deux de complexité linéaire, par rapport au nombre de sommets, et par rapport au nombre d'arêtes du graphe.

2) Chemins

a) Définition

Un chemin est une suite de sommets tels que chacun est adjacent à la fois au précédent et au suivant.

b) Recherche

Un chemin d'un sommet S à un sommet T est

Il est donc possible de programmer récursivement la recherche d'un chemin entre deux sommets dans un graphe :

def chemin(S,T,graphe):
	if S==T:
		return S
	else:
		for R in graphe[T]:
			return chemin(S,R,graphe)+T

3) Cycles

Un cycle est un chemin dont le départ et l'arrivée coïncident.

On ne considère pas ABA comme un cycle (c'est une même arête parcourue dans les deux sens) mais ABC est un cycle, ainsi que ABCD etc.

Pour chercher si un graphe a un cycle, on le parcourt en profondeur et si jamais on trouve, au cours de ce parcours, un sommet

c'est qu'on a trouvé un cycle. On va donc afficher ces situations. 

def cycles(graphe,sommet,visités=[]):
	visités.append(sommet)
	for voisin in graphe[sommet]:
		if voisin not in visités:
			for s in visités:
				if s in graphe[voisin] and s!=sommet:
					print(visités+[voisin,s])
			visités = cycles(graphe,voisin,visités)
	return visités

Cet algorithme ne trouve pas tous les cycles du graphe de Moser, mais il trouve ABCA, ABCDA, BCDEFB, DEFGD et EFGE.

Le parcours en largeur permet également de détecter un cycle :