MST Builder

Select an algorithm to start!

Learning Trace

Start an algorithm and make your choices to see your learning progress here!

Graph Parameters

Parameters

Graph Info

Vertices: 6

Edges: 0

Selected Edges: 0

Current Weight: 0

MST Weight: 0

MST Algorithms

Kruskal's Algorithm

• Sort edges by weight

• Add edge if no cycle formed

• Uses Union-Find structure

• Click the correct next edge!

Prim's Algorithm

• Start from any vertex

• Always add minimum weight edge

• Grows tree from single vertex

• Click the correct next edge!

Spanning Trees

A spanning tree is a subgraph that includes all vertices and is both connected and acyclic.

Properties:

  • Contains exactly n-1 edges for n vertices
  • Connects all vertices with minimum edges
  • Contains no cycles
  • Removal of any edge disconnects the graph

Applications:

Network design, cluster analysis, image segmentation, and approximation algorithms.

Kruskal's Algorithm

A greedy algorithm that finds the MST by sorting edges and adding them if they don't create cycles.

Algorithm Steps:

  1. Sort all edges by weight
  2. Initialize Union-Find structure
  3. For each edge, add if no cycle is formed
  4. Stop when n-1 edges are added

Time Complexity:

O(E log E) where E is the number of edges, dominated by the sorting step.

Prim's Algorithm

A greedy algorithm that grows the MST from a starting vertex by always adding the minimum weight edge.

Algorithm Steps:

  1. Start with any vertex
  2. Add to priority queue all edges from current tree
  3. Select minimum weight edge to unvisited vertex
  4. Repeat until all vertices are included

Time Complexity:

O(E log V) with binary heap, O(E + V log V) with Fibonacci heap.