I'm stuck :(?

Question

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?

Anonymous · Accepted Answer

Algorithm for group 1:

For each node (a, b)
- For each other node (c, d)
- - If a = d or b = c Add (a, b) and (c, d) to group1 Unless they were already added to group 1

Algorithm for group 2:

For each node (a, b)
- For each other node (c, d)
- - If a = c Add (a, b) and (c, d) to group 2 Unless they were already added to group 2

After running those two algorithms, you could just start picking up any two random nodes and making groups with them.

back2nature · Answer

Can try the recursive way.

Have an algorithm to merge two groups into 1 if these two groups should be merged according to your criteria.

Start with n groups containing one pair each.

Repeat applying the above test/merge algorithm to all possible pair of groups until there is no more possible merging

Trending News

I'm stuck :(?

2 Answers