Algorithmus zum Gruppieren verwandter Elemente

Question

Ich habe eine Reihe von Elementen. Jedes Element in dem Set kann mit einem oder mehreren anderen Elementen in Beziehung stehen. Ich möchte einen Algorithmus erstellen, der Elemente gruppiert, die miteinander in Beziehung stehen, entweder direkt oder über andere Elemente.

Beispiel: Meine Menge {a, b, c, d, e, f}

a und b beziehen. c ist verwandt mit d und d ist verwandt mit e.

Der Algorithmus sollte die folgenden Gruppen erzeugen: {a, b}, {c, d, e}, {f}

Irgendwelche Ideen eines effizienten Algorithmus, dies zu tun? Vielen Dank im Voraus :-)

Answer 1

Verwenden Sie Union Find. Es ist unglaublich schnell. Bei der Pfadkomprimierung reduziert sich die Komplexität auf O (a (n)), wobei a (n) die Inverse der Ackermann-Funktion ist.

Answer 2

auf st0le den erweitern ein wenig beantworten ...

So haben Sie eine Liste der Elemente: Beziehungen

a, b, c, d, e, f

und eine Liste der :

ab
cd
de

initialisieren von eac platzieren h Element in seiner eigenen Gruppe.

Dann iterieren Sie über Ihre Beziehungsliste.

für jede Relation finden die Gruppe, wobei jedes Element ein Mitglied ist, und dann die Gruppenzu vereinigen.

So in diesem Beispiel:

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} 

Sie müssen natürlich alle Ihre Beziehungen überprüfen. Abhängig davon, wie Sie den 'Finden'-Teil implementieren, wird sich dies auf die Effizienz Ihres Algorithmus auswirken. Sie wollen also wissen, wie Sie am schnellsten ein Element in einer Gruppe von Elementen finden. Ein naives Vorgehen wird dies in O (n) tun. Sie können dies verbessern, indem Sie eine Aufzeichnung darüber führen, in welcher Gruppe sich ein bestimmtes Element befindet. Wenn Sie dann zwei Gruppen zusammenführen, müssen Sie natürlich Ihren Datensatz aktualisieren. Dies ist jedoch immer noch hilfreich, da Sie die kleinere Gruppe in die größere Gruppe zusammenfassen können, wodurch Sie sparen, wie viele Datensätze Sie aktualisieren müssen.