Algorithm to make undirected graph be connected

Question

Sorry if there is already a question asking this, but I couldn't find anything relevant to this specific problem. I have a set of defined nodes that I want to make an undirected, connected graph from. I also have a set of edges connecting those nodes, but I'm not guaranteed that the collection of those edges makes the graph connected. An example of my situation is shown below.

Careful inspection will reveal that with the edges I have, the set of nodes is actually three graphs. What I want to do is find a way to determine the edges that I can add to my list of edges to make this into one connected graph. Preferably, I'd like to add as few edges as possible (i.e., I don't want to solve the problem by adding all possible edges). To add insult to injury, I don't want to add edges which cross over other edges (each node has a defined position).

Answer 1

It's possible efficiently to find the connected components (e.g. as described by u_seem_surprised). This leads to a list of all possible connecting links. Unfortunately this list is very long - any node in any one component can connect to any other, and it's not even obvious which components are best to connect. It will not be easy to find, from this long list, links which meet your non-crossing requirement.

I suspect there are not any known optimal algorithms for this sort of mixed problem. Instead I suggest you try some natural heuristics.

The best heuristics will depend on the characteristics of your problem (e.g. few components and many nodes or the other way round). But here is a possible example of the sort of heuristic I am thinking of.

To find the nodes to link between any two connected components, I suggest you start by trying nodes from component A that are nearest to the centroid in component B. I think that could be done efficiently using a spatial index. Then you can try to connect that node to the nearest nodes in component B, again using the index.

The algorithm to check if two links cross is pretty trivial.

To decide which components to connect I thought you could try something like this:

Create a new graph with a node for the centroid of each component. Add to the new graph a full mesh with link lengths equal to the distances between the centroids. Find a minimum spanning tree between these centroids on this new graph. Now connect the components along the minimum spanning tree.

However, this algorithm could tell you to connect components that cannot be connected (eg imagine a graph consisting of three concentric components - you will not be able to connect the outer to the inner). So this can only be a heuristic suggestion.

It might be better just to always connect a component to the other one that has the nearest nodes.

Answer 2

Like i said in the comment it can be done by finding the connected components using a dfs traversal, then taking the endpoints of the components and joining the components, so we know that the edges will be minimum i.e no of edges = no of components-1, I have written a c++ code using adjacency matrix, the adjacency list solution will be the same except for some implementation details.

#include<bits/stdc++.h>

using namespace std;

int n, m, G[100][100], vis[100], comp[100][100], sizeOfComp[100], noOfComp;

void dfs(int start){
    vis[start] = 1;
    comp[noOfComp][sizeOfComp[noOfComp]++] = start;
    for(int i = 0;i < n;i++){
        if(vis[i] == 1 || G[start][i] == 0) continue;
        dfs(i);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int p, q;cin >> p >> q;
        G[p][q] = 1;G[q][p] = 1;
    }
    for(int i = 0;i < n;i++){
        if(vis[i] == 0){
            dfs(i);
            noOfComp++;
        }
    }
    cout << "New Edges : " << endl;
    for(int i = 0;i < noOfComp-1;i++){
        cout << comp[i][0] << " " << comp[i+1][0] << endl;
    }

return 0;
}

Link to solution on Ideone : https://ideone.com/T0XKT3