I need to troubleshoot a problem in java and I'm having trouble. I have the array with the following pairs:
0 - 1
1 - 2
2 - 4
2 - 5
3 - 6
4 - 5
6 - 7
I would like to group these numbers as follows: - If the number 'x' has a connection with 'y' and the number 'y' has a link with the number 'z', then I will group x, y, z in the same group. The result would be:
Grupo A: 0,1,2,4,5
Grupo B: 3,6,7
Grupo C: 8
Thank you! I await response !!
The proposed problem can be solved with an algorithm called Flood Fill .
Important points to consider:
1) Implement a search algorithm ( BFS or DFS ) to go through the nodes of the graph;
2) For each unidentified node that is found, you should assign a group identifier to it;
3) You should assign the same group identifier for all nodes adjacent to it, ie for all nodes that are accessible from that node;
4) When there are no more identifiable adjacent nodes, you will begin a new cycle by choosing another unidentified node;
5) Note that the fact that the new node is not identified implies that it was not accessible from our previous node and therefore is part of a different node group; p>
6) When there are no more nodes to identify, the number of identifiers is the same number of groups contained in the graph.
In this example graph, the groups are identified by different colors:
Pairs:
1)GrupoAzul:a)1-2b)2-3c)3-4d)3-5e)4-5f)4-7g)5-6h)6-72)GrupoVerdei)16-15j)15-17k)17-18l)15-18m)19-18n)19-17o)16-173)GrupoVermelho:p)10-11q)14-11r)10-13s)12-13t)10-12u)12-14v)12-114)GrupoAmarelow)8-9Thislinkalsoseemedinterestingtome: Connected-component labeling
I hope I have helped!