Introduction

Tout d’abord, le but de cet article est de partager des informations utiles pour le pathfinding, sous forme de tutoriel. Par conséquent avant de s’attaquer directement aux algorithmes de pathfinding tel que dijkstra ou A*, il est essentiel d’avoir quelques notions sur les graphes.

Les graphes

Premièrement, le graphe est une structure de données qui se représente par deux composants.

• Un ensemble fini de sommets également appelés nœuds ou cellules.
• Un ensemble fini de paire ordonnée ou non de la forme (u, v) appelée arêtes (liens, segments, arcs…).

De plus, un graphe peut être orienté si ses arêtes sont orientées. En effet, dans un graphe orienté, la paire (u, v) n’est pas la même chose que (v, u). Par exemple, la paire ordonnée de forme (u, v) indique qu’il y a une arête du sommet “u” vers le sommet “v”, alors que la paire (v, u) indique l’inverse.

Cependant, dans le cas d’un graphe non orienté, on utilise des paires non ordonnées. Par conséquent (u, v) indique aussi bien une arête de “u” vers “v”, qu’une arête de “v” vers “u”.

Bien que mon souhait en écrivant cet article soit de vous proposer quelque chose de simple et rapide à lire, je vous encourage à faire des recherches sur la théorie des graphes. C’est très intéressant, et utile dans beaucoup de domaines. Par exemple, vous pouvez consulter ce lien pour avoir un aperçu des algorithmes utilisant la théorie des graphes.

https://fr.wikipedia.org/wiki/Liste_des_algorithmes_de_la_théorie_des_graphes

Structure de données

Nous pouvons implémenter un graphe de plusieurs façons, je vais vous présenter les deux représentations de graphe les plus couramment utilisées.

1. Matrice d’adjacence
2. Liste d’adjacence

Matrice d’adjacence

La matrice d’adjacence est un tableau en 2 dimensions de taille V * V où V représente le nombre de sommets dans un graphe.

Prenons le cas d’un tableau 2D, soit adj[][], un attribut adj[i][j] = 1, indique qu’il y a une arête du sommet i au sommet j. En conséquence, la matrice d’adjacence pour un graphe non orienté est toujours symétrique.

Par ailleurs, la matrice d’adjacence est également utilisée pour représenter les graphes pondérés. Par exemple, si adj[i][j] = 5, alors il y a une arête du sommet i au sommet j avec un poids de 5.

Voici une représentation d’un graphe non orienté et de sa matrice d’adjacence.

	a	b	c	d
a	0	1	0	0
b	1	0	1	1
c	0	1	0	0
d	0	1	0	0

Avantages :

• La représentation est plus facile à mettre en œuvre.
• Supprimer une arête est immédiat O(1).
• Pour connaître l’existence d’une arête entre deux sommets le résultat est immédiat O(1).

Inconvénients :

• Pour trouver le voisin d’un sommet O(n). Dans le pire des cas, il faudra scanner la totalité de la colonne pour s’apercevoir qu’il n’y a pas de voisin.
• Consomme plus d’espace mémoire O(n^2). Même si le graphe contient peu d’arêtes, il consomme le même espace.
• L’ajout d’un sommet est de O(n^2).

Liste d’adjacence

Dans ce type de structure, on a un tableau de liste de sommets. La taille du tableau est égale au nombre de sommets. Par exemple, pour un tableau array[], array[5] représente la liste chaînée des sommets adjacents au 5e sommet.

Cette représentation peut également être utilisée pour représenter un graphe pondéré, les poids des arêtes peuvent être stockés dans des nœuds de listes.

Voici la représentation d’une liste d’adjacence pour un graphe orienté.

Avantages :

• Economie de l’espace mémoire. La place requise est proportionnelle au nombre d’arêtes et de sommets du graphe.
• Ajouter un sommet est plus facile.
• Trouver un voisin se fait en O(1).

Inconvénients :

• Trouver l’existence d’une arête est en O(n).

Conclusion

Finalement, pour un graphe creux (un graphe qui n’a que peu d’arêtes), une liste d’adjacence est beaucoup plus efficace en espace qu’une matrice d’adjacence. Plus précisément, l’espace mémoire requis par une liste d’adjacence est proportionnelle au nombre d’arêtes et de sommets du graphe, tandis que, pour une matrice d’adjacence stockée en tableau, l’espace est proportionnel au carré du nombre de sommets.

Dans le cas d’une recherche de chemin et de la programmation de jeux vidéo, nous aurons régulièrement affaire à des graphes creux, par ailleurs, l’opération qu’on utilisera le plus souvent sera de récupérer la liste des voisins d’une arête. En conséquence, la liste d’adjacence est la structure de donnée qu’on aura tendance à privilégiée.

source