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.
Culture algorithmique
L’informatique et ses fondements
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.
Auteur : Liliane Kahmsay / Florent Masseglia
Producteur : Inria
Année de diffusion : 2016
Publié le 25/06/19
Modifié le 19/10/22