C12 : Graphes
💚 Vocabulaire
Arbres
Structure de donnée
Un graphe est une structure de donnée relationnelle.
Structure d'un graphe
Sommets/nœuds et arêtes/arcs
Un graphe est un ensemble de sommets/nœuds reliés entre eux par des arêtes/arcs.
Graphe orienté ou non orienté
Lorsque le sens des liaisons entre les nœuds est pris en compte, on parle de graphe orienté.
Lorsque le sens des liens entre les nœuds n'est pas pris en compte, on parle de graphe non orienté.
Remarque : on utilise plutôt le terme arc pour les graphes orientés, et le terme arête pour les graphes non orientés.
Stockage de données
Les sommets comme les arêtes peuvent être associés à des données.
Vocabulaire
Taille
On appelle taille du graphe le nombre de sommets (nœuds) de ce graphe.
Chemin
Un chemin entre deux nœuds est une séquence finie de nœuds et/ou d'arcs (arêtes) permettant de les relier.
La longueur d'un chemin est le nombre d'arcs (arêtes) de ce chemin.
Vocabulaire concernant les nœuds voisins
Deux nœuds sont dits adjacents ou voisins s'ils sont reliés par un arc (arête).
Dans le cas d'un graphe orienté, on distingue les successeurs et les prédécesseurs.
Cycle
Dans un graphe, un cycle est un chemin dont les extrémités sont identiques.
Implémentation d'un graphe
Matrice d'adjacence
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 (comme 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.
| ↱ | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 |
| B | 0 | 0 | 1 | 1 |
| C | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 |
Liste d'adjacence
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.
Dictionnaire d'adjacence
Il est possible d'implémenter les graphes sous forme d'un dictionnaire d'adjacence , dictionnaire dont les clés sont les étiquettes des nœuds et les valeurs les listes des étiquettes des voisins (des successeurs ou des prédécesseurs si le graphe est orienté) du nœud.
{
"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
Parcours d'un arbre
Parcourir un graphe à partir d'un sommet (nœud), consiste à visiter tous les sommets possibles à partir de ce sommet.
On distingue :
- - le parcours en profondeur ;
- - le parcours en largeur.