IF2211 Strategi Algoritmik Tugas Kecil 2
Algoritma Divide and Conquer adalah metode perancangan algoritma dengan mereduksi persoalan menjadi dua upa-persoalan (sub-problem) yang lebih kecil, tetapi selanjutnya hanya memproses satu sub-persoalan saja. Topological sorting secara umum adalah metode yang bertujuan untuk mengurutkan simpul-simpul pada suatu graf dari simpul yang paling penting atau diutamakan sampai simpul yang paling dapat diabaikan atau prioritas terakhir.
- Buatlah suatu Matriks Ordering kosong yang diinisiasi dengan Nil sesuai ukuran matriks yaitu jumlah node x jumlah node (persegi)
- Buatlah suatu array of boolean yang memiliki jumlah elemen sesuai dengan jumlah node pada graf dan diinisiasi dengan nilai False.
- Inisiasi nilai i dan j sebesar nilai maksimal pada ukuran matriks yang ada. Hal ini berguna agar mata kuliah yang memiliki banyak prasyarat akan ditempatkan di akhir.
- Untuk basis yang digunakan, carilah node dimana node belum dikunjungi sama sekali dan bernilai false.
- Apabila ditemukan node yang belum pernah dikunjungi, panggilan fungsi dfs supaya bisa masuk ke dalam bagian rekursif.
- Pada saat masuk, node yang dikunjungi langsung di-set True dan terus menjalankan operasi.
- Pada rekursif kedua, sama dengan langkah 4, hanya yang berbeda, node asal yang ditentukan adalah node yang menembakkan panah ke node yang dituju selanjutnya.
- Ulangi langkah ini terus menerus hingga seluruh node pada 1 operasi dikunjungi.
- Mulailah operasi pengisian Matriks Ordering hingga yang terakhir dimasukkan adalah node yang paling awal menjadi prasyaratnya, kurangi angka i sebanyak 1 agar bisa diisi menaik.
- Setelah selesai, kembalikan nilai j menjadi berkurang satu yang artinya berpindah kolom. Inisiasi nilai i kembali sebesar ukuran jumlah node pada grafik agar bisa melakukan pengisian kedua, dst.
- Langkah 10 berguna untuk memampatkan mata kuliah yang tidak ada kaitannya dapat diambil di semester awal dan mengefisienkan masa kuliah agar tidak lebih dari 8 semester.
- Jalankan program pada CMD atau Windows Powershell dengan file
13519215-main.exe - Jalankan program pada Terminal Ubuntu dengan file
13519215-main.out - Library yang digunakan:
<vector>dan<map>
- Download zip atau clone git ini
- Change directory to test
- Silahkan Ubah
prereq.txtsesuka hati Anda (Jangan lupa diseparasi dengan tanda koma dan tanda titik) - Selanjutnya, masuklah ke dalam folder bin Untuk Pengguna Ubuntu, silahkan masukkan command
./13519215-main.out
Sedangkan untuk Pengguna Windows, silahkan masukkan command
./13519215-main.exe
- Anda akan melihat hasilnya :)
Leonard Matheus - 13519215