Graph.
Besoin
Structure de données pour modéliser un ensemble de chemins possibles.
Cette structure est généralement utilisée pour résoudre des problèmes de cheminement (pathfinding) comme le PCC.
Analyse
Un graphe est composé de :
- Sommets (vertices) ou nœuds (nodes) de degré
n s'il en part
- n arêtes (edges) orientées (ayant un sens unique) ou non
Il peut être qualifié de :
- Connexe (connected) : tous ses sommets sont reliés au moins indirectement
(atteignables par un chemin). S'il ne l'est pas il est alors constitué de composantes connexes
non reliées entre elles.
- (a)cyclique (with(out) cycles) : ayant des boucles ou non.
- Orienté (directed graph ou digraph) si toutes ses arêtes sont
orientées.
- Complet si tous ses sommets sont reliés les uns avec les autres
Conception
Représentation
Un graphe peut être représenté sous forme de :
- Objets (nœuds) et pointeurs (arêtes)
- Matrice 2D : coût d'un sommet à un autre (0 pour d'un sommet à lui-même, infini
pour des sommets non reliés ou, dans le cas d'un graphe orienté, reliés dans sens interdit)
- Liste d'adjacences (adjency list)
Parcours
Il existe différentes méthodes pour parcourir un graphe, selon les besoins :
Exemples
- Un arbre est un graphe connexe et acyclique dont les sommets sont de degré
- 1 pour les nœuds feuilles (1 seule arête vers le père)
- n pour les autres nœuds internes (2 pour les arbres binaires par
exemple)