Notions abordées : graphes, représentation des graphes, matrice d'adjacence, listes d'adjacence.
On considère ici des graphes orientés simples finis et l'on souhaite représenter ces graphes et les opérations de base sur ces graphes en utilisant une matrice d'adjacence.
graphe
. On fixera le
nombre maximum de sommets du graphe et on utilisera une matrice de
booléens.Grnouv()
(création d'un graphe vide), Adjs(x)
(ajout d'un sommet), Adja(g,x,y)
(ajout d'un arc)
.sups(g,x)
(suppression
d'un sommet), supa(g,x,y)
(suppression d'un arc).exs(g,x)
(existence d'un
sommet), exa(g,x,y)
(existence d'un arc), di(g,x)
(nombre d'arcs entrant en un sommet), de(g,x)
(nombre
d'arcs partant d'un sommet).
On considère ici des graphes orientés simples finis et
l'on souhaite les représenter en utilisant pour chaque sommet x
la liste des sommets y
tels qu'il existe une arc de x
à y
(liste d'adjacence). On représentera le type
abstrait des listes par des listes chaînées en utilisant des pointeurs
(définition les opérations de base sur les listes).
Répondre aux mêmes questions que dans la section précédente, mais en utilisant cette nouvelle représentation.