4 Replies - 376 Views - Last Post: 11 September 2017 - 07:13 AM

#1 Patras  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 01-September 17

Connect k connected components of a graph

Posted 10 September 2017 - 11:23 AM

Hello everybody! Please help me to solve it I'm few days from my exam.
If something is unclear feel free to ask
By connected components I mean components of the graph that are formed by connected nodes, therefore every node of this component is accesible within the component by a traversal.
To connect k connected blocks we need at least k-1 edges.

The request is to make an algorithm that connects all the k connected components of a graph with k-1 edges.
The real problem is maintaining the time performance of a DFS traversal.
O(n+m) where n are the nodes and m are the edges.

We could imagine every connected component as a node and get k nodes. This way our vertex list reduces and now what we have to do is to connect these vertexes like a linked list.
If we try to roughly do a traversal overwriting every status of the node from unexplored to visited, when we complete the traversal of a connected component, we have to go back to our vertex list and look for unexplored nodes to find another connected component. This takes another time and if we imagine this for k connected componenets we get something like O(n^2+m) as worst case could be n=k independent nodes.

Coming back to the idea of the reduced vertex list I thought to do these steps:
1. Clone the original graph, inserting inside clone's nodes references to the original ones
2. Pick up a unexplored node from the cloned list and do a traversal until its connected component gets completely visited and while visiting remove every node already visited once its edges are completely visited (BFS visit). From this connected component we should only have the first one picked up.
3. Even though we just removed a node, we still visit the others as we removed it only after passing through everyone of its edges.
4. Once done and there are no other nodes, get back to the copy of the original list where we should have only unexplored nodes. Like this we don't need to look for them as a graph could have implemented a method that removes even the reference from the vertex list, reducing automatically the vertex list size.
5. Get the reference from the previously picked up node to the original one. In the vertex copy list (clone graph) look for another unexplored node (takes literally O(1) time) and get to the original one node. Connect them in the original graph, and choose the node that we just took as "copy reference node" be the next picked up node for step 2 and now remove from this clone graph the previously picked up node. Go to step 2.

All this stuff should work but there're two conditions that I don't know if they could be tollerated:

a) Is it a good idea to clone a graph (also containing in every node references to the original nodes)?
Would it anyway take O(n+m) time?

B) And this one that is hardly right: O(1) time to remove a node of a graph from the vertex list, reducing even the size of the list. I don't think it's usually possible, maybe modifing the classical graph implementations but it might get bloody hard.


I think my whole solution is too complicated and almost wrong. Anyone has any better advice please? :helpsmilie:

Is This A Good Question/Topic? 0
  • +

Replies To: Connect k connected components of a graph

#2 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12176
  • View blog
  • Posts: 45,243
  • Joined: 27-December 08

Re: Connect k connected components of a graph

Posted 10 September 2017 - 12:39 PM

Hint: I would suggest looking at Tarjan's algorithm. It will be helpful here.

Hint 2: if you have k isolated vertices, can you efficiently construct edges to construct a spanning tree? This is the easy part.

I will also add that just like your last post, you're getting too bogged down by implementation details. Focus on the high level procedure and solving the problem. The implementation details come later.

This post has been edited by macosxnerd101: 10 September 2017 - 12:40 PM

Was This Post Helpful? 0
  • +
  • -

#3 Patras  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 01-September 17

Re: Connect k connected components of a graph

Posted 10 September 2017 - 11:46 PM

View Postmacosxnerd101, on 10 September 2017 - 12:39 PM, said:

Hint: I would suggest looking at Tarjan's algorithm. It will be helpful here.

I've just taken a look at this algortithm but it's something I wouldn't have to know for this exam. Anyway it's for strongly connected nodes, if there's something useful I really can't find.


View Postmacosxnerd101, on 10 September 2017 - 12:39 PM, said:

Hint 2: if you have k isolated vertices, can you efficiently construct edges to construct a spanning tree? This is the easy part.

Well do you mean the connection between every couple of verticles? Then it depends on the implementation... Using an Edge List it would take O(1) but then a BFS traversal gets too hard (maybe even impossible, we need an Ajency List for that)
But as I said previously: if it took O(1), it could be efficient as removing everytime visited nodes from the vertex list (apart from the one picked up) would make the whole thing O(n) when it's completed.

The solution should be easy in my opinion but I can't get it
Was This Post Helpful? 0
  • +
  • -

#4 Patras  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 01-September 17

Re: Connect k connected components of a graph

Posted 11 September 2017 - 06:38 AM

I got it! It should be enough if Vertex List is an array to save the index of the node I've picked up and do a for cycle. Something like this:
for (int i = 0; i < G.vertex_number; ++i) {
    if (G.labels[i] == UNEXPLORED) {
        // New connected component
        if (i > 0) {
            G.adjacents[0].append(i);
            G.adjacents[i].append(0);
        }
        BFS(G, i);
    }


Because the only risk is to examine again nodes I've already visited of the same connected component. This way the worse case would be O(2n+m) so there's no problem it asintotically becomes O(n+m).

It's not better in terms of time performance than what I proposed previously but it is certainly easier to write and understand. Also takes less memory... This is the best solution.

Anyway thanks for the replies
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12176
  • View blog
  • Posts: 45,243
  • Joined: 27-December 08

Re: Connect k connected components of a graph

Posted 11 September 2017 - 07:13 AM

Can you view an undirected graph as a directed graph? Are the connected components of an undirected graph the same as the strongly connected components on the corresponding digraph? In light of this, you should re-examine Tarjan's algorithm. You might also poke through how the algorithm works to get a feel for the techniques being used. Being able to understand and adapt a technique is a timeless skill, which may actually be helpful on an exam.

Regarding my second hint, draw k isolated vertices on a piece of paper. Then add edges until you have a spanning tree. Focus on this at a high level first, NOT at an implementation level. Do you see how these k isolated vertices are analogous to your k connected components?

This post has been edited by macosxnerd101: 11 September 2017 - 07:15 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1