Algorithme de Prim pour les arbres couvrant minimum - confusion dans l'algorithme

Question

J'ai étudié à partir du livre de Cormen et al et je suis un peu confus concernant l'algorithme qu'ils ont fourni. J'ai compris comment le concept de l'algo de Prim fonctionne à travers wikipedia, mais je ne peux pas imiter cela en utilisant l'algorithme fourni dans mon livre.

rapporte à ladite copie en ligne du chapitre: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf

La algo est donnée à la page 13 dans le lien ci-dessus et un diagramme d'exemple sur la page précédente.

Maintenant, en utilisant l'algorithme sur le boîtier par exemple, dans la première étape:

u < --- noeud A à travers ExtractMin (Q). Puis il y a deux entrées dans Adj [u] selon le diagramme: noeud b et noeud h.

Maintenant, le premier jeu v < ---- noeud b. Ensuite, vérifiez si v appartient à Q. C'est le cas. Vérifiez si w (u, v) touche < [v]. Vrai. Donc PI [v] < --- u et touche [v] < --- w (u, v). J'ai reçu ça. Ceci est montré dans (b) du diagramme à la page 12.

MAIS l'algo dit "pour chaque v dans Adj [u]". L'étape suivante doit donc définir v < --- noeud h. Ensuite, vérifiez si v appartient à Q. C'est le cas! Et w (u, v) < clé [v]? C'est! Depuis la clé [v] = l'infini! Mais le diagramme montre une étape différente dans la partie (c)!

Aaaaaah! Pourquoi?

Answer 1

Votre description est correcte, l'algorithme définit la clé [h] = 8 comme vous le décrivez à l'étape a.

L'étape c est associée à une clé, vous pouvez sélectionner h si vous le souhaitez, mais l'exemple sélectionne c à la place.

La meilleure façon de le voir est de voir quels sont les éléments (non-infini) sont dans la file d'attente prioritaire à chaque étape (juste avant le ExtractMin):

1: Q = (a, 0)   - removes a, sets key[b]=4, key[h]=8 
2: Q = (b, 4), (h, 8) - removes b, sets key[c]=8 
3: Q = (h, 8), (c, 8) - could pick either h or c, they have the same key 

Answer 2

Un des gars de MO était un peu assez pour répondre par email. Le problème est que je n'ai pas remarqué que les nœuds d'arbre sont ajoutés un à la fois via l'opération ExtractMin (Q).

Voici la réponse qu'il a donné:

* Votre analyse est en fait tout à fait correct, mais vous (et moi) étaient confus au sujet de ce qui touche la mise à jour [v] et pi (v) des moyens. Dans en particulier, lorsque vous mettez à jour pi (v), vous ne l'ajoutez pas à l'arbre. Un nœud est ajouté à l'arbre (le long du bord le reliant à son parent pi (u)) seulement quand il est extrait de Q. Donc tout se passe comme vous l'avez décrit, mais à la fin, vous avez seulement achevé l'étape (a), pas l'étape (c). Voici une course vers le bas de ce que le programme fait dans ce cas :

• (lignes 1-3) Tous les nœuds sont placés dans Q (l'ensemble des noeuds non dans l'arbre ), leurs parents sont déclarés être nul, et leur clé (c.-à-d. distance minimale de l'arbre existant le long d'un seul bord) est réglé sur infini
• (ligne 4) La clé du noeud racine (noeud A) est réglé sur 0
• (ligne 6) Le nœud u avec un minimum clé (qui est le nœud racine a) retiré de Q et ajouté à l'arbre
• (lignes 8-11) Les clés des nœuds b et h sont mises à jour à 4 et 8, et pi (b) et pi (h) sont mis à u (mais b et h sont et non extraits de Q). Ceci termine l'étape (a)
• (ligne 6) Le nœud u avec clé minimale (qui est maintenant le noeud B, avec key = 4) est retiré de Q et ajouté à l'arbre par l'intermédiaire de son parent (qui est pi (b) = a)
• (lignes 8-11) La clé des nœuds c est mise à jour à 8, et pi (c) est mis à b. Puisque la clé (h) = 8 est plus petite que 11 = w (b, h), la clé et le parent de h ne sont pas mis à jour. Ceci termine l'étape (b)
• (ligne 6) Le nœud u avec la clé minimale (nœud c, avec la clé = 8, mais pourrait également avoir été le nœud h, qui a également la clé = 8) est retiré de Q et ajouté à l'arbre via son parent (qui est pi (c) = b)
• (lignes 8-11) Mettre à jour les clés et les parents des nœuds d, i et f, en complétant l'étape (c)
• etc. *