Complexité temporelle de L'algorithme MST de Prim est O(|V|^2)
si vous utilisez une représentation de matrice d'adjacence. J'essaye de mettre en application l'algorithme de Prim en utilisant la matrice d'adjacence. J'utilise this comme référence.Algorithme MST de Prim dans O (| V |^2)
V = {1,2...,n}
U = {1}
T = NULL
while V != U:
/*
Now this implementation means that
I find lowest cost edge in O(n).
How do I do that using adjacency list?
*/
let (u, v) be the lowest cost edge
such that u is in U and v is in V - U;
T = T + {(u,v)}
U = U + {v}
EDIT:
- Je comprends l'algorithme de Prim très bien.
- Je sais comment l'implémenter efficacement en utilisant des tas et des files d'attente prioritaires.
- Je connais aussi de meilleurs algorithmes.
- Je veux utiliser la représentation de la matrice d'adjacence du graphe et obtenir l'implémentation de O (| V |^2).
JE VEUX LA MISE EN ŒUVRE INEFFICACES
Voici l'implémentation V^2 vers la fin de la page http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm – Ankush