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.

Heaps & Tries

Heaps & Tries 

Heap
Heap adalah struktur data berbasis pohon biner lengkap yang memenuhi properti heap. Heap biasanya diimplementasikan dalam sebuah array. Elemen disimpan secara berurutan dari indeks 1 ke N dari atas ke bawah dan dari node kiri ke kanan pohon. Root disimpan dalam indeks adalah 1

Apa jenis-jenis Heap properti?

• Min Heap: Setiap elemen node lebih kecil dari elemen anak-anaknya. Ini menyiratkan bahwa elemen terkecil terletak di akar pohon. Elemen terbesar terletak di suatu tempat di salah satu node daun. Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk mengimplementasikan heap menggunakan array.

Contoh Min Heap:

Aplikasi Heap

Antrian Prioritas

• Algoritma Seleksi (menemukan elemen min / maks, median, elemen kth-terbesar, dll). 
• Algoritma Dijkstra (menemukan jalur terpendek dalam grafik). 
• Algoritma Prim (menemukan pohon rentang minimum).

Implementasi Antrian Prioritas terdiri dari:

• Find-min: Mencari elemen terkecil di heap. int findmin(){return data[1];} 
• Insert (Push): Masukkan elemen baru ke dalam tumpukan. 
• Delete-min (Pop): Menghapus elemen terkecil dari heap.

Insert in Min-Heap

Agar saat melakukan insert element baru, dan tetap menjaga property heap, dilakukan Upheap (memperbaiki property heap tersebut). Uphead adalah membandingkan nilai node saat ini (mulai dengan node yang disisipkan) dengan nilai induknya. Jika nilai node saat ini lebih kecil dari nilai induknya daripada menukar nilainya dan teruskan upheap node induknya. Berhenti jika nilai induknya lebih kecil dari nilai node  saat ini atau node saat ini adalah root (tidak memiliki induk).

Contoh insert:

Insert node (20)

< Insert node (5) >

Deletion in Min-Heap

Penghapusan elemen terkecil yang terletak di root. Root diganti dengan elemen terakhir dari heap. kemudian kurangi jumlah elemen dalam heap. dan gunakan root Downheap (memperbaiki properti heapnya).

Downheap adalah membandingkan nilai node saat ini (mulai dengan root) dengan nilai anak kiri dan kanannya. Tukar node saat ini dengan anak terkecil dan lanjutkan downheaps pada node (anak) itu. Berhenti jika nilai node saat ini lebih kecil dari nilai anak-anaknya atau node saat ini adalah leaf (tidak memiliki anak).

Contoh Deletion:

Delete-min, node (7)

Penggatian root dengna element terakhir, node (28).

• Max Heap: Setiap elemen node lebih besar dari anak-anaknya.Ini menyiratkan bahwa elemen terbesar terletak di akar pohon. Max-heap memiliki prinsip yang sama dengan min-heap dan dapat digunakan untuk membuat antrian prioritas yang perlu menemukan elemen terbesar alih-alih yang terkecil.

Min Max Heap

Konsep Min Max Heap adalah level root akan bernilai minimum, selanjutnya akan bernilai maximum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya. Insertion dan Deletion sama seperti Min Heap atau Max Heap namun, pengecekan kondisi hanya dapat dilakukan di level sesama min atau max.

Contoh:

Tries

Tries (prefix tree) adalah pohon di mana setiap simpul mewakili satu kata atau awalan. Struktur data tree terurut yang digunakan untuk menyimpan array asosiatif (biasanya string) Istilah TRIE berasal dari kata RETRIEVAL karena mencoba dapat menemukan satu kata dalam kamus dengan hanya awalan kata.