icu.next-video

Contenu proposé par

France Télévisions
Publicité
reprendre la vidéo

Regarde cette vidéo et gagne facilement jusqu'à 15 Lumniz en te connectant !

Il n’y a pas de Lumniz à gagner car tu as déjà vu ce contenu. Ne t’inquiète pas, il y a plein d’autres vidéos, jeux, quiz ou articles intéressants à explorer et toujours plus de Lumniz à remporter.

->   En savoir plus
SNT05:52Publié le 25/06/2019

Culture algorithmique

L’informatique et ses fondements

Comment structurer les données avec un graphe ?

Il existe beaucoup de  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

Auteur : Liliane Kahmsay / Florent Masseglia

Producteur : Inria

Année de diffusion : 2016

Publié le 25/06/19

Modifié le 19/10/22