How to separate an array of pairs into sets?

Question

I need to solve a problem in java and I’m having difficulties. I have the matrix with the following pairs:

0 - 1
1 - 2
2 - 4
2 - 5
3 - 6
4 - 5
6 - 7

I would like to group these figures as follows: --If the number 'x' is linked to 'y' and the number 'y' is linked to the number 'z', then I will group x, y, z , in the same group. The result Obtained would be:

Grupo A: 0,1,2,4,5
Grupo B: 3,6,7
Grupo C: 8

Thank you! I await your reply!!

Answer 1

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 traverse the graph nodes;

2) For each unidentified node that is found, you should assign a group identifier to it;

3) You should assign the same group identifier to all adjacent nodes, i.e., to all nodes that are accessible from that node;

4) When there are no more adjacent nodes that can be identified, you will start a new cycle by choosing another unnamed 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 group of nodes;

6) When there are no more nodes to identify with, the number of identifiers is the same number of groups contained in the graph.

In this example graph, the identification of groups is done through distinct colors:

Pairs:

1) Grupo Azul:

    a) 1-2
    b) 2-3
    c) 3-4
    d) 3-5
    e) 4-5
    f) 4-7
    g) 5-6
    h) 6-7

2) Grupo Verde

    i) 16-15
    j) 15-17
    k) 17-18
    l) 15-18
    m) 19-18
    n) 19-17
    o) 16-17


3) Grupo Vermelho:

    p) 10-11
    q) 14-11
    r) 10-13
    s) 12-13
    t) 10-12
    u) 12-14
    v) 12-11

4) Grupo Amarelo

    w) 8-9

This link also seemed interesting: Connected-Component Labeling

I hope I’ve helped!