1
$\begingroup$

I'm not a computer scientist, so please bear with me if I'm misusing some terminology.

What I'm trying to do is to find the different components of an undirected graph.

I have an array of pairs that represent the edges of my graph, like so: [[1,3],[4,2],[2,1],[5,6],[100,20],[22,5]] and what I want to create out of this are arrays (or objects) containing the connected vertexes (the disjoint sets or components, like this (for the above example): [[1,2,3,4],[5,6,22],[20,100]]

My first approach was to convert the array of pairs into an adjacency list, using hashmaps/tables/sets or something in this line it can be done in O(n) time and additional space (n being the number of pairs). Then using BFS, I scan every vertex in the graph. Whenever the queue is empty, I have completed a component/disjoint set. If unvisited nodes are still in the graph, this is a new component/disjoint set. Until all the nodes are visited.

Now, I learned about the disjoint-set data structure.

My question: Using disjoint-set data structure how can I convert my array of pairs into the disjoint components of the graph I'm looking for? Any resources are also very much appreciated. I'm still learning and don't really know what I'm talking about.

What are the pros and cons of the first approach compared to the second approach.

Oh, BTW, if this is the wrong place to ask this question, please, advise!

Thanks in advance!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Finding the connected components of a graph is a completely standard operation. You should use the standard techniques rather than inventing your own. $\endgroup$
    – David Richerby
    Commented May 1, 2019 at 16:30
  • $\begingroup$ Please, tell me the standard techniques. I'm not a computer scientist. I don't have a standard training in this field. And @DavidRicherby I'm asking because I am looking for the standard technique :-) $\endgroup$
    – kev
    Commented May 1, 2019 at 16:34
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Component_(graph_theory)#Algorithms $\endgroup$
    – David Richerby
    Commented May 1, 2019 at 16:39

1 Answer 1

Reset to default
3
$\begingroup$

In the disjoint-set approach you start from a collection of single vertices and repeatedly join the incident vertices of the edges. This will give you the connected components in $O(n+m\times(\text{find}+\text{union}))$.

The BFS approach takes only $O(n+m)$ and thus is faster, since the disjoint set operations take more than O(1).

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, the BFS approach is more efficient, if I understand that correctly. Can you please elaborate on your first approach? Is that the disjoint-set approach? Can point me to some resources/sample/etc? $\endgroup$
    – kev
    Commented May 1, 2019 at 16:37
  • 1
    $\begingroup$ @kev Yes to all. The disjoint set approach would look something like el = [[1,3],[4,2],[2,1],[5,6],[100,20],[22,5]]; a = IntDisjointSets(200); for e in el union!(a,e[1],e[2]) end; C=[ [] for i=1:200 ]; map(x->push!(C[find_root(a,x)],x),1:200); filter(c->length(c)>1,C) (This is code in Julia.) $\endgroup$
    – Marcus Ritt
    Commented May 2, 2019 at 11:36
  • $\begingroup$ Thanks, Marcus. I still don't understand everything but that's what I have to learn on my part. Cheers! $\endgroup$
    – kev
    Commented May 2, 2019 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.