Algorithmique

⚙️ Chapitre : Algorithmes sur les graphes

1️⃣ Implémentation d'un graphe

Pour implémenter ce graphe, on peut utiliser un dictionnaire de liste de successeurs:

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

• Chaque clé a pour valeur la liste de ses voisins.

2️⃣ Parcours en profondeur (DFS)

Parcourir un graphe en profondeur consiste à explorer le graphe de voisin en voisin jusqu´à tomber sur une impasse ou un sommet déjà visité. La récursivité est ici à l´œuvre. En voici un exemple:

def parcours_profondeur_rec(graphe, sommet, visites=None):
    if visites is None:
        visites = []

    print(sommet)
    visites.append(sommet)

    for voisin in graphe[sommet]:
        if voisin not in visites:
            parcours_profondeur_rec(graphe, voisin, visites)

# Exemple d'appel
parcours_profondeur_rec(graphe, "A")

• On visite un sommet: print(sommet).
• On le marque comme visité (ajouté à la liste: visites.add(sommet)).
• On appelle récursivement la fonction sur ses voisins non visités.

Affiche: A → B → C → E → D (L’ordre exact dépend de l’ordre dans le dictionnaire.)

📊 Complexité:

• Chaque sommet est visité une seule fois.
• Chaque arête est parcourue au plus deux fois (graphe non orienté).

où :

• \( n \) = nombre de sommets
• \( m \) = nombre d’arêtes

3️⃣ Parcours en largeur (BFS)

L'algorithme de parcours en largeur (ou BFS, pour Breadth First Search en anglais) permet le parcours d'un graphe de la manière suivante : on commence par explorer un sommet source, puis ses successeurs, puis les successeurs non explorés des successeurs, etc. Comme pour les arbres, il utilise une file:

def parcours_largeur(graphe, depart):
    visites = []  # liste des sommets déjà visités
    file=[] # On crée une file vide
    file.append(depart) # On enfile le sommet de départ

    while file:
        sommet = file.pop(0)
        if sommet not in visites:
            print(sommet)
            visites.append(sommet)
            for voisin in graphe[sommet]:
                file.append(voisin)

# Exemple d'appel
parcours_largeur(graphe, "A")

On obtient: Affiche: A → B → C → D → E (L’ordre exact dépend de l’ordre dans le dictionnaire.)

• file.append correspond à enfiler
• file.pop(0) correspond à défiler

• Niveau 0 : A
• Niveau 1 : B
• Niveau 2 : C, D
• Niveau 3 : E

🔗 Un exercice intéressant avec DFS, Amérique du Nord – 2023.
🔗 Cet exercice aborde les parcours de graphes dans la partie B.