Algoritma DFS Pada Array 2 Dimensi [Java]
April 12, 2013 Leave a comment
Algoritma DFS merupakan salah satu algoritma pencarian yang menggunakan stack. Jalur pencarian dilakukan secara mendalam, menelusuri node-node dimulai dari node akar kemudian mengunjungi node anak yang dimasukkan ke dalam sebuah stack. Kemudian kembali lagi ke akar dengan melakukan backtracking sekaligus mengeluarkan node yang telah dikunjungi dari dalam stack, dan berganti ke node akar yang lain. Begitu seterusnya. Keuntungan dari DFS sudah jelas akan menjadikan memori lebih ringan, karena DFS tidak menyimpan node dalam memori setelah melakukan penelusuran, node akan di pop/dikeluarkan dari memori melalui stack. Jika diimplementasikan dalam bahasa pemrograman java kurang lebih seperti ini. (Sekedar sharing, curhat revisi skripsi ^^V)import java.util.Stack; public class dfs { public static void main(String[] args) { int in[][] = { { 1, 2, 2, 4, 5, 6 }, { 1, 8, 9, 7, 3, 3 }, { 4, 5, 6, 7, 8, 9 } }; int baris = in.length; int kolom = in[0].length; System.out.println("baris=" + baris); System.out.println("kolom=" + kolom); int a_baris = 0; int a_kolom = 0; int kol = a_kolom; int bar = a_baris; Stack<Integer> st = new Stack<Integer>(); boolean done = false; while (!done) { // System.out.println(bar + "," + kol); a_baris = bar; a_kolom = kol; int acuan = in[a_baris][a_kolom]; if (acuan != 99) { for (int i = a_baris; i < baris; i++) { for (int j = a_kolom; j < kolom; j++) { st.push(in[i][j]); } for (int p = kolom - 1; p >= a_kolom; p--) { int cek = st.pop(); if (cek == acuan) { System.out.println(i + "," + p); in[i][p] = 99; } } a_kolom = 0; } } else { System.out.println("sudah dibuka"); } for (int ii = 0; ii < baris; ii++) { for (int jj = 0; jj < kolom; jj++) { System.out.print(in[ii][jj] + "\t"); } System.out.println(""); } if (kol == kolom - 1) { bar++; kol = 0; } else { kol++; } if (kol == kolom - 1 && bar == baris - 1) { done = true; } } } }