City Network Connection Planner

A small project that determines the minimum cost to connect all cities (nodes) using roads, cables, or network links, ensuring full connectivity with no loops. The solution applies Kruskal’s Minimum Spanning Tree (MST) algorithm to find the optimal set of connections with the least total cost.

Objective

To design a system that determines the minimum cost to connect all cities using road, cable, or network links, ensuring full connectivity with no loops. The project applies Kruskal’s Minimum Spanning Tree (MST) algorithm to find the optimal set of connections with the least total cost.

Theory

In a connected, weighted graph, a spanning tree connects all vertices with the minimum number of edges (V − 1).
The Minimum Spanning Tree (MST) ensures that the total edge weight (cost) is minimum among all possible spanning trees.

Kruskal’s Algorithm is a Greedy Algorithm used to find an MST by:

1. Sorting all edges in increasing order of weight.
2. Adding the smallest edge to the MST if it doesn’t form a cycle (checked using Union-Find / Disjoint Set).
3. Repeating until there are exactly V − 1 edges in the MST.

Applications:

• Designing telecommunication networks
• Electrical grid layout
• Road or railway system planning
• Internet backbone and infrastructure design

Algorithm Steps (Kruskal’s Algorithm)

1. Input number of cities (vertices) V and number of possible connections (edges) E.
2. For each connection, input: source city, destination city, and cost.
3. Sort all edges in ascending order by cost.
4. Initialize the disjoint set (parent/rank arrays) for V vertices.
5. Iterate through sorted edges:
   • Use find() to check the roots of the endpoints.
   • If roots differ, include the edge in the MST and union the sets.
6. Stop when MST contains exactly V − 1 edges.
7. Display the selected edges and the total minimum cost.

Time Complexity

Step	Operation	Complexity
Sorting edges	Sorting (current/basic version)	O(E²) (naive) — can be improved to O(E log E)
Union-Find operations	For each edge	O(E × α(V)) ≈ O(E)
Overall		O(E²) (for a simple/naive sort) or O(E log E) (if efficient sorting is used)

Space Complexity

• Arrays for edges, parent, and result: O(E + V)
  Therefore, Space Complexity = O(V + E)

Example Input / Output

Example input (console):

Number of cities: 4
Number of connections: 5
Edges (u v w):
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

Expected output:

Selected edges in the MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Total minimum cost : 19

Notes:

• City numbering may start at 0 or 1 depending on implementation; adjust input/output accordingly.

How to Build and Run (C)

Compile:

gcc main

Run:

./a.exe

Conclusion

The City Network Connection Planner demonstrates how Kruskal’s MST algorithm can be applied to minimize the total cost of connecting multiple cities or nodes. By using the Greedy approach, the program ensures that at every step, the least costly connection is chosen without forming cycles. This algorithm forms the foundation for real-world systems like telecommunication network design, transportation planning, and electrical grid optimization.

Contact

For questions or contribution discussions, open an issue or contact the repository owner.