Graph optimization problem

Revision en1, by Mr.Awesome, 2016-09-02 15:11:30

Hi everyone.

Lets suppose that we have an array a with some elements, and a function f(x,y) that takes 2 elements and return true if these elements are connected and false otherwise.

We want to extract all connected components.

Note that if f(x,y) = true and f(y,z) = true then x,y,z are in the same connected component even though f(x,z) = false

My simple solution is to iterate over each pair(x,y) and connect them if f(x,y) = true , and then extract all connected components.

The complexity of this solution is O(n^2) , However i'm looking for a better solution. Thanks.

Tags graph, optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Mr.Awesome 2016-09-02 18:18:28 103
en2 English Mr.Awesome 2016-09-02 18:10:24 362
en1 English Mr.Awesome 2016-09-02 15:11:30 615 Initial revision (published)