Minimum Cost Spanning Tree

Introduction of Minimum Cost Spanning Tree

• The minimum (Cost) Spanning Tree is also known as MST.

Definition of MST

• A Minimum Cost Spanning Tree is a way of connecting all the points (or nodes) in a network with the least possible total cost, without creating any closed loops or cycles.
• A Spanning tree with the sum of minimum (edge) weights or costs is called an MST (Minimum Cost Spanning Tree). 

Characteristics of MST

• A Spanning Tree (ST) is (actually derived from a graph) a tree (a connected graph without a cycle) that contains all the vertices of the graph.
• A minimum cost spanning tree makes sure that every point (or vertex) in the graph is connected so that nothing is left out.
• If there are n vertices, the spanning tree will always have exactly n – 1 edges. This is the minimum needed to connect everything without forming loops.
• A spanning tree never forms a closed loop. This prevents extra or unnecessary connections.
• Among all possible spanning trees, the minimum cost spanning tree is the one that uses the edges with the least overall weight (or cost).
• If all edge weights are unique, the minimum cost spanning tree will also be unique. If some edges have the same weights, there may be more than one possible MCST.
• It keeps the network fully connected but avoids adding extra edges that would increase cost.

Properties of MST

• A spanning tree of vertices V has V-1 edges.
• ST is an undirected, connected, and acyclic graph.
• A spanning tree is associated with a weighted, connected, Non-directed or Undirected, or Bi-directional graph.
• The weights on the links or edges are called costs.
• There may be single or multiple spanning trees.
• There exists a unique path between any two vertices of a spanning tree.
• Adding any edge to a spanning tree creates a unique cycle.
• Breaking any edge on this cycle restores a spanning tree.

Use/Application/Implementation of MST

• Designing Road Networks – When cities or towns need to be connected by roads, an MCST helps find the cheapest way to connect them all without building unnecessary roads.
• Electrical Wiring Layout – When setting up electricity distribution for homes, offices, or factories, an MCST ensures that all buildings are connected with wires using the shortest possible length, thereby reducing costs.
• Computer Networks – In LANs (Local Area Networks) or wide networks, an MCST can be used to connect all computers and servers with the minimum number of cables while keeping the system fully connected.
• Water Supply Systems – To supply water to different areas, an MCST can be used to determine the most cost-effective way to lay pipes without redundancy.
• Telecommunication Networks – Telephone lines, internet cables, or mobile towers can be connected in a network using an MCST to reduce infrastructure costs while maintaining full connectivity.
• Transportation and Railway Planning – When building rail tracks or metro lines between cities or stations, an MCST helps plan routes that cover all locations with minimal total track length.
• Cluster Analysis in Data Mining – In computer science, MCST is also used to group similar data points together efficiently in tasks like image segmentation or pattern recognition.
• In Geometric/Vision/Image Processing (Registration & Segmentation) Problems and Analysis work.
• To choose the minimum weight of a spanning tree for broadcasting the messages to its shortest nearby location.
• In Handwriting recognition of mathematical expressions.
• Used in algorithms approximating the traveling salesman problem, the multi-terminal minimum cut problem, and the minimum cost weighted perfect matching.
• In Cluster Analysis.

Algorithms for MST

• There are four famous algorithms for finding out the Minimum Cost Spanning Tree: –
  • Prim’s Algorithms
  • Kruskal’s Algorithms
  • Borůvka’s Algorithm
  • Reverse-Delete Algorithm

Prim’s Algorithm

Introduction of Prim’s Algorithm

• Prim’s Algorithm is one of the famous algorithms to find the minimum cost spanning tree from a given graph.

Definition of Prim’s Algorithm

• Prim’s Algorithm is a powerful greedy vertex-oriented method used to find a Minimum Cost Spanning Tree (MCST) in a weighted connected graph as it builds the tree step by step from a starting vertex always choosing the cheapest available edge while avoiding cycle formation and the algorithm works best for dense graphs being highly practical for real-world network problems with its efficiency depending on the choice of data structures.

Working Mechanism/Steps of Prim’s Algorithm

