Bfs Dan Dfs
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Bfs Dan Dfs as PDF for free.
More details
- Words: 329
- Pages: 2
******************************************************************************* const N = 100; // Besarnya labirin N*N type rec = record x, y : integer; step : longint; end; var grid : array[1..N,1..N] of boolean; // Labirinnya, true jika bisa dilewati, false jika tidak Q : array[1..N*N] of rec; // Queue utk menyimpan langkah langkah1, langkah2 : longint; function bfs(xawal, yawal : integer):longint; // Fungsi bfs mengembalikan nilai langkah minimal var ix, iy : integer; head, tail : integer; istep : longint; begin head := 0; tail := 1; Q[tail].x := xawal; Q[tail].y := yawal; Q[tail].step := 0; grid[xawal,yawal] := false; while (head < tail) do begin inc(head); ix := Q[head].x; iy := Q[head].y; istep := Q[head].tail; if ((ix = xakhir) and (iy = yakhir)) then bfs := istep; // Kalau udah bisa keluar, maka keluar if (grid[ix+1,iy]) then // Cek bisa ke bawah? begin inc(tail);# Q[tail].x := ix+1; Q[tail].y := iy; Q[tail].step := istep+1; grid[ix+1,iy] := false; end; if (grid[ix-1,iy]) then // Cek bisa ke atas? begin inc(tail); Q[tail].x := ix-1; Q[tail].y := iy; Q[tail].step := istep+1; grid[ix-1,iy] := false; end; if (grid[ix,iy+1]) then // Cek bisa ke kanan? begin inc(tail); Q[tail].x := ix; Q[tail].y := iy+1; Q[tail].step := istep+1; grid[ix,iy+1] := false; end;
if (grid[ix,iy-1]) then begin inc(tail); Q[tail].x := ix; Q[tail].y := iy-1; Q[tail].step := istep+1; grid[ix,iy-1] := false; end; end; end;
// Cek bisa ke kiri?
procedure dfs(i,j : integer; langkah : longint); begin grid[i,j] := false; if ((i = xakhir) and (j = yakhir)) then langkah2 := langkah; // Klo uda nyampe, keluar else begin if (grid[i+1,j]) then dfs(i+1,j,langkah+1); // Bisa ke bawah? if (grid[i,j+1]) then dfs(i,j+1,langkah+1); // Bisa ke kanan? if (grid[i-1,j]) then dfs(i-1,j,langkah+1); // Bisa ke atas? if (grid[i,j-1]) then dfs(i,j-1,langkah+1); // Bisa ke kiri? end; end; begin // Mulai baca data labirin... // Baca xawal, yawal utk posisi mulainya // Baca xakhir, yakhir utk posisi akhirnya langkah1 := bfs(xawal,yawal); // Memanggil fungsi bfs dfs(xawal,yawal,0); // Memanggil procedure dfs // Langkah minimal yang didpt dr dfs dimasukkan ke langkah2 end.#
if (grid[ix,iy-1]) then begin inc(tail); Q[tail].x := ix; Q[tail].y := iy-1; Q[tail].step := istep+1; grid[ix,iy-1] := false; end; end; end;
// Cek bisa ke kiri?
procedure dfs(i,j : integer; langkah : longint); begin grid[i,j] := false; if ((i = xakhir) and (j = yakhir)) then langkah2 := langkah; // Klo uda nyampe, keluar else begin if (grid[i+1,j]) then dfs(i+1,j,langkah+1); // Bisa ke bawah? if (grid[i,j+1]) then dfs(i,j+1,langkah+1); // Bisa ke kanan? if (grid[i-1,j]) then dfs(i-1,j,langkah+1); // Bisa ke atas? if (grid[i,j-1]) then dfs(i,j-1,langkah+1); // Bisa ke kiri? end; end; begin // Mulai baca data labirin... // Baca xawal, yawal utk posisi mulainya // Baca xakhir, yakhir utk posisi akhirnya langkah1 := bfs(xawal,yawal); // Memanggil fungsi bfs dfs(xawal,yawal,0); // Memanggil procedure dfs // Langkah minimal yang didpt dr dfs dimasukkan ke langkah2 end.#
