CODEWITHSUNDEEP
graph-algorithm
Abhishek Kumar Paul
Abhishek Kumar Paul

Reputation: 1

Minimum number of edges needed to convert a forest into a tree

What is the minimum number of edges needed to convert a forest into a tree. Forest is given by an adjacency matrix. e.g. given this adjacency matrix (representing the forest) ,

0 0 0 0 0   
0 0 1 0 0   
0 0 0 0 0   
0 0 0 0 1   
0 0 0 0 0

what is the minimum no of edges needed to convert it to a graph. Well the answer is 1, but how to do it through a program ?

Upvotes: 0

Views: 866

Answers (1)

gilleain
gilleain

Reputation: 641

So you want to take a graph (which is potentially a forest of disconnected graphs) and find the minimum number of edges that will connect it? Fairly simple, I would say:

  1. Find the connected components of the graph.
  2. Return the count of the components minus 1.

The reasoning here is that for C components, you only need to (C - 1) edges to connect them up into a tree, which will connect the graph.

Upvotes: 2

Related Questions