[Java] Find minimum number of connections to create fully connected graph from start vertex

In case you were wondering why did we implement the path-based, Tarjan and Kosaraju algorithms for finding strongly connected components, this video quiz is the reason.

We are given a graph representing airline routes and a start city. We need to determine the minimum number of connections to add from the start city so that every other destination is reachable in any number of hops from there.

We are given the following sample graph:

 
DSM -> ORD -> BGI -> LGA <-  
 ^                        |  
 |                        |  
 SFO -> SAN -> EYW -> LHR |  
 ^                     |  |  
  \--------------------|  |  
                          |  
 JFK ---------------------/  
 ^  ^  
 |   \  
 ICN <- HND <- EWR  
   
 TLV -> DEL -> DOH  
       |  
       v  
 SIN <-> CDG -> BUD  

We remember that all nodes in a strongly connected component are reachable from all other nodes in the same component, so we can simplify the graph by finding and squashing all strongly connected components in it.

Using:

SCC1 = EYW, LHR, SFO, SAN

SCC2 = SIN, CDG

We get:

SCC1 -> DSM -> ORD -> BGI -> LGA  
                               ^  
 EWR -> HND -> JFK ------------|  
    |    ^  
    v   /  
     ICN  
   
 TLV -> DEL -> SCC2 -> BUD  
       |  
       v  
     DOH  

 

Now taking as sample start "LGA", we can easily find which new routes we need to add. 

We can observe that ignoring the start node and its SCC (if any), all others nodes or SCCs that do NOT have any incoming edge are part of our solution since there is NO way to reach them at all.

Our solution then follows these steps:

• calculate all SCCs in the graph, we use Tarjan's algorithm for this: O(V + E)
  
• calculate which nodes have at least one incoming edge. Start node and its SCC, if any, are always reachable so count them as having an incoming edge. Edges among nodes in same SCC are NOT counted, we need an external connection into the SCC. If a node has an incoming edge, its whole SCC, if any, has the same incoming edge: O(V + E)
• add every node in the graph that did NOT have an incoming edge to our solution. If the node was part of a SCC, pick only ONE node from it since the whole SCC would be reachable afterwards: O(V)

Our solution runs in O(V+E) time and uses O(V) extra space.

You can find my implementation of findMinimumNewEdgesForFullyConnectedGraphFromStart on my Gist along with some tests in MinimumEdgesForFullyConnectedGraphJTests.