On Oct 14, 10:18 am, Legend <[EMAIL PROTECTED]> wrote:
> Suppose that I have some data:
>
> 12,30
> 12,45
> 2,3
> 7,8
> 3,9
> 30, 8
> 45,54
> 56,65
>
> Where (a,b) indicates that a is connected to b. I want to get all
> connected nodes to one point. For instance, the output of the above
> example should be something like:
>
> Group 1
> 2,3
> 3,9
> Group 2
> 12,30
> 12,45
> 30,8
> 7,8
> Group 3
> 45,54
> Group 4
> 56,65
>
> The order is not important as long as the whole group stays together.
> Reason why they are grouped like that:
>
> 1. 2 is connected to 3 and 3 is connected to 9 and so we put all the
> three, i.e. 2,3,9 into one group.
> 2. 12 is connected to 45 and 12 is also connected to 30 so we put
> these in the same group but 30 is connected to 8 and 8 is connected to
> 7 so ultimately we put all these into the same group.
> 3. 45 and 54 are connected but not related to any other numbers so we
> put them into another group
> 4. 56 and 65 are connected but not related to any other numbers so we
> put them into another group
>
> I am unable to figure out an algorithm for this. Can someone guide me?
It seems to me that you are looking for all maximally connected
subgraphs of a graph. Flood fill should be the easiest/fastest way to
solve this one.
Hope this helps,
Muntasir
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
