C12.2 : Implémentation des graphes

Implémentation sous forme d'une matrice d'adjacence

Présentation

Une implémentation possible d'un graphe est une matrice carrée (c'est-à-dire un tableau comprenant autant de lignes que de colonnes) que l'on appelle matrice d'adjacence.

Les colonnes et les lignes correspondent aux nœuds.

L'intersection entre une ligne est une colonne correspond à l'arc entre les nœuds correspondants. La cellule contient 0 si les nœuds ne sont pas reliés et 1 dans le cas contraire (pour les graphes orientés, il faut tenir compte de l'orientation).

Exemple

↱	A	B	C	D
A	0	1	1	1
B	0	0	1	1
C	0	0	0	0
D	0	0	0	0

Application (sur papier)

1) Représenter les matrices des graphes n° 1, n° 2 et n° 3.

2) Comment peut-on obtenir simplement le nombre de voisins d'un nœud à partir de la matrice d'adjacence ?

3) De quelle façon peut-on implémenter une matrice d'adjacence en Python ?

Un peu de python

Dans cette partie on travaillera avec des matrices implémentées par des listes de listes. Les nœuds d'un graphe seront identifiés par un nombre entier allant de 0 à n-1, n étant la taille du graphe.

Application I.3_app1

Compléter la fonction suivante :

def nb_successeurs(matrice, noeud):
    '''
    Fonction qui, à partir d'un graphe représenté par une matrice d'adjacence, renvoie :
        - le nombre de voisins de noeud si le graphe n'est pas orienté,
        - le nombre de successeurs de noeud si le graphe est orienté.
    Paramètres
        matrice (liste) : liste de liste représentant la matrice d'adjacence d'un graphe
        noeud (int) : entier correspondant à un nœud du graphe
    Valeur renvoyée
        return (int) : nombre entier correspondant au nombre de voisins
    '''
    pass

...

def nb_successeurs(matrice, noeud):
    '''
    Fonction qui, à partir d'un graphe représenté par une matrice d'adjacence, renvoie :
        - le nombre de voisins de noeud si le graphe n'est pas orienté,
        - le nombre de successeurs de noeud si le graphe est orienté.
    Paramètres
        matrice (liste) : liste de liste représentant la matrice d'adjacence d'un graphe
        noeud (int) : entier correspondant à un nœud du graphe
    Valeur renvoyée
        return (int) : nombre entier correspondant au nombre de voisins
    '''
    somme = 0
    for val in matrice[noeud]:
        somme += val
    return somme

def teste_nb_successeurs():
    m_teste = [[0,1,1,1],
               [0,0,1,1],
               [0,0,0,0],
               [0,0,0,0]]
    assert nb_successeurs(m_teste, 0) == 3
    print('Les tests sont ok')

# Programme principal
teste_nb_successeurs()

Application I.3_app2

Compléter la fonction suivante :

def sont_lies(matrice, noeud1, noeud2):
    '''
    Fonction qui permet de savoir si deux nœuds d'un graphe sont adjascents
    Paramètres
        matrice : (liste) liste de liste représentant la matrice d'adjacence d'un graphe
        noeud1 : (int) entier correspondant à un nœud du graphe
        noeud2 : (int) entier correspondant à un nœud du graphe
    Valeur renvoyée
        return (bool) : True si les deux nœuds sont adjascents et False sinon
    '''
    pass

...

def sont_lies(matrice, noeud1, noeud2):
    '''
    Fonction qui permet de savoir si deux nœuds d'un graphe sont adjascents
    Paramètres
        matrice : (liste) liste de liste représentant la matrice d'adjacence d'un graphe
        noeud1 : (int) entier correspondant à un nœud du graphe
        noeud2 : (int) entier correspondant à un nœud du graphe
    Valeur renvoyée
        return (bool) : True si les deux nœuds sont adjascents et False sinon
    '''
    return matrice[noeud1][noeud2] == 1


def teste_sont_lies():
    m_teste = [[0,1,1,1],
               [0,0,1,1],
               [0,0,0,0],
               [0,0,0,0]]
    assert sont_lies(m_teste, 2, 1) == False
    assert sont_lies(m_teste, 1, 2) == True
    print('Les tests sont ok')

# Programme principal
teste_sont_lies()

Implémentation sous forme d'une liste d'adjacences ou d'un dictionnaire d'adjacences

Présentation

Il est possible d'implémenter les graphes sous forme :

- d'une liste d'adjacence : liste dont chaque élément correspond à un nœud et est une liste des voisins (des successeurs ou des prédécesseurs) de ce nœud,
- d'un dictionnaire d'adjacence : dictionnaire dont les clés sont les étiquettes des nœuds et les valeurs les listes des voisins (des successeurs ou des prédécesseurs) du nœud.

