Please enable JavaScript.
Coggle requires JavaScript to display documents.
M14, Prim's Algorithm, Kruskal's Algorithm, Disjoint Subsets and…
-
Prim's Algorithm
Steps
Initialize a tree with a single vertex, chosen arbitrarily from the graph.
-
-
-
-
Principle
Greedy algorithm that builds the MST by starting with a single vertex and repeatedly adding the cheapest possible connection from the tree to another vertex.
Complexity
O(V²) using an adjacency matrix, or O(E log V) with a priority queue and adjacency list.
Kruskal's Algorithm
-
Principle
Greedy algorithm that builds the MST by sorting all edges and adding them one by one to the growing spanning tree, ensuring no cycles are formed.
Steps
-
Initialize an empty forest (a set of trees), where each vertex is a separate tree.
-
If the edge connects two different trees, add it to the forest, merging the two trees into a single tree.
If the edge connects two vertices in the same tree, discard it to avoid cycles.
Repeat until there is only one tree left, which will be the MST.
Complexity
O(E log E) or O(E log V), due to sorting the edges and using the Union-Find data structure.
-