💻 Minimum Cost Railway Network with Kruskal

Connect cities with minimal cost using greedy MST — sort segments, add without cycles via Union-Find, visualize the spanning tree!

🚂 The Logistics Connector's Challenge

🎯 The Challenge:

You are given cities and costs to build railway track segments. Find the minimum cost to connect all cities (MST).

📋 Problem:

Implement Kruskal's: sort edges, add if no cycle (Union-Find), sum costs if connected, else impossible.

Problem Specifications

  • Input: N (1≤N≤10), M (1≤M≤10), M lines u v w.
  • Output: Min cost if connected, else "It is not possible to connect all cities."

Example: Input 1

3
3
0 1 4
1 2 5
0 2 3

Output: 7 (edges 0-2:3, 0-1:4)

🔄 Kruskal's Algorithm Strategy

Key Idea

  1. Sort all M edges by increasing weight.
  2. Init Union-Find: each city parent itself, components=N.
  3. For each sorted edge (u,v,w): if find(u) != find(v), union(u,v), add w to cost, components--.
  4. If components==1, output cost; else impossible.

Note: Union-Find with path compression/rank for efficiency, but N≤10 simple ok. Greedy: cheapest safe edges first.

Kruskal

Time: O(M log M + M α(N))
Space: O(N)

Prim

O((N+M) log N) — similar

🔍 Step-by-Step Kruskal Demo

Ready. Use controls below to start demo.

Edges (sorted by weight)

Union-Find Components

Total Cost: 0

Progress Tracker

1. Sort edges by weight ascending
2. Init Union-Find: each city alone (N components)
3. For each edge (u,v,w): if different components
4. Union components, add w to cost, components--
5. Skip if same component (cycle)
6. If 1 component: cost; else impossible

🎮 Build Your MST Cost Calculator

Enter N, M, segments and press Compute

Examples

Sample 1 (N=3,M=3)
→ 7
Sample 2 (N=6,M=8, disconnected)
→ It is not possible...

📊 Analysis & Optimization

Time

O(M log M)

Sort + Union-Find nearly linear.

Space

O(N + M)

Edges + parent array.

Optimization Ideas

  • Union by rank/path compression for α(N) ~ constant.
  • For larger N, Kruskal efficient for sparse graphs.
  • In C++, vector> edges; sort by get<2>; vector parent(N).
  • Check connected: components ==1 after N-1 edges or Union-Find find all same root.