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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: