5

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:

  1. Je comprends l'algorithme de Prim très bien.
  2. Je sais comment l'implémenter efficacement en utilisant des tas et des files d'attente prioritaires.
  3. Je connais aussi de meilleurs algorithmes.
  4. 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

+2

Voici l'implémentation V^2 vers la fin de la page http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm – Ankush

Répondre

0

Vous le faites comme dans Dijkstra's algorithm, en sélectionnant le nœud qui est connecté à votre arbre partiel courant avec le bord de coût minimum (qui ne génère pas un cycle) . Je pense que wikipedia explique Prim mieux que ce pseudo-code que vous avez. Jetez un coup d'oeil et laissez-moi savoir si vous avez d'autres questions.

+1

Le problème n'est pas de comprendre l'algorithme. Je le comprends très bien. Le problème n'est pas une implémentation efficace. Il y a beaucoup de files d'attente prioritaires. Le problème est de savoir comment l'implémenter avec exactement la complexité O (| V |^2). –

5

Trouver le bord inférieur de coût (u, v), de telle sorte que u est en U et v se trouve dans V-U, est fait avec une file d'attente de priorité . Plus précisément, la file d'attente prioritaire contient chaque noeud v de V-U avec le bord de coût le plus bas de v dans l'arbre courant U. En d'autres termes, la file contient exactement | V-U | éléments.

Après avoir ajouté un nouveau nœud u à U, vous devez mettre à jour la file d'attente prioritaire en vérifiant si les noeuds voisins de u peut maintenant être atteint par un bord de coût moindre que précédemment.

Le choix de la file d'attente prioritaire détermine la complexité temporelle. Vous obtiendrez O (| V |^2) en implémentant la file d'attente prioritaire comme un simple tableau cheapest_edges[1..|V|]. En effet, trouver le minimum dans cette file d'attente prend l'heure O (| V |), et vous répétez que | V | fois.

En pseudo-code:

V = {2...,n} 
U = {1} 
T = NULL 
P = array, for each v set P[v] = (1,v) 

while V != U 

    (u,v) = P[v] with v such that length P[v] is minimal 

    T = T + {(u,v)} 
    U = U + {v} 

    for each w adjacent to v 
     if length (v,w) < length P[w] then 
      P[w] = (v,w) 
+0

Pouvez-vous écrire un petit pseudocode? –

+0

Bien sûr. Edited ma réponse. –

0

Vous pouvez trier les bords par le coût et itérer ensuite les bords de l'ordre du coût, et si ce bord se joint à deux sous-graphes distincts utiliser ce bord.

J'ai une implémentation here. Il lit le nombre de verticles (N), le nombre d'arêtes (M) et les arêtes dans l'ordre (A, B, Coût) et sort ensuite les arêtes. C'est l'algorithme de Kruskal.

Une implémentation de l'algorithme de Prim avec un tas, utilisant la même entrée peut être trouvée here.