Warum verfolgt der Algorithmus von Prim den Elternknoten eines Knotens?

  • Es gibt eine offensichtliche Ähnlichkeit in der Arbeitsweise zwischen dem Algorithmus von Prim und dem Algorithmus von Dijkstra. Ich sehe jedoch keinen Grund dafür, dass der Algorithmus von Prim den übergeordneten Knoten eines Knotens verfolgt. Im Dijkstra-Algorithmus muss das übergeordnete Element des Knotens verfolgt werden, um der Kette bis zum ursprünglichen Knoten zu folgen, um die Entfernung von der Quelle zu bestimmen. Da der Algorithmus von Prim jedoch nur die Kenntnis der Entfernung vom minimalen Spannbaum erfordert, ist dies nicht der Fall Für einen bestimmten Knoten gibt es keinen Grund, das übergeordnete Element zu verfolgen.

    Siehe Pseudocode als Referenz:

     PRIM(V, E, w, r )
      Q ← { }
      for each u in V do
        key[u] ← ∞
        π[u] ← NIL
        INSERT(Q, u)
      DECREASE-KEY(Q, r, 0)    ▷ key[r ] ← 0
      while Q is not empty do 
        u ← EXTRACT-MIN(Q)
        for each v in Adj[u] do 
          if v in Q and w(u, v) < key[v] then 
            π[v] ← u
            DECREASE-KEY(Q, v,  w (u, v)) 
      
    15 August 2012
    Raphael
1 answer
  • Um den minimalen Spannbaum zu erhalten, ist es nicht erforderlich, das übergeordnete Element jedes Scheitelpunkts zu behalten. Der in Wikipedia beschriebene Algorithmus macht dies beispielsweise nicht.

    Es sollte jedoch beachtet werden, dass es mehr als eine Darstellung einer MST gibt. In bestimmten Anwendungen kann es hilfreich sein, das übergeordnete Element eines bestimmten Scheitelpunkts schnell zu finden.

    14 August 2012
    Mario