Algoritma DFS Pada Array 2 Dimensi [Java]

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;
			}
		}
	}
}

About nugan88
Mencoba untuk selalu menjadi orang yang lebih baik dan lebih maju

Leave a comment