Алгоритм группировки связанных элементов

Question

У меня есть набор предметов.Каждый предмет в наборе может быть связан с одним или несколькими другими предметами.Я хотел бы построить алгоритм, который группирует элементы, которые связаны друг с другом, напрямую или через другие элементы.

Пример: Мой набор: {a, b, c, d, e,f}

a и b связаны между собой.c относится к d, а d относится к e.

Алгоритм должен создавать следующие группы: {a, b}, {c, d, e}, {f}

Anyидеи эффективного алгоритма для этого?Заранее спасибо: -)

Answer 1

Использование Союз Найти . Это невероятно быстро. Используя сжатие путей, сложность сводится к O (a (n)), где a (n) - обратная функция Аккермана.

Answer 2

Чтобы немного расширить ответ st0le ...

Итак, у вас есть список элементов:

a, b, c, d, e, f

И список отношений:

ab
cd
de

Инициализируйте, поместив каждый элемент в его собственную группу.

Затем выполните итерацию по вашему спискуотношения.

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

Итак, в этомпример:

1: init -> {a}, {b}, {c}, {d}, {e}, {f}  
2: a-b -> {a,b}, {c}, {d}, {e}, {f}  
3: c-d -> {a,b}, {c,d}, {e}, {f}
4: d-e -> {a,b}, {c,d,e}, {f}

Вам, очевидно, придется проверить все ваши отношения.В зависимости от того, как вы реализуете часть поиска, это будет влиять на эффективность вашего алгоритма.Поэтому на самом деле вы хотите знать, какой самый быстрый способ найти элемент в наборе групп элементов.Наивный подход сделает это за O (n).Вы можете улучшить это, ведя учет, в какой группе находится данный элемент. Затем, конечно, когда вы объединяете две группы, вам придется обновить свою запись.Но это все еще полезно, потому что вы можете объединить меньшую группу в большую, что сэкономит на количестве записей, которые вам нужно обновить.