Disjoin Sets & Graph

Disjoint Sets & Graph

Set adalah tipe data abstrak yang dapat menyimpan nilai-nilai tertentu, tanpa urutan tertentu, dan tidak ada nilai berulang.

Disjoint Sets 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).

Setiap pohon adalah satu set terpisah. Jika dua elemen berada di pohon yang sama, maka mereka berada di set disjoint yang sama. Simpul root (atau simpul paling atas) dari setiap pohon disebut representatif dari himpunan. Selalu ada satu perwakilan unik dari setiap set.  Itu merupakan operasi Find, operasi Lalu berikutnya adalah operasi Union. Pertama-tama, Menemukan perwakilan set mereka menggunakan operasi Find, dan akhirnya menempatkan salah satu pohon (mewakili set) di bawah simpul akar dari pohon lain, secara efektif menggabungkan pohon dan set.

Graph

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

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.

2. Graf berarah (directed graph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.

Minimum Spanning Tree
Algoritma Prim:

1. Buat array dengan nama T.
2. Pilih titik awal.
3. Setiap kali setiap titik menunjuk, ujung yang terhubung akan ditandai sebagai aktif.
4. Bandingkan semua nilai tepi aktif, temukan angka terkecil.
5. Tambahkan node dengan tepi aktif terkecil ke T.

6. Lakukan langkah 3 hingga 5 sementara simpul dalam T lebih sedikit dari total simpul yang ada.

Algoritma Kruskal:

1. Buat array dengan nama T.
2. Urutkan semua tepi menggunakan tumpukan (priority queue)
3. Ambil nilai tepi paling minimum
4. Jika ada loop, lanjutkan ke tepi berikutnya
5. Jika tidak, tambahkan tepi ke T

6. Ulangi langkah 3 hingga 5 hingga semua titik dikunjungi

Algoritma Dijkstra:

1. Pilih simpul sumber (simpul awal)
2. Tentukan N sebagai set kosong
3. Beri label simpul awal dengan 0, dan masukkan ke dalam N
4. Ulangi langkah 5 hingga 7 hingga simpul tujuan berada di N atau tidak ada        mode berlabel node di N.
5. Pertimbangkan setiap simpul yang tidak dalam N dan terhubung oleh tepi          dari simpul yang baru dimasukkan.
6. a)Jika node yang tidak dalam N tidak memiliki label maka SET label label =           label dari node yang baru dimasukkan + panjang tepi
    b)Lain jika node yang tidak dalam N sudah diberi label, maka SET label baru         = minimum (label titik baru dimasukkan + panjang tepi, label lama)

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