• Choose any arbitrary node or vertex first (and start MST formation from the given graph).
• Select the cheapest Neighbour vertex that is connected to it into the growing spanning tree. This can be done using Priority Queues.
• Now, add a selected vertex to the MST one by one from the remaining vertices having the next smallest weight until the final MST is formed.
• During each step, only those next vertices are added/selected to the MST that don’t form a cycle during the formation of the MST.
• All the vertices/Nodes must be traversed from the graph and present in the MST.
• In summary form, we start with any arbitrary node/vertex given in the graph and mark it. In each iteration, we will mark & traverse a new smallest-weight vertex that is adjacent to the one that we have already marked/traversed. Now, as a greedy algorithm, Prim’s algorithm will select the cheapest edge and mark the vertex. In the next iteration, we will select the edge with the second smallest weight and mark the vertex, and so on, one by one, considering no creation of a cycle. In the end, we finish a minimum spanning tree with a total cost by adding all the traversed vertices with their paths. (Such as AB+AD+DC+BC=3+6+7+10=26).

Advantages of Prim’s Algorithm

• Simple and Intuitive
  • Prim’s Algorithm is easy to understand because it grows the tree step by step, starting from a single vertex and always adding the cheapest edge.
• Efficient for Dense Graphs
  • If the graph has lots of edges (dense graphs), Prim’s Algorithm performs very well, especially when combined with advanced data structures like a priority queue (using a binary heap or Fibonacci heap).
• Works Well with Adjacency Matrices
  • When the graph is stored as an adjacency matrix, Prim’s Algorithm is very convenient since it can easily check the cost of connecting to new vertices.
• Good for Real-World Network Design
  • Because it builds the spanning tree gradually, Prim’s Algorithm is especially useful in real-world problems like designing road maps, electrical grids, and computer networks, where you often start from one point and keep adding connections.
• Produces a Minimum Spanning Tree (MST)
  • Like Kruskal’s Algorithm, Prim’s Algorithm guarantees that the final result will be the minimum cost spanning tree, ensuring the lowest total cost of connections.
• Less Sorting Overhead than Kruskal’s
  • Unlike Kruskal’s Algorithm, which sorts all edges at the beginning, Prim’s Algorithm doesn’t require sorting the entire edge list. This makes it efficient in graphs with a very large number of edges.
• Good for Connected Graphs
  • Prim’s Algorithm naturally works well when the graph is connected, making sure all vertices get included in the tree step by step.

Disadvantages of Prim’s Algorithm

• Prim’s Algorithm is powerful, but it becomes less efficient for sparse or very large graphs, requires extra data structures, and may be harder to implement compared to alternatives like Kruskal’s. Some common disadvantages of Prim’s algorithm are –
  • Not Always Efficient for Sparse Graphs
    • Prim’s Algorithm works best with dense graphs (lots of edges). But in sparse graphs (few edges), it may take extra time to scan through unnecessary edges, especially if implemented with an adjacency matrix.
  • Requires Complex Data Structures for Speed
    • To make Prim’s Algorithm efficient for large graphs, we often need advanced data structures like priority queues or heaps. This increases the complexity of implementation compared to simpler algorithms like Kruskal’s.
  • Harder to Implement for Very Large Graphs
    • For very big networks (like internet routing systems), maintaining the minimum edge selection can become tricky and memory-consuming.
  • Sensitive to Graph Representation
    • If the graph is represented as an adjacency matrix, Prim’s Algorithm may run slower even when there are only a few edges. This makes it less practical in cases where the number of vertices is huge but the number of edges is small.
  • Multiple Minimum Trees Possible
    • If the graph has several edges with the same weights, Prim’s Algorithm might produce different minimum spanning trees depending on the starting vertex. This isn’t always a problem, but it can make results less predictable in certain applications.

Use/Application of Prim’s Algorithm

• Designing Road Networks
  • Using Prim’s Algorithm, planners can figure out which roads should be built so that all cities are connected without wasting money on extra roads.
• Electrical Power Grid Design
  • Prim’s Algorithm helps in deciding how to connect all houses or cities with power lines while spending the least on wiring.
• Telecommunication Networks
  • By applying Prim’s Algorithm, they can connect all towers using the minimum amount of cable, saving both time and money.
• Computer Networks
  • When building a local area network (LAN), Prim’s Algorithm helps in deciding how to connect computers and servers using the least number of cables while ensuring every device is connected.
