T – 4 – Implémenter les graphes | Cercles informatiques

Une seconde implémentation : modéliser les matrices d'adjacences

Nous avons vu en cours comment représenter un graphe avec une matrice. Nous allons implémenter cette représentation en python.

La matrice ne contient pas les noms des sommets. En réalité, il n'est pas très pratique de modéliser cette matrice en utilisant des listes de listes, créer une classe graphe serait bien mieux adapté et nous y viendrons ensuite. Néanmoins il est possible de modéliser les graphes avec simplement une liste de liste pour la matrice d'adjacence, mais cela nous oblige à conserver en plus de la matrice, un vecteur contenant les clés.

Pour cette raison, le graphe sera donc représenté ainsi :

G={ 'cles' : [liste des cles] , 'matrice' : [ [...] [...]...[...] ] }

Attention, cette implémentation est difficile et non exigible, mais essayez de l'étudier de près, elle est riche en enseignements.
Pour des raisons technique (limite du nombre de ligne des codes exemple) ce code est très condensé et manque de lisibilité, ce n'est pas très recommandé de mettre plusieurs instructions sur une même ligne...

Exemple : implémentation des graphes avec un dictionnaire

Premier exemple d'implémentation d'un graphe, en utilisant une liste de dictionnaire donc les clés sont les sommets et les valeurs les listes d'adjacence des sommets.

def  creerGrapheVide() -> dict:
    return {'cles':[],'matrice':[]}
def estVideGraphe(G : dict) -> bool :
    return G=={'cles':{} , 'matrice':[]}
def ajouterSommet(G : dict ,s) -> dict : # s est int ou str
    G['cles'].append(s)
    G['matrice'].append([0 for i in range(len(G['matrice']))])
    for ligne in G['matrice']:
        ligne.append(0)
def ajouterArete(G : dict , sd , sa ) -> dict: # sd et sa sont int ou str
    i=G['cles'].index(sd) ; j=G['cles'].index(sa)
    G['matrice'][i][j] =  G['matrice'][j][i] = 1
def supprimerSommet(G : dict , s ) -> dict: # s est int ou str
    i=G['cles'].index(s) ; G['cles'].remove(s)
    for ligne in G['matrice'] :
         del ligne[i]
    del G['matrice'][i]
def supprimerArete(G : dict ,sd,sa) -> dict : # sd et sa sont int ou str
    i=G['cles'].index(sd) ; j=G['cles'].index(sa)
    G['matrice'][i][j] = 0
    G['matrice'][j][i] = 0
def existeArete(G : dict ,sd,sa) -> dict : # sd et sa sont int ou str
    i=G['cles'].index(sd)
    j=G['cles'].index(sa)
    return G['matrice'][i][j] == G['matrice'][j][i] == 1
def existeSommet(G : dict ,s) -> bool : # s est int ou str
    return s in G['cles']
def showG(G : dict) :
    print('clés:',G['cles'])
    for ligne in G['matrice']:
        print(ligne)
G=creerGrapheVide()
ajouterSommet(G,'A') ; ajouterSommet(G,'B') ; ajouterSommet(G,'C') ; ajouterSommet(G,'D')
ajouterArete(G,'A','B') ; ajouterArete(G,'C','D')
print('après ajout des 4 sommets et de des arc A->B et C->D:') ; showG(G)
supprimerSommet(G,'D')
print('Après suppression du sommet D,  G = ') ; showG(G)
print('A-B existe :',existeArete(G,'A','B'))
supprimerArete(G,'A','B')
print('Après suppression de l arete A-B :')
print('A-B existe :',existeArete(G,'A','B'))
showG(G)

Bien que l'implémentation soit plus compliquée, vous remarquerez que la création d'un graphe est ensuite identique au cas des graphes implémentés avec une liste d'adjacence et un dictionnaire puisque les primitives sont identiques avec les mêmes arguments.
Modifier l'implémentation pour modéliser des graphes orientés, et/ou pondérés, ne poserait pas de grandes difficultés.

L'exercice ci-dessous va vous permettre d'utiliser cette nouvelle implémentation pour générer un graphe avec sa matrice d’adjacence.

4. Utiliser la matrice d'adjacence

Les fonctions ajouterArete, ajouterSommet, creerGrapheVide, estVideGraphe, existeArete, existeSommet, showG, supprimerArete, et supprimerSommet ont été défini préalablement et n'apparaissent pas dans le code ci-dessous

Pages : 1 2 3 4