Minimum Spanning Tree Algorithms

[JohnnyWan1123]

Description

Implement Kruskal's and Prim's algorithms for finding minimum spanning trees, and add verification logic to check if a student's submitted tree is a valid MST.

Tasks

• Implement Kruskal's algorithm with union-find data structure
• Implement Prim's algorithm with priority queue
• Add MST verification (check if tree is spanning and minimum weight)
• Support both algorithms with auto-selection
• Handle disconnected graphs gracefully
• Write unit tests with various graph configurations
• Add visualization support for MST edges

Acceptance Criteria

• Both algorithms produce correct MSTs
• Verification correctly identifies valid/invalid MSTs
• Works with weighted graphs
• Handles edge cases (single node, disconnected components)
• Unit tests achieve >90% coverage