General Discussions

Prim’s and Kruskal’s Algorithm

Prim

Kruskal

Grows with minimum cost vertex Grows with minimum cost edge
If we stop in the middle, Prim always generates connected trees If we stop the algorithm in the middle, Kruskal can give a disconnected tree or forest
Need not give attention on cycle check Need to give attention on cycle check
Graph must be connected Can function on disconnected graphs too
Spans from one vertex to another Edge selected is not based on previous step
Joins new vertex to old vertex Allows new to new and old to old to get connected.
With an efficient union find algorithm, running time will be dominated by the time needed to sorting edges. Time efficiency is O (|E log|E|) Weight matrix and priority queue as unordered array implementation is  Ѳ (|V2|) and adjacency list and priority queue as min heap running time is O(|E| log|V|)
Advertisements

Let me Know What you Think!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s