LC: 1135. Connecting Cities With Minimum Cost - spiralgo/algorithms GitHub Wiki

1135. Connecting Cities With Minimum Cost

The Essence:

The problem-solver needs to be able to recognize what information problem implies about the solution. The problems don't usually state what they're about. It's important to actually notice their essence.

• The connected cities would form a graph.
• The minimum length connection should have no cycles.
• The connection of the cities will thus form a tree.
• The task is then to find the tree with the minimum total length that includes all the nodes.

Details:

This is a well-known problem in computer science called "Minimum Spanning Tree". The most famous and simplest algorithms for solving this problem are Prim's algorithm and Kruskal's Union-find algorithm. These are both greedy algorithms. The problem-solvers should familiarize themselves with such concepts.