Graphe - Implémentation de graphes

Exercice 10 : Nous considérons ici les graphes ayant pour ensemble de sommets des intervalles d'entiers de la forme $[1,n]$ avec $n \geq 0$. Décrire une implémentation de ces graphes comprenant notamment les primitives usuelles en utilisant

1. une matrice de booléens de taille $n \times n$
2. un tableau de $n$ listes de sommets

Les primitives usuelles sont adjacence, degré, liste_voisins.

Avec une matrice de booléens

fonction adjacence(M: matrice, sommet u, sommet v): booléen
    retourne M[u][v]

fonction degré(M: matrice, sommet u): entier
    n= dimension M
    deg = 0
    pour i de 1 à n
        deg+=M[u][i]
    retourner deg

fonction liste_voisins(M: matrice, sommet u):liste
    n= dimension M
    liste= []
    pour i allant de 1 à n
        si M[u][i]!=0
            liste+=i
    retourner liste

Avec un Tableau de $n$ listes de sommets

fonction adjacence (T: tableau, u: entier, v: entier): booléen
    pour i de 1 à |T|
        si T[u][i]==v
            retourner Vrai
    retourner Faux

fonction degré(T: tableau, u: entier): entier
    retourner |T[u]|

fonction liste_voisins(T: tableau, u: entier): liste
    retourner T[u]