# Add edges to undirected graph to make connected and minimize longest path

I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the number of vertices on the longest path in the resulting connected graph. As a result I need the number of vertices on the longest simple path in the resulting graph.

For example, given a graph with the following edges:

1 0
2 0
4 3
5 3


There are multiple ways to add edges to make it a connected graph. But since I want to minimize the number of vertices on the longest path in the resulting graph, I have to add an edge between 0 and 3. Now the path with the most vertices contains 4 vertices (2 -> 0 -> 3 -> 5). If I had added an edges between 2 and 4 then the path with the most vertices would've been 1 -> 0 -> 2 -> 4 -> 3 -> 5.

Another example, given a graph with the following edges:

0 1
1 2
3 4
5 6


Here two edges need to be added: between 1 and 3 and between 3 and 5. The path with the most vertices then contains 5 vertices.

My approach was to first use DFS to identify all components. Then, for each component, I find the longest path in that component, I take the vertex that is in the middle of each of those paths and connect them. This results in one connected graph. In that resulting graph I can find the path with the most vertices. I suspect that there must be a more efficient approach to this, especially since it needs to work for a disconnected graph with at most $$10^6$$ vertices. Hopefully someone has a better idea on how to solve this.

Here goes the algorithm. In each step we find the connected components of the graph and we handle them as different graphs say $$G_1, \dots, G_l$$. Note that the task is to add $$l-1$$ edges between these graphs in a way that makes them connected. Each time we add an edge we will combine two graphs and decrease $$l$$ by one until it gets to the value 1.
The eccentricity of each component can be built using a BFS from each vertex in total quadratic time in the size of the input graph. Each iteration can be implemented in constant ime (for example keep a stack of pairs (central, eccentricity) and in each step pop two elements, unify them and push thr new pair back to thr stack. each step decreases the size of the stack by one and hence we end after $$l-1$$ steps.