Exemple de dictionnaires d'adjacences

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

Dictionnaire des listes de successeurs

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

Dictionnaire des listes de prédécesseurs

Applications

Application II.2_app1

1) Représenter les dictionnaires d'adjacences (successeurs si le graphe est orienté) des graphes n°1, n°2 et n°3.

...

graphe_1 = {
        0 : [1,2,3],
        1 : [0,4],
        2 : [0,3,4,5],
        3 : [0,2],
        4 : [1,2,5],
        5 : [2,4]
    }

Application II.2_app2

En python, écrire une fonction qui prend en paramètre un graphe sous la forme d'un dictionnaire des listes de successeurs et renvoie un dictionnaire dont les clés sont les nœuds et les valeurs le nombre de voisins des nœuds.

...

def dico_nb_voisins(dico_successeurs):
    dico = {}
    for noeud in dico_successeurs:
        dico[noeud] = len(dico_successeurs[noeud])
    return dico

def teste_dico_nb_voisins():
    graphe_teste = {
        "A" : ["B", "C", "D"],
        "B" : ["C", "D"],
        "C" : [],
        "D" : []
    }
    assert dico_nb_voisins(graphe_teste) == {"A" : 3, "B" : 2, "C" : 0, "D" : 0}
    print('Les testes sont ok')


# Programme principal
teste_dico_nb_voisins()

Application II.2_app3

En python, écrire une fonction qui prend en paramètre un graphe sous la forme d'un dictionnaire des listes de successeurs et renvoie le même graphe sous la forme d'un dictionnaire des listes de prédécesseurs.

...

def successeurs_to_predecesseurs(dico_successeurs):
    dico = {}
    for noeud in dico_successeurs:
        dico[noeud] = []
    for noeud_p in dico_successeurs:
        for noeud_s in dico_successeurs[noeud_p]:
            dico[noeud_s].append(noeud_p)
    return dico

def teste_successeurs_to_predecesseurs():
    graphe_succ = {
        "A" : ["B", "C", "D"],
        "B" : ["C", "D"],
        "C" : [],
        "D" : []
    }
    graphe_pred = {
        "A" : [],
        "B" : ["A"],
        "C" : ["A", "B"],
        "D" : ["A", "B"]
    }
    assert successeurs_to_predecesseurs(graphe_succ) == graphe_pred
    print('Les testes sont ok')


# Programme principal
teste_successeurs_to_predecesseurs()

Conversion d'une implémentation à une autre

Dans cette partie, on travaillera avec des graphes orientés dont les nœuds ont les valeurs de 0 à n-1, n étant la taille du graphe.

Application III_app1

Écrire une fonction qui prend en paramètre un graphe sous la forme d'un dictionnaire des listes de successeurs et renvoie le même graphe sous la forme d'une matrice d'adjacence.

...

def dico_to_matrice(dico_successeurs):
    # Création de la matrice avec uniquement des 0
    matrice = [[0 for i in range(len(dico_successeurs))] for j in range(len(dico_successeurs))]
    # 
    for noeud_p in dico_successeurs:
        for noeud_s in dico_successeurs[noeud_p]:
            matrice[noeud_p][noeud_s] = 1
    return matrice

def teste_dico_to_matrice():
    dico = {
        0 : [1, 2, 3],
        1 : [2, 3],
        2 : [],
        3 : []
    }
    matrice = [[0, 1, 1, 1],
               [0, 0, 1, 1],
               [0, 0, 0, 0],
               [0, 0, 0, 0]]
    assert dico_to_matrice(dico) == matrice
    print('Les tests sont ok')

# Programme principal
teste_dico_to_matrice()

Application III_app2

Écrire une fonction qui prend en paramètre un graphe sous la forme d'une matrice d'adjacence et renvoie le même graphe sous la forme d'un dictionnaire des listes de successeurs.

...

def matrice_to_dico(matrice):
    # Création du dictionnaire vide
    dico = {}
    for i in range(len(matrice)):
        dico[i] = []
    # 
    for noeud_p in range(len(matrice)):
        for noeud_s in range(len(matrice)):
            est_lie_p_s = matrice[noeud_p][noeud_s]
            if est_lie_p_s == 1:
                dico[noeud_p].append(noeud_s)
    return dico

def teste_matrice_to_dico():
    dico = {
        0 : [1, 2, 3],
        1 : [2, 3],
        2 : [],
        3 : []
    }
    matrice = [[0, 1, 1, 1],
               [0, 0, 1, 1],
               [0, 0, 0, 0],
               [0, 0, 0, 0]]
    assert matrice_to_dico(matrice) == dico
    print('Les tests sont ok')

# Programme principal
teste_matrice_to_dico()