алгоритм алгоритма — элементы PHP быстрой кластеризации, хранящиеся в массиве

Question

алгоритм алгоритма — элементы PHP быстрой кластеризации, хранящиеся в массиве

У меня есть массив, состоящий из 1,5 миллионов пар элементов (разделенных »):

$array {
[0] => "element1 element2"[1] => "element2 element3"[2] => "element8 element4"[3] => "element8 element5"[4] => "element4 element5"[5] => "element6 element7"[6] => ...
}

Каждая пара элементов уникальна, и элементы представляют собой строки длиной от 15 до 20 символов.

В моем конвейере этот массив означает [0] «element1 связан с element2», [1] «element2 связан с element3», …
Я хотел бы объединить все связанные элементы и получить вывод, похожий на:

 $array_output {
[0] => "element1 element2 element3"[1] => "element8 element4 element5"[2] => "element6 element7"[3] => ...
}

Я полагаю, что это очень простое задание, и мне, вероятно, не хватает очевидного способа сделать это, но я не нашел быстрого способа кластеризации своих элементов (то есть от нескольких минут до нескольких часов).

2

clique graph-algorithm php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

У вас есть график, представленный в виде списка смежности, и вы хотите преобразовать его в список связанных компонентов графика. Лучший способ сделать это — создать наборы узлов, которые соединены, и объединять их для каждого ребра, пока у вас не останется ребер.

Чтобы сделать это в PHP:

Преобразовать ваш ввод в многомерный массив ([["element1", "element2"],["element2","element3"]] так далее.)
Инициализируйте список узлов в представлении карты, где каждый узел указывает на набор, содержащий только этот узел (например, ["element1" => ["element1"],"element2" => ["element2"]] так далее.)
Для каждой пары в массиве из (1) объедините наборы двух элементов в массиве из (2) и укажите оба элемента, а также любые другие элементы в наборе, на вновь объединенный набор
Поместите все наборы из (3) в набор (наборов), чтобы вы получили каждый из них только один раз
Преобразуйте каждый набор в желаемый формат вывода

Вы хотите использовать справочный оператор (&) для повторного использования тех же массивов в (3). Алгоритм было бы намного проще реализовать в Java или в чем-то еще с более очевидными хэш-картами и хеш-таблицами.

0