Culture algorithmique

Class'Code - L’informatique et ses fondements

Chargement de la playlist en cours...

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

Producteur : Inria

Auteur : Liliane Kahmsay / Florent Masseglia

Diffusion : 2016

en partenariat avec
Class'Code

Class’Code est un programme de formation gratuit à destination de toutes celles et ceux qui désire initier les jeunes de 8 à 14 ans à la pensée informatique. Retrouvez toutes les informations sur classcode.fr et les Moocs sur openclassrooms.fr

Publié le - Mis à jour le 25-06-2019

Recommandations