Français
Menu

Structures de données et algorithmes

Quelle est une façon appropriée de stocker en mémoire un graphe creux, c'est-à-dire un graphe ayant peu d'arêtes par rapport à son nombre de sommets, comme un réseau routier d'environ 1 million de sommets et 3 millions d'arêtes ?

  1. AUne matrice d'adjacence : elle vérifie en O(1) si deux sommets sont reliés et occupe aussi le moins de mémoire
  2. BDes listes d'adjacence : la mémoire est proportionnelle au nombre de sommets plus le nombre d'arêtes, et elles conviennent pour suivre une à une les arêtes qui partent d'un sommet
  3. CUne matrice d'adjacence : sa mémoire n'est proportionnelle qu'au nombre d'arêtes
Afficher la réponse et l'explication

Réponse : B. Des listes d'adjacence : la mémoire est proportionnelle au nombre de sommets plus le nombre d'arêtes, et elles conviennent pour suivre une à une les arêtes qui partent d'un sommet

Une matrice d'adjacence utilise une table V × V pour V sommets : 1 million de sommets demandent donc 10¹² cases, soit environ 125 GB même à 1 bit par case. Les listes d'adjacence ne stockent que les voisins de chaque sommet : la mémoire est en O(V + E), seulement quelques millions d'entrées dans cet exemple. La matrice d'adjacence a l'avantage de tester l'existence d'une arête en O(1) et convient aux graphes denses ou aux graphes ayant peu de sommets. Pour les traitements qui suivent tour à tour les arêtes partant de chaque sommet, comme le parcours en largeur et l'algorithme de Dijkstra, les listes d'adjacence sont plus efficaces.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. Dans un graphe dont les arêtes n'ont pas de poids, on veut trouver le plus petit nombre d'arêtes entre un sommet de départ et chacun des autres sommets. Quelle association entre méthode de recherche et structure de données convient ?
  2. Dans un graphe non orienté, les voisins de chaque sommet sont A : B, C / B : A, D, E / C : A, F / D : B / E : B, F / F : C, E. Un parcours en profondeur par récursion part du sommet A. Les voisins sont examinés dans l'ordre indiqué, et dès qu'un sommet non visité est trouvé, le parcours s'y déplace. Dans quel ordre les sommets sont-ils visités ?
  3. Dans un graphe non orienté, les poids des arêtes (distances) sont S−A : 4, S−B : 1, A−B : 2, A−C : 1, B−C : 5, C−T : 3 et A−T : 6. Quelle réponse donne le plus court chemin de S à T trouvé par l'algorithme de Dijkstra et sa longueur ?
  4. Quelle condition sur le graphe est nécessaire pour que l'algorithme de Dijkstra trouve des plus courts chemins corrects ?
  5. Les tâches A à E ont les contraintes d'ordre « A avant C », « B avant C », « C avant D », « B avant E » et « E avant D ». Quel ordre satisfait toutes les contraintes (résultat d'un tri topologique) ?