Understanding when to use Prim or Kruskal for Minimum Spanning Tree

Question

I'm trying to apply Prim's or Kruskal's algorithms to certain situations. I understand that Prim is used when graphs are dense (Example: as adjacency matrix with priority queue as unordered array would be good for a dense tree where E = O(V^2). And Kruskal is used when graphs are sparse (Example: as adjacency list with fast sort where E = O(V). What I'm unsure about is the in between. For example, a graph with a moderate number of edges such that

E = O(V log V)

Would this be Prim or Kruskal? I think it may be either one because Prim O(E log V) and Kruskal O(E log E) have similar time complexities.

Answer 1

Due to the nature of each algorithm, in the case of a graph with moderate number of edges, you should use Kruskal's algorithm. Prim's algorithm runs faster in a graph with many edges as it only compares limited number of edges per loop, where as Kruskal's start by sorting all the edges in the list then going through them again to make check if the edge is part of the minimal spanning tree (MST) or not. So in the case of your question, while both algorithms have similar running time, number of edges in the graph should be the main component when you are deciding between the algorithms. More edges compared to vertices, use Prim's, otherwise, use Kruskal's.

Answer 2

Prim's algorithm is faster when you've got a really dense graph with many more edges than vertices. Kruskal performs better in sparse graphs.Because prim's algorithm always joins a new vertex to an already visited(old) vertex, so that every stage is a tree. Kruskal's allows both "new" to "new" and "old" to "old" to get connected, so this can lead to creating a circuit and algorithm must check for them every time. So Kruskal's has a larger complexity than Prim.So it is depends to edge number vertices ratio.