## Introduction

In this article, we will discuss a very interesting problem based on the application of graph theory. We will solve the problem in one of the most intuitive ways and build the solution step by step, similar to how you are expected to solve an unknown problem in a coding interview.

You will also get to know the detailed analysis of time and space complexities, which will help you develop the complexity analysis of other questions too.

(Also, see Data Structures)

Let’s get started with the problem statement.

## Problem Statement

There are n cities and roads in between some of the cities. Somehow all the roads are damaged simultaneously. We have to repair the roads to connect the cities again. There is a fixed cost to repair a particular road.

Input is in matrix(city) form, if city[i][j] = 0 then there is not any road between city i and city j, if city[i][j] = a > 0 then the cost to rebuild the path between city i and city j is a.

Find out the minimum cost to connect all the cities by repairing roads.

### Example

Let’s take some examples to understand the goal of this problem.

**Input**

n=5

matrix city[n][n] is given as -

**Output**

`11`

**Explanation**

If we consider the cities as nodes and the roads between them as edges of a graph, then we will obtain a weighted graph as shown below -

Among all possible ways, the most optimal path connecting all the cities to get the minimum cost is:

So, we obtain the minimum cost by repairing the roads connecting the cities 1-4, 1-3, 3-2, and 3-5.

**How to approach the problem? **

The most important step towards approaching the problem is to first understand the problem. So, here you have to find the minimum cost to connect all the cities.

**What do you understand by the problem statement?** 💡

Connecting all cities implies that there should exist at least one path between every two cities. That is, you should be able to travel from any one city to any other city through a road connecting them.

You might think that I have n cities and some roads to repair. Now, I just need to connect the cities by repairing the roads such that all cities are connected. Well, this sounds easy. I will repair all the roads and check if all cities are connected.

**Does this work? **

Well, this solves just a part of the problem.

There are two goals to achieve in this problem -

- Connect all cities
- The cost of connecting them should be minimum

**Do we have a standard concept in graph theory that achieves the above two requirements?**

The great news is, **Yes**🤩. Can you remember?

If yes, then well done!! You must have been practicing the graph theory concepts by heart.

If not, it's never too late to learn an important concept 😎. Before moving further to make the most out of this blog, you should consider reading this beginner-friendly article: Introduction and Properties of Minimum Spanning Tree.

We know about Minimum Spanning Tree(MST) in a graph, and the problem in this blog is a direct application of MST.

**Minimum Spanning Tree(MST)** - A minimum spanning tree is nothing but a subset of a graph that connects all the vertices without forming a cycle and with minimum cost.