Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's Algorithm, Kruskal's Algorithm - Coggle Diagram
Prim's Algorithm
Given n points, the goal is to connect them in the cheapest way to ensure there is a path between every pair of points.
We can represent the points given by vertices of a graph, possible connections
by the graph’s edges, and the connection costs by the edge weights.
MST Problem: A spanning tree of an undirected connected graph is its connected
acyclic subgraph that contains all the vertices of the graph. If such graph has weights tyo its edges, a Minimum Spanning Tree is its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all it edges.The minimum spanning tree problem is the problem of
finding a minimum spanning tree for a given weighted connected graph.
Points are represented as vertices, possible connections as edges, and connection costs as edge weights in a graph.
The algorithm begins with a single vertex selected arbitrarily from the set of vertices in the graph.
Greedy Expansion: In each iteration, the algorithm expands the current tree by adding the nearest vertex not yet in the tree.
-
Each vertex not in the current tree needs information about the shortest edge connecting it to the tree. This is done using two labels: the nearest tree vertex and the edge weight.
Vertices not adjacent to any tree vertices are given an infinite distance label and a null label for the nearest tree vertex.
-
Finding the Next Vertex: Select the vertex with the smallest distance label from the set of vertices not in the tree (V - VT). Ties can be broken arbitrarily.
-
The efficiency of Prim's algorithm depends on the graph representation and priority queue implementation:
-
-
Kruskal's Algorithm
-
Kruskal's algorithm is a greedy algorithm for constructing a minimum spanning tree (MST), similar to Prim's algorithm, but with a different approach.
-
Ensures the subgraph remains acyclic, even if it is not connected at intermediate stages.
It works by sorting all edges of the graph in non-decreasing order of their weights, and then starts with an empty subgrapgh. it Iterates through the sorted edge list, adding the next edge to the subgraph if it does not create a cycle and skip any edge that would form a cycle in the subgraph.
Like Prim's algorithm, Kruskal's algorithm guarantees an optimal solution, producing a minimum spanning tree for the given weighted connected graph.
Manually applying Kruskal’s algorithm might seem simpler than Prim's, but it requires cycle checks at each step.
A cycle is formed if the new edge connects two vertices already linked by a path, meaning the vertices are in the same connected component.
-
-
-
Union-Find Operations: Efficient algorithms exist to manage trees and check if two vertices are in the same tree, known as union-find algorithms.
With efficient union-find and sorting algorithms, the running time of Kruskal's algorithm is dominated by edge sorting, resulting in O( E log E) time complexity.
-