views:

1496

answers:

1

Prims algorithm is a priority first search algorithm. If this is the case, why does Sedgewick refer to the MST algorithm for a sparse graph as the priority first search algorithm but the MST algorithm for a dense graph is called Prim's algorithm?

The complexity differences between the two only arise because (a) the properties of sparse vs. dense graphs, (b) the data structure used to implement the priority queue in each algorithm (min heap vs. array) and (c) the representation of the graph itself (adjacency list vs. adjacency matrix).

+1  A: 

Please rephrase for clarity and add details about which algorithms you're talking about. (e.g. MST is a problem not an algorithm).

Corporal Touchy