1 of 40

Breadth/Depth First Search (BFS/DFS)�Pertemuan 9

1

2 of 40

Traversal Graf

  • Algoritma traversal graf: mengunjungi simpul dengan cara yang sistematik
    • Pencarian melebar (breadth first search/BFS)
    • Pencarian mendalam (depth first search/DFS)
    • Asumsi: graf terhubung
  • Graf: representasi persoalan

🡺 Traversal graf: pencarian solusi

2

social graph

http://www.oreilly.de/catalog/9780596518172/toc.html

Web page network

3 of 40

Algoritma Pencarian Solusi

  • Tanpa informasi (uninformed/blind search)
    • Tidak ada informasi tambahan
    • Contoh: DFS, BFS, Depth Limited Search, Iterative Deepening Search, Uniform Cost Search

​

  • Dengan informasi (informed Search)
    • Pencarian berbasis heuristik
    • Mengetahui non-goal state “lebih menjanjikan” daripada yang lain
    • Contoh: Best First Search, A*

3

4 of 40

Representasi Graf dalam Proses Pencarian

Dalam proses pencarian solusi, terdapat dua pendekatan:

​

  1. Graf statis: graf yang sudah terbentuk sebelum proses pencarian dilakukan

- graf direpresentasikan sebagai struktur data

​

  1. Graf dinamis: graf yang terbentuk saat proses pencarian dilakukan

- graf tidak tersedia sebelum pencarian, graf dibangun selama pencarian solusi

4

5 of 40

Graf Statis

5

6 of 40

Pencarian Melebar (BFS)

  • Traversal dimulai dari simpul v.
  • Algoritma:

1. Kunjungi simpul v

2. Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu.

3. Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya.

6

1

2

3

4

5

6

7

8

7 of 40

BFS: Struktur Data

  1. Matriks ketetanggaan A = [aij] yang berukuran nxn, � aij= 1, jika simpul i dan simpul j bertetangga,

aij= 0, jika simpul i dan simpul j tidak bertetangga.

​

2. Antrian q untuk menyimpan simpul yang telah dikunjungi.

​

3. Tabel Boolean, diberi nama “dikunjungi”

dikunjungi : array[l..n] of boolean

dikunjungi[i] = true jika simpul i sudah dikunjungi

dikunjungi[i] = false jika simpul i belum dikunjungi

7

8 of 40

8

9 of 40

BFS: Ilustrasi

9

1

2

3

4

5

6

7

8

Iterasi

V

Q

dikunjungi

1

2

3

4

5

6

7

8

Inisialisasi

1

{1}

T

F

F

F

F

F

F

F

Iterasi 1

1

{2,3}

T

T

T

F

F

F

F

F

Iterasi 2

2

{3,4,5}

T

T

T

T

T

F

F

F

Iterasi 3

3

{4,5,6,7}

T

T

T

T

T

T

T

F

Iterasi 4

4

{5,6,7,8}

T

T

T

T

T

T

T

T

Iterasi 5

5

{6,7,8}

T

T

T

T

T

T

T

T

Iterasi 6

6

{7,8}

T

T

T

T

T

T

T

T

Iterasi 7

7

{8}

T

T

T

T

T

T

T

T

Iterasi 8

8

{}

T

T

T

T

T

T

T

T

Urutan simpul2 yang dikunjungi: 1, 2, 3, 4, 5, 6, 7, 8

10 of 40

10

BFS: Latihan

Iterasi

V

Q

​

dikunjungi

S

A

B

C

D

E

F

G

H

Inisialisasi

S

{S}

T

​

F

F

F

F

F

F

F

F

Iterasi 1

S

{A,F}

T

T

F

F

F

F

T

F

F

Iterasi ...

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

11 of 40

Pencarian Mendalam (DFS)

  • Traversal dimulai dari simpul v.

​

  • Algoritma:
  • Kunjungi simpul v
  • Kunjungi simpul w yang bertetangga dengan simpul v.
  • Ulangi DFS mulai dari simpul w.
  • Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum dikunjungi.
  • Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi.

​

11

1

2

3

4

5

6

7

8

12 of 40

DFS

12

13 of 40

DFS: Ilustrasi 1

  • DFS(1): v=1; dikunjungi[1]=true; DFS(2)
    • DFS(2): v=2; dikunjungi[2]=true; DFS(4)
      • DFS(4): v=4; dikunjungi[4]=true; DFS(8)
        • DFS(8): v=8; dikunjungi[8]=true;

DFS(8): DFS(4)

DFS(4): DFS(2)

DFS(2): DFS(5)

      • DFS(5): v=5; dikunjungi[5]=true

