TP graphes et algorithmique

On commence par corriger la recherche de plus court chemin donnée pour aujourd’hui :

Pour demain : un autre parcours

Plus court chemin de H à E ?


TP – algorithmique des graphes

Dans un premier temps, autocorrection des implémentations pour aujourd’hui : corriger ou faire si pas fait ! Les codes corrigés sont disponibles ci-dessous ou en cliquant sur « lire la suite ».

Puis implémenter la recherche de cycles (algorithme en pseudo-code à « À faire vous-même 8 » sur cette page de l’excellent David Roche) et pour les plus valeureuses et les plus valeureux l’algorithme de Dijkstra.


Corrigés des codes pour aujourd’hui

Implémentation d’un graphe avec une matrice d’adjacence :

"""Une implémentation de graphe par matrice d'adjacence
et liste de sommets """

# liste de sommets
L = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
# facultatif : dictionnaire inversé
dico = {L[i] : i for i in range(len(L))}

# matrice d'adjacence

M = [[0, 1, 1, 0, 0, 0, 0, 1, 0],
     [1, 0, 0, 0, 0, 0, 0, 0, 1],
     [1, 0, 0, 1, 1, 0, 0, 0, 0],
     [0, 0, 1, 0, 1, 0, 0, 0, 0],
     [0, 0, 1, 1, 0, 0, 1, 0, 0],
     [0, 0, 0, 0, 0, 0, 1, 0, 1],
     [0, 0, 0, 0, 1, 1, 0, 1, 0],
     [1, 0, 0, 0, 0, 0, 1, 0, 1],
     [0, 1, 0, 0, 0, 1, 0, 1, 0]]


def ajouter_sommet(s):
    """
    ajoute le sommet s au graphe
    @param s: string
    @return: None
    """
    # ajout d'un zéro à chaque ligne
    for ligne in M:
        ligne.append(0)
    # ajout d'une ligne
    M.append([0 for i in range(len(M) + 1)])
    # ajout à la liste des sommets
    L.append(s)
    dico[s] = len(L) - 1

ajouter_sommet('K')

#tests
def afficher():
    for ligne in M:
        print(ligne)
    print(L)
    print(dico)
#afficher()


def ajouter_arete(s1, s2):
    """
    ajoute une arête dans le graphe liant s1 à s2
    @param s1: string
    @param s2: string
    @return: None
    """

    i1 = dico[s1]
    i2 = dico[s2]
    M[i1][i2] = 1
    M[i2][i1] = 1


ajouter_arete('A','E')
ajouter_arete('B','C')
ajouter_arete('H','K')
ajouter_arete('B','K')
ajouter_arete('K', 'F')

# afficher()


def supprimer_arete(s1, s2):
    """
    supprime une arête liant s1 à s2
    @param s1: string
    @param s2: string
    @return: None
    """

    i1 = dico[s1]
    i2 = dico[s2]
    M[i1][i2] = 0
    M[i2][i1] = 0


supprimer_arete('A', 'C')
afficher()

def supprimer_sommet(s):
    """
    Supprime s et toutes ses arêtes du graphe
    @param s: string
    @return: None
    """
    # suppression des arêtes
    i = dico[s]

    for ligne in M:
        # pour chaque sommet e
        # on enlève s de la liste
        del(ligne[i])
    del(M[i])

    # suppression du sommet
    del L[i]
    del dico[s]


supprimer_sommet('I')
afficher()

Parcours en profondeur récursif:

On a ici choisi l’implémentation par listes d’adjacence dans un dictionnaire.

# clés : sommets
# valeurs : liste d'adjacence du sommet en clé
g = {'A' : ['B', 'C', 'H'],
     'B' : ['A', 'I'],
     'C' : ['A', 'D', 'E'],
     'D' : ['C', 'E'],
     'E' : ['C', 'D', 'G'],
     'F' : ['G', 'I'],
     'G' : ['E', 'F', 'H'],
     'H' : ['A', 'G', 'I'],
     'I' : ['B', 'F', 'H']}

def parcours_profondeur_recursif(g, s, liste_marques = []):
    # liste_marques : une liste des sommets visités par défaut à []
    # print(s, end = '\t')
    liste_marques.append(s)
    for e in g[s]:
        if e not in liste_marques:
            liste_marques = parcours_profondeur_recursif(g, e, liste_marques)
    return liste_marques

print(parcours_profondeur_recursif(g, 'H'))

Parcours en largeur (avec une file) :

On a ici choisi l’implémentation par listes d’adjacence dans un dictionnaire.

from primitives import *

# clés : sommets
# valeurs : liste d'adjacence du sommet en clé
g = {'A' : ['B', 'C', 'H'],
     'B' : ['A', 'I'],
     'C' : ['A', 'D', 'E'],
     'D' : ['C', 'E'],
     'E' : ['C', 'D', 'G'],
     'F' : ['G', 'I'],
     'G' : ['E', 'F', 'H'],
     'H' : ['A', 'G', 'I'],
     'I' : ['B', 'F', 'H']}

def parcours_largeur(g, s):
    # une liste des sommets visités
    liste_marques = []
    # une pile vide
    F = creer_file_vide()
    # On enfile le sommet de départ
    enfiler(F, s)
    # tant que la file n'est pas vide
    while not est_file_vide(F):
        # je défile un sommet
        sommet = defiler(F)
        # je visite le sommet
        if sommet not in liste_marques:
            liste_marques.append(sommet)
        # j'enfile ses voisins non visités
        for elt in g[sommet]:
            # si le voisin n'est pas visité
            if elt not in liste_marques:
                # on l'empile
                enfiler(F, elt)
    # je renvoie mon parcours
    return liste_marques

print(parcours_largeur(g, 'H'))

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.