Disjoint Sets and Graphs

Sets =>
- Satu set adalah kumpulan objek.
- Himpunan A adalah himpunan bagian himpunan B jika semua elemen A berada di B.
  + Subset adalah set
- Persatuan dua set A dan B adalah set C yang terdiri dari semua elemen dalam A dan B
- Dua set saling terpisah jika mereka tidak memiliki elemen yang sama.
- Partisi himpunan adalah kumpulan himpunan bagian sehingga
  + Persatuan dari semua himpunan bagian ini adalah himpunan itu sendiri
  + Setiap dua himpunan bagian saling terpisah

Disjoint Sets =>
- Set disjoint berbeda dari set
- Disjoint Set juga dikenal sebagai Union-Find
- Set Disjoint adalah struktur data yang menjaga kesetaraan hubungan.
- Pembagian satu set ke banyak kelompok berdasarkan pada relasi ekivalensi disebut partisi
- Disjoint Set adalah struktur data yang melacak sekumpulan elemen yang dipartisi menjadi sejumlah    subset disjoint (non-overlapping).
- Disjoint Set dapat digunakan untuk menentukan siklus dalam grafik, yang membantu dalam                menemukan pohon spanning minimum grafik.

Disjoint Set Operations =>
- makeSet (x)
  + Operasi ini membuat set baru yang mengandung elemen x.
  + Satu set yang hanya memiliki satu elemen disebut set singleton.
- findSet (x)
  + Operasi ini mengembalikan perwakilan dari set di mana x hadir.
  + Berguna dalam memeriksa apakah suatu elemen termasuk dalam set
- union (x, y)
  + Ini membuat set baru yang mengandung elemen set x dan y dan kemudian menghapus set                   individu  x dan y.

Application =>
- Disjoint-set struktur data memodelkan partisi dari set, misalnya untuk melacak komponen yang        terhubung dari grafik yang tidak diarahkan. Model ini kemudian dapat digunakan untuk menentukan apakah dua simpul milik komponen yang sama, atau apakah menambahkan tepi di antara mereka akan menghasilkan siklus. Algoritma Union – Find digunakan dalam implementasi unifikasi kinerja tinggi.

- Struktur data ini digunakan oleh Perpustakaan Grafik Peningkatan untuk mengimplementasikan fungsionalitas Komponen Terhubung yang Tambahannya. Ini juga merupakan komponen kunci dalam mengimplementasikan algoritma Kruskal untuk menemukan pohon rentang minimum dari grafik.

- Perhatikan bahwa implementasi sebagai hutan disjoint-set tidak memungkinkan penghapusan tepi, bahkan tanpa kompresi jalur atau heuristik peringkat.

- Sharir dan Agarwal melaporkan hubungan antara perilaku kasus terburuk dari disjoint-set dan panjang urutan Davenport-Schinzel, struktur kombinatorial dari geometri komputasi.

Referensi = https://en.wikipedia.org/wiki/Disjoint-set_data_structure