Minimum Spanning Tree Calculator

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph. It connects all the vertices together without any cycles and with the minimum possible total edge weight. In other words, it is a tree that spans all vertices in a graph such that the sum of the weights of the edges is minimized.

Kruskal's vs. Prim's Algorithm

There are two classic greedy algorithms used to find the Minimum Spanning Tree of a graph:

• Kruskal's Algorithm: This is an edge-centric approach. It starts by sorting all the edges of the graph by their weight in ascending order. Then, it iterates through the sorted edges and adds each edge to the spanning tree if it does not form a cycle with the already chosen edges. Cycle detection is efficiently managed using a Disjoint Set Union (DSU) data structure. The time complexity is $O(E \log E)$ or $O(E \log V)$, where $E$ is the number of edges and $V$ is the number of vertices.
• Prim's Algorithm: This is a vertex-centric approach. It starts from a single arbitrary starting vertex and grows the MST one vertex at a time. In each step, it finds the minimum weight edge that connects a visited vertex to an unvisited vertex and adds it to the tree. The time complexity is $O(V^2)$ for simple implementations or $O(E \log V)$ using a binary heap/priority queue.

How to Use the MST Calculator

1. Select your preferred algorithm from the dropdown: Kruskal's or Prim's.

2. If you choose Prim's algorithm, choose the starting vertex from which the tree should grow.

3. Enter your graph's edges in the input textarea. Each line represents a weighted edge in the format: Source Node [space] Destination Node [space] Weight. For example, A B 4.

4. The calculator automatically parses the graph, checks for cycles or disconnected regions, and displays the Minimum Spanning Tree edges, total weight, and a step-by-step trace in real time.

For other graph problems, you can also use our Dijkstra's Shortest Path Calculator to find shortest paths.