• Transportation and Railway Systems
  • Railway networks between cities can be planned using Prim’s Algorithm so that all stations are connected with the least possible track length, reducing costs.
• Water Supply Systems
  • To provide water pipelines in a new residential area, Prim’s Algorithm can be applied to connect all houses with the minimum pipeline cost.
• Clustering in Data Mining
  • In computer science, Prim’s Algorithm is used in clustering methods, where data points are grouped together based on minimum distances, similar to connecting “closest” nodes in a network.

Kruskal’s Algorithm

Introduction of Kruskal’s Algorithm

• Kruskal’s Algorithm is another one of the famous algorithms to find the minimum cost spanning tree from a given graph.

Definition of Kruskal’s Algorithm

• Kruskal’s Algorithm is an edge-oriented greedy method that builds an MST by picking the smallest edges one by one, working especially well on sparse graphs, avoiding cycle formation, and always ends up with a spanning tree of minimum total cost.
• Kruskal’s Algorithm builds the spanning tree by adding the smallest edge value/cost one by one into a growing spanning tree.
• Kruskal’s Algorithm is easy to implement, efficient for sparse graphs, works well with edge-based problems, can handle disconnected graphs (forests), and always guarantees the least total cost of connections.

Characteristics of Kruskal’s Algorithm

• Kruskal’s algorithm follows and works on the principle of the greedy algorithm approach in each iteration by finding an edge that has the least weight/cost and adding it to the growing spanning tree.
• Kruskal’s algorithm focuses on edges first, not vertices, because it sorts all the edges in increasing order of weight and then keeps adding them one by one to the tree.
• Cycle formation is not allowed in Kruskal’s algorithm.
• Kruskal’s guarantees that the final result will be a minimum spanning tree that connects all vertices with the least total cost.
• The MST formed will always contain exactly (n – 1) edges, where n is the number of vertices.
• The efficiency of Kruskal’s algorithm relies heavily on sorting all edges at the start. If there are too many edges, the sorting step can take significant time.
• If all edge weights are unique, Kruskal’s Algorithm produces a unique MST. If there are equal edge weights, multiple MSTs may exist, but all will have the same minimum total cost.
• Applicable to Both Directed and Undirected Graphs (with Modification), i.e., Kruskal’s is mainly applied to undirected weighted graphs, but with adjustments, it can also be extended to certain directed cases.

Advantages of Kruskal’s Algorithm

• Kruskal’s algorithm performs better than Prim’s when the graph has fewer edges (sparse graphs). This is because it only needs to sort the edges and then process them, rather than scanning through all vertex connections.
• Kruskal’s algorithm is very straightforward and Simple to understand.
• Kruskal’s algorithm is efficient for Sparse Graphs (the graph has fewer edges) due to it doesn’t waste time checking unnecessary connections, because it only considers sorted edges.
• Since Kruskal’s works directly with edges, it’s well-suited when the problem naturally provides data in the form of edge lists (like road costs between cities or cable connections between towers).
• Kruskal’s algorithm works on Disconnected Graphs (for Forests). This makes it useful not just for single networks but also for handling multiple smaller networks at once.
• Kruskal’s algorithm avoids cycle formation. This keeps the algorithm clean and predictable.
• Kruskal’s algorithm guarantees minimum cost, ensuring that the overall connection cost is the least possible.
• Kruskal’s algorithm has a deterministic output. It means that if all edge weights are unique, Kruskal’s algorithm always produces the same MST. Even if multiple MSTs are possible due to equal weights, the total cost will always be minimum, so the solution remains optimal.
• Kruskal’s algorithm is good for Real-Life Applications. It means that Kruskal’s algorithm is widely used in designing road networks, electrical wiring, computer networking, and telecommunication systems, where costs between connections are already given in edge lists.

Disadvantages of Kruskal’s Algorithm

