Prims

High Level Algorithm

1. Start with an arbitrary vertex. Mark it as known.

2. Note all the vertices that extend from starting vertex. Select the next adjacent vertex that has the lowest cost relative (not cumulative); and will not create a cycle upon connection. Mark this vertex as known.

3. Note the next possible connections of all the known vertex and select the next lowest vertex, such that it does not create a cycle.

4. See 3. Stop once all nodes have at least one edge connected to it.

Data Structures

• Minimum Binary Heap, or priority_queue. This will allow us to both efficiently insert elements into the graph when we discover a new node, as well as retrieve the next minimum Graph node to incorporate into the MST.

Differences with Kruskal's

• Does not pick globally minimum vertex. Rather it only looks at the edges that were already introduced by the already visited vertices.

• Doesn't begin with a distinguished vertex per say, because prims may generate different minimum spanning trees depending on what vertex it starts.

Time Complexity

• $O(nlogn)$ or more precisely $O(VELog(V))$

• Priority Queue insertions will operate O(V) times, since we pop from the queue at most once for all the vertices of the graph.

• Per each pop, we scan through the adjacenct elements of a particular vertecy possible update an edge weight. This is will be proportional to the number of edges E.