Culture algorithmique

Comment structurer les données avec un graphe ?

Il existe beaucoup de structures de données complexes en informatique : la liste, les listes doublement chaînées, les piles et files qui servent notamment à stocker des tâches à effectuer, les tables de hachage pour représenter des ensembles, des arbres et des tas qui sont des structures plus compliquées, avec beaucoup de structures sous-jacentes, les graphes et les bases de données. 

Qu'est-ce qu'un graphe ? 

Un graphe est constitué de nœuds et d'arêtes (des flèches qui vont d'un nœud vers un autre nœud). Un graphe peut représenter beaucoup de choses : des réseaux (internet, électrique, d'eau...), des dépendances (pour faire C, on a besoin de faire B), des relations (A et B se connaissent)... Il y a différents types de graphes. Il peut y avoir des graphes sans flèches, ce sont des graphes non orientés. Pour les représenter par des structures de données, il y a plusieurs possibilités :

• le graphe d'adjacence, qui consiste à utiliser un booléen pour indiquer si deux nœuds sont en relation.
• la liste de voisins. Par exemple, le graphe A a deux voisins qui sont B et C. Le graphe C n'a pas de voisin.

On peut utiliser un graphe de dépendances pour représenter ce MOOC : cela permet d'identifier les séquences nécessaires pour suivre une séquence donnée. Pour ce faire, on peut utiliser un algorithme.