• Kruskal’s algorithm has sorting overhead. It means that Kruskal’s requires sorting all edges at the beginning, and for very large graphs with thousands or millions of edges, this sorting step can become time-consuming and memory-heavy.
• Kruskal’s algorithm needs extra data structures to efficiently avoid cycle formation in Kruskal’s algorithm which relies on the Union-Find (Disjoint Set Union – DSU) data structure.
• Kruskal’s algorithm is not as efficient for dense graphs (the graph has many edges ). Kruskal’s algorithm becomes slower compared to Prim’s Algorithm, because it still has to sort and check every single edge.
• In disconnected graphs, Kruskal’s algorithm needs extra care because it produces a spanning forest instead of a single spanning tree. This may require additional logic if the goal is to fully connect all vertices.
• Kruskal’s algorithm shows multiple MST possibilities. It means that if the graph has several edges with the same weight, Kruskal’s algorithm may generate different MSTs depending on which edges are chosen first. While the total cost remains the same, this can make the output less predictable.
• Kruskal’s algorithm is slower for Adjacency Matrices. It means that if the graph is stored as an adjacency matrix instead of an edge list, Kruskal’s algorithm is not as natural to apply, since it works directly on edges. In such cases, Prim’s Algorithm is often more convenient.
• Kruskal’s algorithm is less practical for real-time problems because this algorithm sorts all edges at once. Kruskal’s is less suitable for dynamic situations where edges or weights may change frequently (like real-time traffic routing).

Working Mechanism of Kruskal’s Algorithm

• Choose the lowest edge value/costs first (and start MST formation from the given graph).
• Now, add edges to the MST one by one from the remaining edges having the next smallest weight until the final MST is formed.
• Only those next edges are added in the MST, which don’t form a cycle during the formation of the MST.
• All the Vertices/Nodes must be traversed from the graph and present in the MST. 

Practically, in Kruskal’s algorithm, at each iteration, we will select the edge with the lowest weight, i.e., we will start with the lowest weighted edge first, and after that, we will select the second lowest weighted edge, and so on till all the vertices are traversed without any cycle formation in the MST. In the end, we finish a minimum spanning tree with a total cost by adding all the traversed edges with their paths. (Such as AB+AD+DC+BC=3+6+7+10=26).

Time Complexity of Kruskal’s Algorithm

• The time complexity, in Kruskal’s algorithm, is mostly consumed during the operation of sorting of Disjoint-Set is O(E log V), which is the overall Time Complexity of the algorithm.

Use/Applications of Kruskal’s Algorithm

• Designing Road Networks
  • When a government or city planner wants to connect towns or cities with roads at the lowest total construction cost, Kruskal’s Algorithm can be used. Since road costs are usually given as edges between cities, Kruskal’s algorithm works perfectly by choosing the cheapest road connections without forming unnecessary loops.
• Laying Electrical Power Lines
  • Electricity boards often need to connect different cities or houses using the minimum length of wire. Kruskal’s helps in finding the cheapest way to connect everything while making sure the network is fully connected.
• Telecommunication and Internet Networks
  • Telephone companies, cable networks, or internet service providers use Kruskal’s Algorithm to minimize the cost of laying out fiber cables or phone lines. It ensures every area is connected with the least amount of cabling.
• Computer Networking
  • In local area networks (LANs), Kruskal’s algorithm helps in connecting all computers and servers with the least number of cables, avoiding redundant or costly links.
• Water Supply Pipelines
  • Municipal corporations of a city use Kruskal’s idea to design the minimum-cost water distribution system, ensuring that every house or colony gets water through the shortest possible pipeline network.
• Railway Networks
  • Railway authorities can use Kruskal’s algorithm to connect stations with minimum total track length while ensuring that all stations are reachable.
• Broadcasting in Wireless Networks
  • In wireless sensor networks, Kruskal’s algorithm helps design a low-cost communication structure that connects all sensors efficiently without wasting bandwidth.
• Approximation Algorithms in NP-Hard Problems
  • Kruskal’s Algorithm is also used as part of approximation techniques in solving hard optimization problems, like the Traveling Salesman Problem (TSP).

Boruvka’s Algorithm

• In this, every vertex is trying to grab its cheapest neighboring edge at the same time.
• In each round, all vertices pick their lowest-cost edge, and slowly these small trees merge into bigger ones until only one spanning tree remains.

Reverse-Delete Algorithms

• This works in the opposite way, i.e., we started with all edges included, then keep removing the most expensive edges one by one—but only if removing them doesn’t disconnect the graph.
• What remains at the end is the minimum cost spanning tree.