🎯 What is Borůvka's Algorithm?
Borůvka's Algorithm is a greedy algorithm for finding the Minimum Spanning Tree (MST) of a connected, weighted graph. Developed by Otakar Borůvka in 1926, it was the first MST algorithm ever published.
- Time Complexity: O(E log V) where E = edges, V = vertices
- Space Complexity: O(V) for Union-Find data structure
- Parallel Nature: Naturally suited for distributed computation
- Applications: Network design, clustering, circuit design
🧮 Algorithm Steps
- Initialize: Each vertex starts as its own component
- Find Minimum Edges: For each component, find the minimum weight edge leaving it
- Add to MST: Add all minimum edges to the MST (avoiding cycles using Union-Find)
- Update Components: Merge components connected by new edges
- Repeat: Continue until only one component remains
Key Property: Each phase reduces the number of components by at least half
Phases: At most log V phases needed for completion
🔧 Graph Configuration
- Weight Types:
- Random: Random integer weights (1-20)
- Distance-based: Weights based on Euclidean distance
- Selection Mode: Click vertices to select them for custom graph creation
- Animation Speed: Control visualization speed (0.25x to 3x)
🎮 Graph Operations
- Generate Random Graph: Creates 6-8 vertices with random edges
- Create Complete Graph: Connects all existing vertices
- Create from Selected: Creates graph using only selected vertices
- Manual Creation: Click to add vertices, click two vertices to add edges
- Clear Graph: Removes all vertices and edges
⚙️ Execution Modes
- Automatic Mode: Algorithm runs with smooth animations between steps
- Step-by-Step (Manual): Use "Next Step" button to advance through each phase
- Standard Borůvka: Classic centralized version of the algorithm
- Distributed Version: Simulates parallel processing with visual processor highlighting
📊 Visual Elements
- Vertices: Blue circles with component labels (C1, C2, etc.)
- Edges: Lines with weight labels
- MST Edges: Thick green lines when added to MST
- Minimum Edges: Highlighted in yellow during selection
- Selected Vertices: Orange outline in selection mode
- Processors: Yellow highlighting during distributed simulation
📈 Performance Metrics
- Total Cost: Sum of weights of edges in MST
- Current Phase: Which phase of the algorithm is executing
- Components: Number of remaining separate components
- MST Edges: Number of edges currently in the MST
- Graph Stats: Vertices, edges, connectivity, and density
🌐 Distributed Computing
Borůvka's algorithm is particularly well-suited for parallel and distributed computing:
- Parallel Edge Finding: Each processor can independently find minimum edges for assigned components
- Communication Phase: Processors exchange minimum edge information
- Synchronization: All processors must complete before next phase
- MPI Implementation: Download production-ready MPI code for real distributed systems
🧪 Educational Experiments
- Basic MST: Create simple connected graph, run algorithm in manual mode
- Compare Modes: Run same graph in automatic vs manual mode
- Distributed vs Centralized: Compare standard vs distributed versions
- Graph Types: Test on complete graphs, sparse graphs, different densities
- Weight Impact: Compare random vs distance-based weights
- Scalability: Test with different graph sizes
🎯 How to Use This Visualizer
- Create Graph: Generate random graph or manually create vertices/edges
- Choose Mode: Select automatic or step-by-step execution
- Configure: Adjust animation speed and weight type
- Run Algorithm: Click "Run Borůvka's Algorithm" or "Run Distributed Version"
- Observe: Watch component merging and MST construction
- Analyze: Review performance metrics and activity logs
💡 Key Insights
- Greedy Choice: Always selecting minimum edges guarantees optimal MST
- Component Reduction: Each phase significantly reduces component count
- Distributed Advantage: Natural parallelism makes it ideal for large-scale systems
- Cycle Prevention: Union-Find ensures no cycles are created
- Historical Significance: First MST algorithm, predating Prim's and Kruskal's
⌨️ Keyboard Shortcuts & Controls
- F1 or Ctrl+H: Open/close this help guide
- Escape: Close this modal
- Mouse Controls:
- Click empty space: Add vertex
- Click vertex then another: Add edge
- Selection mode: Click to select/deselect vertices
- Speed Slider: Adjust animation speed in real-time