avatar_url

Sandesh Rana | Python

I'm a developer from Himalayas, with a passion for crafting efficient and elegant code, with creativity and precision.

Minimum Spanning Tree

21 Aug 2024 » programming, datastructure, graph

Minimum Spanning Tree (MST): Easy to Hard Problems

Easy

  1. Kruskal’s Algorithm Implementation (Not directly MST but involves understanding of MST concepts)
  2. Union-Find Data Structure (Useful for Kruskal’s Algorithm)
  3. Graph Valid Tree (Checks if a graph is a valid tree, which involves MST properties)
  4. Find the Redundant Connection (Finds an edge that creates a cycle, relevant for MST understanding)
  5. Find the Town Judge (Involves concepts of connectivity and component checking)

Medium

  1. Minimum Spanning Tree (Direct MST problem)
  2. Network Delay Time (Involves finding shortest paths with MST concepts)
  3. Connecting Cities With Minimum Cost (Direct MST problem)
  4. Cheapest Flights Within K Stops (Related to pathfinding and minimum costs, can be related to MST concepts)
  5. Kruskal’s Algorithm (Classic problem for understanding MST algorithms)

Hard

  1. Minimum Cost to Connect All Points (Minimum spanning tree in 2D plane)
  2. Roads and Libraries (MST problem with additional constraints)
  3. Minimum Spanning Tree (Generalized Problem) (Generalized MST problem with custom constraints)
  4. Find the Minimum Spanning Tree Weight (Advanced MST problem with specific weight constraints)
  5. Optimal Network Design (Complex network design problem involving MST concepts)
  6. Maximum Spanning Tree (Variant of MST where the goal is to maximize the spanning tree weight)
  7. Traveling Salesman Problem (TSP) with MST Heuristic (Advanced problem involving MST heuristics for solving TSP)
  8. Advanced Minimum Spanning Tree Algorithms (Complex MST problem involving advanced algorithmic techniques)