Pourquoi avons-nous besoin d'une file d'attente prioritaire dans l'Algorithme de Prim

Que ma question parle, je veux savoir pourquoi avons-nous utiliser la file d'attente de Priorité dans L'Algorithme de Prim?
Comment il nous sauve de l'aide de l'naïf façon (oui j'en ai entendu parler mais je ne sais pas pourquoi).

Je serais très heureux si quelqu'un pouvait expliquer étape par étape pour la liste d'adjacence . Je suis à l'aide de Cormen du livre.

Le pseudo-code :

Prim(G,w,r) //what is w (weight?) and r?
  For each u in V[G]
    do key[u] ← ∞ //what is key?
       π[u] ← NIL  
  key[r] ← 0
  Q ← V[G]  
  While Q ≠ Ø
    do u ← EXTRACT-MIN(Q)
       for each v in Adj[u]
            if v is in Q and w(u,v) < key[v]
                 then π[v] ← u
                       key[v] ← w(u,v)

Je pense utiliser std::vector puis std::make_heap(); file d'attente de priorité pour le stockage des bords.

n'est-il pas expliqué dans le livre?
Que voulez-vous utiliser à la place d'une file d'attente de priorité? Qu'est ce qui influence cela aurait-il sur l'efficacité et l'exactitude?
où, dans ce pseudo-voulez-vous ajouter à la mstree?

OriginalL'auteur Mr.Anubis | 2011-08-12

  1. 10

    Dans l'algorithme de prim, il y a une étape où vous devez obtenir le "plus proche" de vertex. Cette étape serait de coût O(N) si vous utilisez un tableau normal, mais il faudra seulement O(logN) si vous utilisez la file d'attente de priorité (tas par exemple)

    Par conséquent, la raison pour l'utilisation de la file d'attente de priorité est de réduire l'algorithme de complexité temporelle (ce qui signifie qu'il faire à votre programme courir plus vite)

    **

    Mise à jour:

    **

    Voici l'algorithme de Prim description de Wikipédia. La partie en gras est la partie pour trouver le plus proche de vertex, j'ai parlé de:

    D'entrée: Un non-vide connecté pondérée graphe dont les sommets V et d'arêtes E (le poids peut être négatif).

    Initialiser: Vnew = {x}, où x est l'arbitraire d'un nœud (point de départ) à partir de V, Enew = {}

    Répétez jusqu'à ce que Vnew = V:
    Choisir une arête (u, v) avec un poids minimal tel que u est dans Vnew et v n'est pas (s'il y a plusieurs bords avec le même poids, l'un d'eux peut être choisi)
    Ajouter v à Vnew, et (u, v) pour Enew

    De sortie: Vnew et Enew décrire un minimum spanning tree

    there is a step where you have to get the 'nearest' vertex . Pouvez-vous dire ce que vous entendez par le plus proche du vertex , parlez-vous le plus proche sommet adjacent ? depuis quand on prend de la coupe du graphe nous parlons de tout sommet adjacent es pour tout V dans Un lieu sûr (coffre de pointe) . Dites-moi que je suis de droite?
    Je viens d'ajouter quelques précisions à partir de wikipedia, espérons que cela aide 🙂

    OriginalL'auteur Chan Le

  2. 6

    Vous n'avez pas "besoin" de lui. En fait, une implémentation naïve de l'algorithme de Prim aurait suffit de faire une recherche linéaire de la matrice de distances pour trouver le plus proche de vertex. L'algorithme de Dijkstra fonctionne exactement de la même manière.

    La raison pourquoi les gens utilisation c'est parce qu'il accélère significativement le temps d'exécution de l'algorithme. Il se détourne de O(V^2 + E) à O(E*log(V)).

    La clé, c'est la EXTRACT-MIN(Q) fonction. Si vous le faites, naïvement, cette opération prendrait O(V) temps. Avec un tas, il ne faut O(logV) temps.

    attendre.. extraire-min(Q) <- n'est-ce pas de temps constant, car il est juste en tirant le premier élément de la file d'attente de priorité?
    Non, car il faut O(log V) de temps pour restaurer la structure de tas.

    OriginalL'auteur tskuzzy

  3. 3

    Ce faisant à peu près à partir de la mémoire, de sorte qu'il peut être un peu incohérent, mais il obtient le point à travers: 

    class Graph
  Set<node> nodes;   //The set of nodes in the graph
  MultiMap<Node, Edge> edges; //Map from Node, to a list of weighted edges connected to the node. If it weren't weighted, any spanning tree by definition would be a minimum spanning tree.

Graph Prim(Graph input):
   Graph MST = new Graph();
   PriorityQueue<Edge> candidateEdges;
   Node anyNode = input.pickAnyNodeAtRandom()
   candidateEdges.putAll(input.edges.get(anyNode));

   while MST.nodes.size() < input.nodes.size():
      edge = candidateEdges.takeLowest()  //THIS IS THE IMPORTANT PART         
      if edge.v1 in MST.nodes and edge.v2 not in MST.nodes:
         MST.nodes.add(edge.v2)       
         MST.edges.add(edge)
         candidateEdges.add(edge.v2.edges)

    En gros, à chaque étape de l'algorithme, vous êtes à la recherche pour le minimum de bord avec un sommet dans le partiel minimum spanning tree, et un sommet est pas dans l'arbre, et vous allez à ajouter, a déclaré le bord de l'arbre. Comment voulez-vous le faire efficacement? Si vous avez un moyen efficace de commander tous les bords connecté à un sommet dans votre partielle spanning tree, vous pouvez simplement parcourir jusqu'à ce que vous trouver un bord avec un niveau acceptable de vertex.

    Sans une telle commandé structure de données, vous auriez à itérer sur tous les bords à chaque fois pour trouver le minimum, plutôt que d'être en mesure de saisir efficacement le minimum directement.

    Très terriblement expliqué 🙂 Il a été parmi l'une des meilleures explications que j'ai trouvé sur. merci s'accoupler 😀

    OriginalL'auteur James

  4. 1

    Prim de l'algorithme utilise deux Ensembles - permet de dire que U et V/U.

    Vous êtes à partir de la racine (root est le seul élément en U).
    Vous mettez tous les sommets adjacents dans la file d'attente, avec poids[v] = dist[racine,v] où v est adjacent à la racine.
    De sorte que lorsque vous éclater à partir de la file d'attente, vous prenez le vertex (disons u) a une extrémité en U et à la fin en V/M et est le plus petit avec cette propriété.
    Vous définissez son poids, sa mère d'être root et etc... et de mettre tous ses ajdacent nœuds dans la file d'attente. Alors maintenant, la file d'attente a tous les nœuds ajdacent à la racine et tous les nœuds de la ajdacent à la racine et tous les nœuds ajdacent de u avec leurs poids respectifs. Donc quand vous sautez, vous aurez une fois de plus obtenir un nœud de V/U, qui est "le plus proche" pour U.

    Dans la mise en œuvre, ils sont d'abord l'ajout de chaque sommet de la file d'attente avec l'INFINI priorité, mais ils sont à jour progressivement le poids, comme vous pouvez le voir. Cela se reflète dans la file d'attente de priorité ainsi, guaranteeng le texte ci-dessus.

    Espère que cela aide.

    OriginalL'auteur George