Добрый день.
Не могу сообразить, как должен выглядеть правильный алгоритм (язык C#, но это неважно).
Имеется N элементов z1, z2, ..., zN. Два элемента zi и zj могут иметь отношение связанности (а могут не иметь). Отношение связанности является транзитивным. Т.е. если zi и zj связаны, и также zj и zk связаны, тогда zi и zk также являются связанными.
Отношения могут быть выражены матрицей, где 1 обозначает связанность, 0 - её отсутствие. Имея подобную матрицу, необходимо посчитать количество кластеров, т.е. подмножеств элементов; в каждом кластере все элементы связаны друг с другом, но не связаны с элементами из других кластеров.
Пример 1: 4 элемента
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
Отсюда, можно видеть, что связаны элементы 1 и 2, также 2 и 3 => связаны 1,2, и 3, образуя 1-й кластер. Элемент 4 не связан ни с кем, и образует 2-й кластер из одного элемента.
Пример 2: 3 элемента
1 0 0
0 1 0
0 0 1
тут, как можно видеть, имеются три кластера из одного элемента каждый.