Français
Menu

Structures de données et algorithmes

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 ?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Afficher la réponse et l'explication

Réponse : C. A, B, D, E, F, C

Depuis A, le parcours passe à B, puis à D, le premier voisin non visité de B. Le seul voisin de D, B, est déjà visité : le parcours revient donc à B et passe à E, puis de E au sommet non visité F, et de F à son voisin C. L'ordre est donc A, B, D, E, F, C. A, B, C, D, E, F est l'ordre du parcours en largeur, qui visite d'abord les sommets les plus proches. A, B, D, E, C, F revient en arrière depuis E sans aller au sommet non visité F : ce n'est donc pas un ordre de 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 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 ?
  2. Quelle condition sur le graphe est nécessaire pour que l'algorithme de Dijkstra trouve des plus courts chemins corrects ?
  3. 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) ?
  4. 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 ?
  5. Une fonction fib(n) qui calcule les nombres de Fibonacci est définie par récursion : « si n vaut 1 ou moins, renvoyer n ; sinon, renvoyer fib(n−1) + fib(n−2) ». Quand on appelle fib(5), combien de fois fib est-elle appelée, premier appel compris ?