Set
adalah kumpulan object.
- Set A adalah subset dari set B jika semua elemen A terdapat di dalam set B.
- Union adalah gabungan dari 2 set.
- Disjoint adalah gabungan dari 2 set dimana tidak ada elemen yang sama dari kedua set tersebut.
- Partisi set adalah kumpulan set yang mempunyai syarat :
1. 2 set haruslah saling disjoint
2. Union dari semua partisi akan menghasilkan set awal
• Disjoint Set
adalah struktur data yang menyimpan kumpulan partisi set dimana kumpulan partisi ini saling disjoint
- Disjoint Set tidaklah sama dengan Set.
- Dikenal juga dengan sebutan Union Find.
- Biasa digunakan untuk mencari Minimum Spanning Tree dari suatu Graph.
- Operasi yang ada antara lain :
1. makeSet(x) = membuat set baru berisi elemen x
2. findSet(x) = mengembalikan set yang mempunyai elemen x
3. union(x,y) = menggabungkan set x & y kemudian menghapus set asli x & y.
• Path Compression
adalah suatu teknik yang digunakan untuk meningkatkan efisiensi dari find operation. Cara yang bisa kita lakukan adalah semua node yang ada harus mempunyai direct pointer ke root node.
• Graphs
adalah abstract data structure yang digunakan untuk mengimplementasikan mathematical concepts dari graph. Juga bisa dikatakan sebagai kumpulan vertices (nodes) dan edges (penghubung antar vertex).
- Biasa digunakan untuk mentransformasikan data yang berkaitan satu sama lain. Contohnya : maps, family tree, games conversation chit - chat.
- Graph terbagi menjadi 2 yaitu directed graph dan undirected graph.
1. Directed Graph
disebut sebagai directed graph karena edges graph ini memiliki arah. Dalam directed graph kita juga mengenal konsep in degree dan out degree.
In degree adalah jumlah edges yang masuk / menunjuk vertex tersebut.
Out degree adalah jumlah edges yang keluar dari vertex tersebut.
2. Undirected Graph
disebut demikian karena edges graph ini tidak memiliki arah. Jika kita mempunyai edge yang terhubung dari A ke B maka kita bisa simpulkan bahwa terdapat hubungan dari A ke B maupun dari B ke A.
Connection dari suatu graph ini bisa direpresentasikan dengan adjacency matrix. Adjacency Matrix ini merepresentasikan jumlah in degree dan out degree dari semua vertex yang ada di dalam suatu graph.
• Minimum Spanning Tree
adalah suatu metode yang bisa digunakan untuk mendapatkan tree dengan cost seminimum mungkin. Ada 2 algoritma yang biasa digunakan dalam konsep MST ini yaitu Prim dan Kruskal. Kedua metode ini menghasilkan MST dengan cost yang sama namun tidak bisa dipungkiri bahwa hasil graph yang dihasilkan dapat berbeda.
Prim = kita mengambil satu edges secara acak lalu kita akan melihat edges yang aktif (yaitu edges yang berkaitan dengan dua vertex awal kita). Kita akan terus mengambil edges yang memiliki cost minimum dan mengulangi cara ini sampai semua vertex terhubung.
Kruskal = kita melakukan sorting edges dan mengkaitakan satu edges dengan yang lain asalkan tidak terbentuk cycle diantara edges ini.
Contoh case MST :
Graph seperti contoh di atas dapat kita sederhanakan menjadi :
• Shortest Path
adalah metode yang dapat kita gunakan untuk mendapatkan jarak minimum dari suatu titik pada graph ke titik yang lain. Metode yang akan kita gunakan adalah metode Dijkstra.
Formula Relaksasi :
if(d(U) + c(U,V) < d(V))
d(V) = d(U) + c(U,V) ;
Cara kerja metode ini adalah kita mengambil titik awal. Misalkan kita sebut titik awal ini adalah A. Setelah ini maka kita perlu melihat vertices yang berkaitan dengan A, misalkan terdapat dua vertices yaitu B dan C. Jika vertices B atau C mempunyai cost yang lebih kecil dari cost A ke B atau A ke C maka kita perlu melakukan relaksasi (update cost vertex). Hal ini kita lakukan sampai semua vertex sudah kita visit. Vertex yang sudah tervisit tidak perlu kita kunjungi lagi.
adalah kumpulan object.
- Set A adalah subset dari set B jika semua elemen A terdapat di dalam set B.
- Union adalah gabungan dari 2 set.
- Disjoint adalah gabungan dari 2 set dimana tidak ada elemen yang sama dari kedua set tersebut.
- Partisi set adalah kumpulan set yang mempunyai syarat :
1. 2 set haruslah saling disjoint
2. Union dari semua partisi akan menghasilkan set awal
• Disjoint Set
adalah struktur data yang menyimpan kumpulan partisi set dimana kumpulan partisi ini saling disjoint
- Disjoint Set tidaklah sama dengan Set.
- Dikenal juga dengan sebutan Union Find.
- Biasa digunakan untuk mencari Minimum Spanning Tree dari suatu Graph.
- Operasi yang ada antara lain :
1. makeSet(x) = membuat set baru berisi elemen x
2. findSet(x) = mengembalikan set yang mempunyai elemen x
3. union(x,y) = menggabungkan set x & y kemudian menghapus set asli x & y.
• Path Compression
adalah suatu teknik yang digunakan untuk meningkatkan efisiensi dari find operation. Cara yang bisa kita lakukan adalah semua node yang ada harus mempunyai direct pointer ke root node.
• Graphs
adalah abstract data structure yang digunakan untuk mengimplementasikan mathematical concepts dari graph. Juga bisa dikatakan sebagai kumpulan vertices (nodes) dan edges (penghubung antar vertex).
- Biasa digunakan untuk mentransformasikan data yang berkaitan satu sama lain. Contohnya : maps, family tree, games conversation chit - chat.
- Graph terbagi menjadi 2 yaitu directed graph dan undirected graph.
1. Directed Graph
disebut sebagai directed graph karena edges graph ini memiliki arah. Dalam directed graph kita juga mengenal konsep in degree dan out degree.
In degree adalah jumlah edges yang masuk / menunjuk vertex tersebut.
Out degree adalah jumlah edges yang keluar dari vertex tersebut.
2. Undirected Graph
disebut demikian karena edges graph ini tidak memiliki arah. Jika kita mempunyai edge yang terhubung dari A ke B maka kita bisa simpulkan bahwa terdapat hubungan dari A ke B maupun dari B ke A.
Connection dari suatu graph ini bisa direpresentasikan dengan adjacency matrix. Adjacency Matrix ini merepresentasikan jumlah in degree dan out degree dari semua vertex yang ada di dalam suatu graph.
• Minimum Spanning Tree
adalah suatu metode yang bisa digunakan untuk mendapatkan tree dengan cost seminimum mungkin. Ada 2 algoritma yang biasa digunakan dalam konsep MST ini yaitu Prim dan Kruskal. Kedua metode ini menghasilkan MST dengan cost yang sama namun tidak bisa dipungkiri bahwa hasil graph yang dihasilkan dapat berbeda.
Prim = kita mengambil satu edges secara acak lalu kita akan melihat edges yang aktif (yaitu edges yang berkaitan dengan dua vertex awal kita). Kita akan terus mengambil edges yang memiliki cost minimum dan mengulangi cara ini sampai semua vertex terhubung.
Kruskal = kita melakukan sorting edges dan mengkaitakan satu edges dengan yang lain asalkan tidak terbentuk cycle diantara edges ini.
Contoh case MST :
Graph seperti contoh di atas dapat kita sederhanakan menjadi :
• Shortest Path
adalah metode yang dapat kita gunakan untuk mendapatkan jarak minimum dari suatu titik pada graph ke titik yang lain. Metode yang akan kita gunakan adalah metode Dijkstra.
Formula Relaksasi :
if(d(U) + c(U,V) < d(V))
d(V) = d(U) + c(U,V) ;
Cara kerja metode ini adalah kita mengambil titik awal. Misalkan kita sebut titik awal ini adalah A. Setelah ini maka kita perlu melihat vertices yang berkaitan dengan A, misalkan terdapat dua vertices yaitu B dan C. Jika vertices B atau C mempunyai cost yang lebih kecil dari cost A ke B atau A ke C maka kita perlu melakukan relaksasi (update cost vertex). Hal ini kita lakukan sampai semua vertex sudah kita visit. Vertex yang sudah tervisit tidak perlu kita kunjungi lagi.
Comments
Post a Comment