DFS(5): DFS(2)

DFS(2): DFS(1)

DFS(1): DFS(3)

    • DFS(3): v=3; dikunjungi[3]=true; DFS(6)
      • DFS(6): v=6; dikunjungi[6]=true
      • DFS(7): v=7; dikunjungi[7]=true

13

1

2

3

4

5

6

7

8

14 of 40

DFS: Ilustrasi 2

  • Tentukan urutannya!

14

1

2

3

4

5

6

7

8

15 of 40

DFS: Ilustrasi 2

  • DFS(1): v=1; dikunjungi[1]=true; DFS(2)
    • DFS(2): v=2; dikunjungi[2]=true; DFS(4)
      • DFS(4): v=4; dikunjungi[4]=true; DFS(8)
        • DFS(8): v=8; dikunjungi[8]=true; DFS(5)
          • DFS(5): v=5; dikunjungi[5]=true
          • DFS(6): v=6; dikunjungi[6]=true; DFS(3)
            • DFS(3): v=3; dikunjungi[3]=true; DFS(7)
              • DFS(7): v=7; dikunjungi[7]=true

15

1

2

3

4

5

6

7

8

Urutan simpul2 yang dikunjungi: 1, 2, 4, 8, 5, 6, 3, 7

16 of 40

DFS: Ilustrasi 3

  • Tentukan urutannya!

16

1

2

3

4

5

6

7

8

17 of 40

DFS: Ilustrasi 3

  • DFS(1): v=1; dikunjungi[1]=true; DFS(2)
    • DFS(2): v=2; dikunjungi[2]=true; DFS(3)
      • DFS(3): v=3; dikunjungi[3]=true; DFS(6)
        • DFS(6): v=6; dikunjungi[6]=true; DFS(8)
          • DFS(8): v=8; dikunjungi[8]=true; DFS(4)
            • DFS(4): v=4; dikunjungi[4]=true;

DFS(8): DFS(5)

            • DFS(5): v=5; dikunjungi[5]=true

DFS(8): DFS(7)

            • DFS(7): v=7; dikunjungi[7]=true

17

1

2

3

4

5

6

7

8

Urutan simpul2 yang dikunjungi: 1, 2, 3, 6, 8, 4, 5, 7

18 of 40

Latihan

18

19 of 40

19

20 of 40

20

21 of 40

Contoh Graf Berarah

  • Khusus untuk graf berarah, beberapa simpul mungkin tidak dapat dicapai dari simpul awal. Coba dengan simpul yang belum dikunjungi sebagai simpul awal.

​

  • DFS (1): 1-2-4-3-5-6-7
  • BFS (1): 1-2-4-3-5-7-6

21

1

2

3

4

5

6

7

22 of 40

Contoh Lain

  • Bagaimana penelusuran graf dengan BFS?

​

  • Bagaimana Penelusuran graf dengan DFS

22

23 of 40

23

Penerapan BFS dan DFS: Citation Map

24 of 40

Citation Map:

24

Sumber: Teufel (1999), Argumentative Zoning

25 of 40

25

Penerapan BFS dan DFS: Web Spider

query

26 of 40

Penerapan BFS dan DFS: Web Spider

  • Secara periodik, web spider menjejalahi internet untuk mengunjungi halaman-halaman web

​

26

http://www.ibm.com/developerworks/web/library/wa-lucene2/

Arsitektur umum mesin pencari

27 of 40

Web Spider: Penjelajahan Web

  • Halaman web dimodelkan sebagai graf berarah
    • Simpul menyatakan halaman web (web page)
    • Sisi menyatakan link ke halaman web
  • Bagaimana teknik menjelajahi web? Secara DFS atau BFS
  • Dimulai dari web page awal, lalu setiap link ditelusuri secara DFS sampai setiap web page tidak mengandung link.

27

http://introcs.cs.princeton.edu/java/16pagerank/

28 of 40

28

DFS dan BFS untuk penelusuran direktori (folder)

29 of 40

29

Pencarian dokumen di dalam direktori (folder) secara BFS

30 of 40

30

Pencarian dokumen di dalam direktori (folder) secara DFS

31 of 40

Pencarian Rute (Route Finding/Path Finding)

31

32 of 40

32

33 of 40

Path Finding BFS Vs DFS

33

34 of 40

Path Finding dengan BFS dan DFS: Latihan

34

35 of 40

Graf Dinamis

35

36 of 40

36

37 of 40

37

38 of 40

38

Biasanya Kompleksitas dari BFS dan DFS adalah O(bd)

39 of 40

39

40 of 40

40

--- Berlanjut Ke Mata Kuliah AI ---