You are to implement Prim\'s algorithm. Which data structures and algorithms you

Question

You are to implement Prim's algorithm. Which data structures and algorithms you would use and why those rather than some alternative. Be sure to specify the contents of any required record types.

Prim's Minimum Cost Spanning Tree Algorithm:

The only spanning tree of the empty graph (with an empty vertex set) is again the empty graph. The following description assumes that this special case is handled separately.

The algorithm continuously increases the size of a tree, one edge at a time, starting with a tree consisting of a single vertex, until it spans all vertices.

(a) Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).

(b) Initialize: Vnew = fxg, where x is an arbitrary node (starting point) from V,
Enew = {}
(c) Repeat until Vnew = V:
- Choose an edge (u, v) with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)

- Add v to Vnew, and (u, v) to Enew

(d) Output: Vnew and Enew describe a minimal spanning tree
5

Explanation / Answer

Dear....

Data Structures Required
1. a C++ class called Graph to encapsulate most of the data structures and methods
2. a Node structure. Use these to store graph edges in the linked lists
3. array of linked lists to store the graph in memory. Declared with Node ** adj;
4. an int array dist[ ] to record the current distance of a vertex from the MST.
5. an int array parent[ ] to store the MST
6. a heap h to find the next vertex nearest the MST so that it can be added to the MST.
7. an int array hpos[ ] which records the position of any vertex with the heap array h[ ].

So vertex v is in position hpos[v] in h[].

Pseudocode:

Prim_Sparse( Vertex s )
Begin
// G = (V, E)
for each v belongs V
dist[v] = infnite
parent[v] = 0 // treat 0 as a special null vertex
hPos[v] = 0 // indicates that v heap
h = new Heap // priority queue (heap) initially empty
h.insert(s) // s will be the root of the MST
while (not h.isEmpty() ) // should repeat |V|-1 times
v = h.remove() // add v to the MST
dist[v] = -dist[v] // marks v as now in the MST
for each u belongs adj(v) // examine each neighbour u of v
if wgt(v, u) < dist[u]
dist[u] = wgt(v, u)
parent[u] = v
if u not belongs h
h.insert( u)
else
h.siftUp( hpos[u])
end if
end for
end while
return parent
End

----------------

Time complexity for above algorithm is O(v^2)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.