Français
Menu

Structures de données et algorithmes

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 ?

  1. ALe parcours en largeur avec une file d'attente
  2. BLe parcours en profondeur avec une pile
  3. CLe parcours en largeur avec une pile
Afficher la réponse et l'explication

Réponse : A. Le parcours en largeur avec une file d'attente

Le parcours en largeur visite les sommets par ordre de distance : d'abord ceux qui sont à une arête du départ, puis ceux qui sont à deux arêtes, et ainsi de suite. Ajouter chaque sommet nouvellement découvert à l'arrière d'une file d'attente et prendre les sommets par l'avant préserve cet ordre « du plus proche au plus lointain » ; le nombre d'arêtes au moment où un sommet est atteint pour la première fois est donc le plus court. Le parcours en profondeur (par récursion ou avec une pile) avance le plus loin possible le long d'un chemin : il peut atteindre un sommet d'abord par un détour, et les distances les plus courtes ne sont pas garanties. Remplacer la file par une pile transforme le parcours en quelque chose de proche d'un parcours en profondeur.

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

Autres questions sur Structures de données et algorithmes

  1. 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 ?
  2. 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 ?
  3. Quelle condition sur le graphe est nécessaire pour que l'algorithme de Dijkstra trouve des plus courts chemins corrects ?
  4. 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) ?
  5. Une fonction f(x, y) est définie par « si y vaut 0, renvoyer x ; sinon, renvoyer f(y, x mod y) ». Quand on appelle f(84, 36), quelle est la valeur renvoyée, et combien de fois f est-elle appelée, premier appel compris ?