Algoritma Depth First Search (BFS) dengan Source Code Python

Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya. Pencarian rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari tujuan atau sebagai simpul yang dicari.

Dalam algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal).

Pada Postingan kali ini saya akan membagikan source code Algoritma DFS dengan menggunakan bahasa pemrograman Python, Berikut adalah source codenya :

#contoh peta 
Peta =  {'A':set(['B','H']),
         'B':set(['A','C','H']),
         'C':set(['B','D','E']),
         'D':set(['C','E','F','G','H']),

Algoritma Breadth First Search (BFS) dengan Source Code Python

Breadth First Search (BFS)

Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.

Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.

Pada Postingan kali ini saya akan membagikan source code Algoritma BFS dengan menggunakan bahasa pemrograman Python, Berikut adalah source codenya :

#contoh Peta

Peta =  {'A':set(['B','H']),

         'B':set(['A','C','H']),

         'C':set(['B','D','E']),

Membuat Meja Menggunakan OpenGL

Pada kesempatan ini saya akan membagikan source code cara membuat meja dari OpenGL

Aplikasi yang digunakan yaitu Basic 4GL.

Berikut code yang telah dibuat: 

'var posisi kamera

Dim cx# = 0

Dim cy# = 3

Dim cz# = 20

'var posisi titik pandang

Dim vx# = 0

Dim vy# = 0

Dim vz# = 0

'var perpindahan

Dim move# = 0.01

'var texture

Dim kayu

kayu = loadmipmaptexture("kayu.jpg")

glEnable (GL_TEXTURE_2D)

Algoritma Pembuat Lingkaran

Untuk membuat Algoritma Pembuat lingkaran dalam pemrogaman bahasa java dibutuhkan langkah-langkah sebagai berikut ini ;

1. Menentukan xc, yc, dan r (jari-jari)

2. Melakukan pengubahan posisi dengan
   - p = 1 - r
     x = 0
     y = r

3. Pengulangan

      Perulangan akan berhenti jika x > y

       - Kondisi
         Jika p < 0 maka, x + 1, y tetap dan p berubah menjadi p = p + (2* x) + 1
         Jika tidak maka, x + 1, y - 1 dan p berubah menjadi p + *(x - y)) + 1 

Contoh code :

//Nama File : Lingkaran.java

Algoritma Bresenham

Algoritma garis Bresenhem adalah algoritma konversi penambahan nilai integer.

Langkah-langkah untuk membentuk garis menurut algoritma ini adalah :

1. Menentukan titik awal & akhir
2. Pengubahan posisi
3. Perulangan

1. Menentukan titik awal & akhir
   - Titik awal (x1,y1)
   - Titik akhir (x2,y2)

2. Pengubahan posisi

    - Tentukan dx & dy
      dx = x2 - x1
      dy = y2 - y1

    - Tentukan p awal

      p = (2*dy)-dx

 3. Perulangan

    - Kondisi

      Jika p > 0 maka, x = x + 1, y = y, dan nilai p berubah dengan p = p + (2*dy)

      Jika tidak, maka x = x + 1, y = y +1 dan nilai p berubah dengan p p + 2(dy - dx)

Contoh code:

//Nama File : Bresenham.java

Algoritma Garis DDA

Apa itu algoritma DDA? DDA (Digital Differential Analyzer) adalah algoritma pembentukan garis berdasarkan perhitungan Dx dan Dy, Langkah-langkah pembuatan algoritma DDA yaitu:

1. Menentukan titik awal & akhir
2. Pengubahan posisi (menggunakan steps)
3. Perulangan

1. Menentukan titik awal & akhir
   - Titik awal (x1,y1)
   - Titik akhir (x2,y2)

2. Pengubahan posisi (step)

    - Tentukan dx & dy
      dx = x2 - x1
      dy = y2 - y1

   - Menentukan steps
     Jika dx > dy, maka steps = dx, dan jika dy => dx maka steps = dy

   - Menentukan perubahan nilai
      x_inc  = dx / steps
      y_inc = dy / steps

3. Perulangan
 
   - Perulangan akan berhenti jika perulangan sampai ke titik akhir
 
   - Rumus perulangan
     x = x + x_inc
     y = y + y_inc


Contoh code:

// Nama File : DDA.java