2

Добрый день.

Не могу сообразить, как должен выглядеть правильный алгоритм (язык 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

тут, как можно видеть, имеются три кластера из одного элемента каждый.

1

2 ответа 2

2

Ну это же обычный неориентированный граф, матрица инцеденций, поиск связных компонентов... Просто выполняете поиск в глубину (или в ширину).

Описания есть везде, см., например, тут.

Реализовать могу только на C++, C# могу только читать, но не писать :)

0
0

Написал такую реализацию на JavaScript:

var arr = [[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1]];
//var arr = [[1, 1, 0], [1, 1, 1], [0, 1, 1]];
//var arr  = [[1, 0, 0], [0, 1, 0], [0, 0, 1]];


var check = function(i) {   

    var was1 = false;

    for (var j=0; j<arr.length;j++) {
        if (arr[i][j] == 1) {
            was1 = true;
            arr[i][j] = 0;
            check(j);
        }
    }   
    if (was1)
        return 1;
    else
        return 0;
}

var count = 0;

for (var i=0; i<arr.length;i++) {   
    count += check(i);  
}

alert(count);

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.