Kruskal, Prim, Djisktra

Question 1

[Dijkstra] Initialisation : que vaut la distance de tous les sommets ?

Answer 1

∞ sauf le sommet source qui vaut 0

Question 2

[Dijkstra] Quelle structure utilise-t-on pour choisir le prochain sommet ?

Answer 2

File de priorité (min-heap)

Question 3

[Dijkstra] Que fait-on lorsqu’on visite un voisin v de u ?

Answer 3

Si dist[u] + poids(u,v) < dist[v], on met à jour dist[v]

Question 4

[Dijkstra] Complète : Dijkstra ne fonctionne pas si le graphe contient des ________

Answer 4

poids négatifs

Question 5

[Dijkstra] Complexité avec file de priorité et liste d’adjacence ?

Answer 5

Θ((n + a) log n)

Question 6

[Dijkstra] Vrai ou Faux : Dijkstra peut être utilisé sur un graphe non orienté

Answer 6

Vrai

Question 7

[Dijkstra] Quand Dijkstra donne-t-il une solution optimale ?

Answer 7

Toujours si les poids sont positifs

Question 8

Complète : La distance minimale du sommet source est mise à jour par ________

Answer 8

relaxation

Question 9

[Kruskal] Quel est le principe général de Kruskal ?

Answer 9

Trier les arêtes par poids croissant et ajouter celles qui ne forment pas de cycle

Question 10

[Kruskal] Quelle structure de données est essentielle pour éviter les cycles ?

Answer 10

Structure d’ensemble disjoint (Union-Find)

Question 11

[Kruskal] Complète : Kruskal fonctionne uniquement si le graphe est ________

Answer 11

connexe

Question 12

[Kruskal] Complexité avec Union-Find efficace ?

Answer 12

Θ(a log n)

Question 13

[Kruskal] Fonctionne-t-il sur un graphe orienté ?

Answer 13

Non, seulement sur les graphes non orientés

Question 14

[Kruskal] Que doit-on faire après avoir trié les arêtes ?

Answer 14

Parcourir les arêtes en ajoutant celles qui relient deux composants distincts

Question 15

[Prim] Quelle est la stratégie de Prim ?

Answer 15

Construire l’arbre en ajoutant à chaque fois l’arête minimale reliant un sommet visité à un sommet non visité

Question 16

[Prim] Quelle structure est utilisée pour choisir l’arête minimale suivante ?

Answer 16

File de priorité sur les sommets

Question 17

[Prim] Complète : On démarre l’algorithme de Prim à partir ________

Answer 17

d’un sommet arbitraire

Question 18

[Prim] Complexité avec file de priorité binaire ?

Answer 18

Θ((n + a) log n)

Question 19

[Prim] Fonctionne-t-il sur graphe orienté ?

Answer 19

Non, seulement sur graphe non orienté pondéré

Question 20

[Prim] Quand ne pas utiliser Prim ?

Answer 20

Sur un graphe non connexe, car on ne peut pas atteindre tous les sommets

Question 21

Complète : Dijkstra suppose que tous les poids sont ________

Answer 21

positifs

Question 22

Complète : Kruskal trie les ________ pour construire l’ACM

Answer 22

arêtes

Question 23

Complète : Prim sélectionne toujours l’arête ________ connectant un sommet visité à un non visité

Answer 23

de poids minimal

Question 24

Vrai ou Faux : Kruskal et Prim produisent le même arbre si les poids sont uniques

Answer 24

Vrai

Question 25

Quel algorithme parmi Dijkstra, Kruskal et Prim fonctionne aussi sur des graphes partiellement connectés ?

Answer 25

Kruskal (il construit une forêt)

Question 26

Quand est-il mieux d’utiliser Dijkstra que Kruskal ?

Answer 26

Quand on cherche un chemin de coût minimal depuis un sommet source vers tous les autres

Question 27

Quand est-il mieux d’utiliser Kruskal que Dijkstra ?

Answer 27

Quand on veut construire un arbre couvrant de poids minimal (ACM)

Question 28

Quand est-il mieux d’utiliser Prim plutôt que Kruskal ?

Answer 28

Quand le graphe est dense et représenté avec une matrice d’adjacence

Question 29

Quand est-il mieux d’utiliser Kruskal que Prim ?

Answer 29

Quand le graphe est clairsemé et représenté avec une liste d’adjacence

Question 30

Quel algorithme est préférable pour un graphe non connexe ?

Answer 30

Kruskal (il construit une forêt de minimums)

Question 31

Quel algorithme est plus simple à implémenter sans file de priorité ?

Answer 31

Kruskal

Question 32

Quel algorithme est sensible aux poids négatifs ?

Answer 32

Dijkstra

Question 33

Si tu dois connaître la structure exacte du chemin minimum, que dois-tu conserver dans Dijkstra ?

Answer 33

Les pointeurs vers les prédécesseurs (predecesseurs)

Question 34

Vrai ou faux : Prim est plus rapide que Kruskal sur les graphes très denses ?

Answer 34

Vrai

Question 35

Complète : Si tu veux un ACM et que tu as une structure Union-Find prête, utilise ________

Answer 35

Kruskal