Les graphes

Mémo

Vocabulaire

Graphe: Ensemble de sommets (ou nœuds) reliés par des arêtes (non orienté) ou des arcs (orienté).
Graphe orienté: Les liens ont un sens : un arc de $A$ vers $B$ ne signifie pas qu'il y a un arc de $B$ vers $A$.
Graphe non orienté: Les liens sont symétriques : une arête entre $A$ et $B$ va dans les deux sens.
Voisins (adjacents): Sommets directement reliés à un sommet donné.
Degré: Nombre de voisins d'un sommet.
Chemin: Suite de sommets consécutivement reliés.
Cycle: Chemin qui revient à son point de départ.
Graphe connexe: Il existe un chemin entre toute paire de sommets.
Graphe pondéré: Chaque arête porte un poids (distance, coût…).

Représentations

Matrice d'adjacence: Tableau $n × n$ où $M[i][j] = 1$ s'il existe une arête de $i$ vers $j$, 0 sinon. Pour un graphe pondéré, on met le poids à la place de 1.
Liste d'adjacence: Dictionnaire : chaque sommet est associé à la liste de ses voisins.

(Figure : voir la version PDF pour la représentation graphique)

{0.35}

(Tableau : voir la version PDF)

{0.35}

graphe = {
  "A": ["B", "C"],
  "B": ["A", "D"],
  "C": ["A", "D"],
  "D": ["B", "C"]
}

Parcours en profondeur (DFS)

On explore le plus loin possible avant de revenir en arrière. Utilise une pile (ou la récursion).

def dfs(graphe, depart):
    visites = set()
    pile = [depart]
    while pile:
        sommet = pile.pop()
        if sommet not in visites:
            visites.add(sommet)
            for voisin in graphe[sommet]:
                pile.append(voisin)
    return visites

Parcours en largeur (BFS)

On explore tous les voisins d'abord, puis les voisins des voisins. Utilise une file.

from collections import deque

def bfs(graphe, depart):
    visites = set()
    file = deque([depart])
    visites.add(depart)
    while file:
        sommet = file.popleft()
        for voisin in graphe[sommet]:
            if voisin not in visites:
                visites.add(voisin)
                file.append(voisin)
    return visites

Le BFS donne le plus court chemin (en nombre d'arêtes) dans un graphe non pondéré.

Exemples

Création d'un graphe (liste d'adjacence)

graphe = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"]
}

(Graphe : voir la version PDF pour la représentation graphique)

DFS récursif

def dfs_rec(graphe, sommet, visites=None):
    if visites is None:
        visites = set()
    visites.add(sommet)
    print(sommet, end=" ")
    for voisin in graphe[sommet]:
        if voisin not in visites:
            dfs_rec(graphe, voisin, visites)
    return visites

# dfs_rec(graphe, "A") donne A B C D (ou autre ordre selon les voisins)

BFS avec reconstruction du chemin

def bfs_chemin(graphe, depart, arrivee):
    file = deque([depart])
    visites = {depart}
    parent = {depart: None}
    while file:
        sommet = file.popleft()
        if sommet == arrivee:
            # Reconstruction du chemin
            chemin = []
            while sommet is not None:
                chemin.append(sommet)
                sommet = parent[sommet]
            return chemin[::-1]
        for voisin in graphe[sommet]:
            if voisin not in visites:
                visites.add(voisin)
                parent[voisin] = sommet
                file.append(voisin)
    return None   # pas de chemin

Détection de cycle (graphe non orienté)

def a_cycle(graphe):
    visites = set()
    for sommet in graphe:
        if sommet not in visites:
            if _dfs_cycle(graphe, sommet, None, visites):
                return True
    return False

def _dfs_cycle(graphe, sommet, parent, visites):
    visites.add(sommet)
    for voisin in graphe[sommet]:
        if voisin not in visites:
            if _dfs_cycle(graphe, voisin, sommet, visites):
                return True
        elif voisin != parent:
            return True
    return False

Composantes connexes

def composantes_connexes(graphe):
    visites = set()
    composantes = []
    for sommet in graphe:
        if sommet not in visites:
            composante = set()
            dfs_composante(graphe, sommet, visites, composante)
            composantes.append(composante)
    return composantes

def dfs_composante(graphe, sommet, visites, composante):
    visites.add(sommet)
    composante.add(sommet)
    for voisin in graphe[sommet]:
        if voisin not in visites:
            dfs_composante(graphe, voisin, visites, composante)

