Google for connected components... you'll probably land up some method using disjoint set structures and depth-first search...
On 10/16/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote: > > > > 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 -~----------~----~----~----~------~----~------~--~---
