Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's algorithm, Kruskal's algorithms - Coggle Diagram
Prim's algorithm
Time efficiency
Weight matrix and the priority queue is implemented as an unordered array
Θ(|V²|)
Represented by its adjacency lists and the priority queue is implemented as a min-heap
O(|E| log |V |)
Insertion/deletion -> O(log n)
Kruskal's algorithms
time efficiency
sorting algorithms -> O(|E| log |E|)
union-find
find(x)
union(x, y)
makeset(x)
implements
quick find -> optimizes the time efficiency of the find operation
makeset/find -> Θ(1)
quick union -> optimizes the union operation
makeset/union -> Θ(1)
find -> O(n)