Exercices

Exercice 1 — Représentations

3 pts

Soit le graphe non orienté suivant :

(Graphe : voir la version PDF pour la représentation graphique)

Donner la matrice d'adjacence.
Donner la liste d'adjacence (dictionnaire).
Donner le degré de chaque sommet.
Ce graphe est-il connexe ? Comporte-t-il un cycle ?

▶ Voir la solution

1. Matrice d'adjacence :

1  2  3  4  5
1 [ 0, 1, 1, 0, 0 ]
2 [ 1, 0, 0, 1, 0 ]
3 [ 1, 0, 0, 1, 1 ]
4 [ 0, 1, 1, 0, 1 ]
5 [ 0, 0, 1, 1, 0 ]

Matrice symétrique (graphe non orienté).

2. Liste d'adjacence :

{1: [2, 3], 2: [1, 4], 3: [1, 4, 5], 4: [2, 3, 5], 5: [3, 4]}

3. Degrés : sommet 1 : 2 ; sommet 2 : 2 ; sommet 3 : 3 ; sommet 4 : 3 ; sommet 5 : 2.

On vérifie : la somme des degrés vaut $2 + 2 + 3 + 3 + 2 = 12 = 2 × 6$ (deux fois le nombre d'arêtes). ✓

4. Le graphe est connexe (on peut atteindre tout sommet depuis tout autre sommet). Il comporte des cycles, par exemple $1 - 2 - 4 - 3 - 1$ ou $3 - 4 - 5 - 3$.

Exercice 2 — Parcours

3 pts

En utilisant le graphe de l'exercice précédent :

Donner l'ordre de visite du DFS en partant du sommet 1 (en choisissant les voisins dans l'ordre croissant).
Donner l'ordre de visite du BFS en partant du sommet 1.
Donner le plus court chemin de 2 à 5 (en nombre d'arêtes). Justifier avec le BFS.

▶ Voir la solution

1. DFS depuis 1 (voisins en ordre croissant) :

Visite 1, empile [2, 3]. Dépile 3.
Visite 3, empile [1, 4, 5]. 1 déjà visité. Dépile 5.
Visite 5, empile [3, 4]. 3 déjà visité. Dépile 4.
Visite 4, empile [2, 3, 5]. 3 et 5 déjà visités. Dépile 2.
Visite 2. Tous ses voisins sont visités.

Ordre : 1, 3, 5, 4, 2.

Remarque : avec la version pile (itérative), le dernier voisin ajouté est visité en premier, ce qui explique que 3 est visité avant 2.

Avec la version récursive (voisins en ordre croissant), on obtiendrait 1, 2, 4, 3, 5.

2. BFS depuis 1 :

File : [1]. Visite 1, enfile [2, 3].
File : [2, 3]. Visite 2, enfile [4]. File : [3, 4].
Visite 3, enfile [5] (4 déjà visité par 2). File : [4, 5].
Visite 4. Tous ses voisins sont visités. File : [5].
Visite 5. File vide.

Ordre : 1, 2, 3, 4, 5.

3. Plus court chemin de 2 à 5 :

Le BFS depuis 2 visite les sommets par distance croissante :

Distance 0 : {2} ;
Distance 1 : {1, 4} ;
Distance 2 : {3, 5}.

Le plus court chemin est de longueur 2. Par exemple : $2 - 4 - 5$.

Exercice 3 — Algorithme de plus court chemin

3 pts

Écrire une fonction distance(graphe, depart, arrivee) qui renvoie la longueur du plus court chemin (en nombre d'arêtes) entre deux sommets d'un graphe non pondéré.

Renvoyer $-1$ si aucun chemin n'existe.

▶ Voir la solution

from collections import deque

def distance(graphe, depart, arrivee):
    if depart == arrivee:
        return 0
    visites = {depart}
    file = deque([(depart, 0)])
    while file:
        sommet, dist = file.popleft()
        for voisin in graphe[sommet]:
            if voisin == arrivee:
                return dist + 1
            if voisin not in visites:
                visites.add(voisin)
                file.append((voisin, dist + 1))
    return -1

Principe : c'est un BFS classique où l'on stocke la distance dans la file. Le premier chemin trouvé vers arrivee est garanti le plus court (propriété fondamentale du BFS).

Complexité : $O(S + A)$ où $S$ est le nombre de sommets et $A$ le nombre d'arêtes.

← Retour aux fiches