Disjoint Sets & Graphs

Disjoint Sets & Graphs

Set adalah tipe data abstrak yang dapat menyimpan nilai-nilai tertentu, tanpa urutan tertentu, dan tidak ada nilai berulang. 
Disjoint Sets (Union-Find ) adalah struktur data yang menjaga kesetaraan hubungan. Pembagian satu set ke banyak kelompok berdasarkan pada relasi ekivalensi disebut partisi.
Disjoint Set merupakan 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 minimum spanning tree of a graph.

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 milik suatu set

• union (x, y), Ini membuat set baru yang mengandung elemen set x dan y dan kemudian menghapus set individu x dan y.

Union Operation
Union Operation adalah untuk membuat tree yang lebih kecil menjadi bagian dari tree yang lebih besar. Operasi gabungan juga dapat dilakukan berdasarkan ukuran.

Union berdasarkan ukuran (atau berat) adalah prosedur membuat tree yang lebih kecil menjadi subtree dari tree yang lebih besar berdasarkan ukuran (atau berat).

Path Compression

Path Compression adalah teknik yang digunakan untuk meningkatkan efisiensi operasi find (untuk meningkatkan kinerja operasi find, setiap node harus memiliki pointer langsung ke root).

Algoritma bekerja dengan memeriksa apakah node sudah di-root, maka tidak perlu dilakukan. Jika tidak, pointer harus diperbarui untuk menunjuk ke root.

Graph

Graph adalah struktur data abstrak yang digunakan untuk mengimplementasikan konsep matematika Graph . Pada dasarnya, Graph adalah kumpulan node (juga disebut node ) dan edge yang menghubungkan node-node ini.

Grafik dapat membantu kami mengubah data yang terkait satu sama lain. Seperti, Family Tree, Obrolan Obrolan Game, dll.

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:

1.  Undirected Graph (Grafik Tidak Terarah)
     Undirected Graph adalah grafik tanpa penunjuk arah di setiap edgenya.
Contoh:


2.  Directed Graph (Grafik Terarah)

     Semtara Directed Graph adalah grafik dengan penunjuk arah di setiap edgenya.
Contoh:

Minimum Spanning Tree

Minimum spanning tree (MST) atau minimum spanning tree adalah subset dari edge-edge dari graf tak-berbobot edge-terhubung yang terhubung, yang menghubungkan semua node secara bersamaan, tanpa siklus apa pun dan dengan total berat edge minimum yang mungkin. Artinya, itu adalah pohon spanning yang jumlah bobot edge sekecil mungkin. Secara umum, grafik tanpa arah berbobot edge (tidak harus terhubung) memiliki hutan spanning minimum, yang merupakan gabungan dari pohon spanning minimum untuk komponen yang terhubung.

Berdasarkan caranya Minimum spanning tree (MST) terdapat 3 cara yaitu:

• Algoritma Prim:

1. Buat array dengan nama adalah T.

2. Pilih titik awal.

3. Setiap kali setiap titik menunjuk, ujung yang terhubung akan ditandatangani sebagai aktif.

4. Bandingkan semua nilai edge aktif, temukan angka terkecil.

5. Tambahkan node dengan edge aktif terkecil ke T.

6. Lakukan langkah 3 hingga 5 saat node dalam T lebih sedikit dari total node yang ada.

• Algoritma Kruskal:

1. Buat array dengan nama adalah T.

2. Urutkan semua edge menggunakan heap (antrian prioritas).

3. Ambil nilai edge paling minimum.

4. Jika ada loop, lanjutkan ke edge berikutnya.

5. Lain menambahkan edge ke T.

6. Ulangi langkah 3 hingga 5 hingga semua titik dikunjungi.

Algoritma Dijkstra:

1. Pilih node sumber (node awal).

2. Tentukan N sebagai set kosong.

3. Beri label node awal dengan 0, dan masukkan ke dalam N.

4. Ulangi langkah 5 hingga 7 hingga node tujuan berada di N atau tidak ada mode yang berlabel          simpul di N.

5. Pertimbangkan setiap node yang tidak ada di N dan terhubung dengan ujung dari node yang          baru dimasukkan.

6.

    a) Jika node yang tidak ada dalam N tidak memiliki label maka SET label dari node = label                      dari node yang baru dimasukkan + panjang edge .

    b) Jika node yang tidak dalam N sudah diberi label, maka SET label baru = minimum (label titik            baru dimasukkan + panjang edge , label lama).

7. Pilih satu node , bukan di N yang memiliki label terkecil yang ditugaskan padanya, dan tambahkan ke N.