Graphique du pire cas pour l'algorithme de Prim

Question

Ma classe d'algorithmes parle de l'algorithme de Prim en tant que méthode de recherche des arbres de portée minimale des graphes pondérés. Notre professeur nous a demandé d'essayer de penser à un exemple de graphique que l'algorithme de Prim prend N^2 fois pour résoudre (N = nombre de sommets). Personne dans la classe ne pouvait en imaginer une de leur tête, alors je vous le demande. Je suis assez sûr que l'algorithme de Prim = O (N^2), donc ce serait le pire des cas pour l'algorithme.

Quel est un bon exemple d'un graphique qui prend N^2 fois pour résoudre l'algorithme de Prim?

Answer 1

Si je comprends bien votre question, l'exemple est trivial.

Si le graphique est complet, il y a O(N^2) bords, il suffit donc de lire le graphique O(N^2).