Praktikum Searching

Kegiatan Belajar 1: Pengantar Searching

A. Definisi Searching

1. Konsep Searching

• Searching: operasi dasar yang diterapkan pada graph dengan cara mencari vertex yang sesuai dengan vertex yang dicari (Lafore, 2003).
• Key (kata kunci): vertex yang dicari, menjadi petunjuk utama dalam pencarian.
• Contoh penerapan searching dalam teknologi:
  • Mesin pencarian (Google) — mencari informasi di internet.
  • Pencarian kontak telepon — mengetik huruf awal nama untuk menemukan kontak.
  • Ctrl+F — mencari kata pada dokumen/file di desktop.
  • Peta digital — mencari lokasi dan mendapatkan arah, jarak, estimasi waktu.

2. Algoritma Searching

• Terdapat dua algoritma utama dalam searching:
  • Depth First Search (DFS) — pencarian ke dalam (vertex terdalam).
  • Breadth First Search (BFS) — pencarian per level.

B. Depth First Search (DFS)

1. Konsep DFS

• DFS menggunakan stack sebagai tempat menyimpan vertex yang dikunjungi dan akan dikunjungi (Lafore, 2003).
• DFS menelusuri graph dengan cara menuju vertex terdalam terlebih dahulu.

2. Tiga Rule Algoritma DFS

• Rule 1: Jika memungkinkan, kunjungi vertex yang belum dikunjungi dan berdekatan, tandai dan simpan pada stack.
• Rule 2: Jika rule 1 tidak bisa, keluarkan vertex dari stack (Pop).
• Rule 3: Jika rule 1 dan 2 tidak bisa → pencarian selesai.

3. Contoh Tahapan DFS pada Graph 9 Vertex (A–I)

• Visit A → Stack: A
• Visit B → Stack: AB
• Visit F → Stack: ABF
• Visit H → Stack: ABFH (vertex terdalam pada rangkaian B)
• Pop H, Pop F, Pop B → Stack: A (rangkaian B habis)
• Visit C → Stack: AC; Pop C → Stack: A (C tidak punya rangkaian)
• Visit D → Stack: AD
• Visit G → Stack: ADG
• Visit I → Stack: ADGI (vertex terdalam pada rangkaian D)
• Pop I, Pop G, Pop D → Stack: A (rangkaian D habis)
• Visit E → Stack: AE
• Pop E, Pop A → Stack: kosong
• Done — seluruh vertex telah dikunjungi.

C. Breadth First Search (BFS)

1. Konsep BFS

• BFS menggunakan queue (antrean) sebagai tempat menyimpan vertex.
• BFS menelusuri graph per level, dimulai dari root.

2. Tiga Aturan Algoritma BFS

• Aturan 1: Kunjungi vertex yang belum pernah dikunjungi, tandai dan masukkan ke antrean.
• Aturan 2: Jika tidak ada vertex baru, hapus vertex terdepan dari antrean (Remove), jadikan vertex saat ini.
• Aturan 3: Jika antrean kosong → kunjungan selesai.

3. Contoh Tahapan BFS pada Tree 9 Vertex (A–I)

• Visit A → Queue: (kosong, root)
• Visit B → Queue: B; Visit C → Queue: BC; Visit D → Queue: BCD; Visit E → Queue: BCDE
• Remove B → Queue: CDE; Visit F → Queue: CDEF
• Remove C → Queue: DEF (C tidak punya child)
• Remove D → Queue: EF; Visit G → Queue: EFG
• Remove E → Queue: FG
• Remove F → Queue: G; Visit H → Queue: GH
• Remove G → Queue: H; Visit I → Queue: HI
• Remove H → Queue: I; Remove I → Queue: kosong
• Done — seluruh vertex telah dikunjungi.

---

Kegiatan Belajar 2: Praktikum Depth-First Search

A. Praktikum DFS

1. Struktur Coding DFS

• Terdiri dari 46 baris, class Graph, dengan method: main, Graph, addEdge, DFSUtil, DFS.
• Library: java.io.* dan java.util.*.

2. Komponen Utama Coding

• Variabel: V (jumlah vertex, private), adj[] (LinkedList adjacency, private).
• Graph(int v): konstruktor — membuat graph dengan v vertex, inisialisasi LinkedList untuk setiap vertex.
• addEdge(int v, int w): menambahkan edge dari vertex v ke vertex w.
• DFSUtil(int v, boolean visited[]): rekursif — tandai vertex v sebagai visited, cetak v, kunjungi semua vertex adjacent yang belum dikunjungi.
• DFS(int v): entry point — buat array boolean visited[], panggil DFSUtil.

3. Contoh Coding DFS

import java.io.*;
import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFSUtil(v, visited);
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        System.out.println("DFS dengan vertex awal 2");
        g.DFS(2);
    }
}

4. Penjelasan Kunci

• visited[v] = true → tandai vertex v telah dikunjungi.
• adj[v].listIterator() → daftar vertex adjacent dengan v.
• While loop mengunjungi semua adjacent; jika belum dikunjungi, panggil DFSUtil rekursif.
• Output: 2 0 1 3.

B. Ilustrasi Coding DFS ke Graph

1. Graph Awal

• 4 vertex (0, 1, 2, 3) dengan edge: 0→1, 0→2, 1→2, 2→0, 2→3, 3→3.

2. Traversal DFS dari Vertex 2

• Vertex 2 → 0 → 1 → 3. Urutan: 2, 0, 1, 3.

---

Kegiatan Belajar 3: Praktikum Breadth-First Search

A. Praktikum BFS

1. Struktur Coding BFS

• Terdiri dari 52 baris, class Graph, dengan method: main, Graph, addEdge, BFS.
• Komponen utama sama dengan DFS, kecuali method BFS menggunakan queue (bukan rekursif stack).

2. Komponen Utama Coding BFS

• BFS(int s): entry point — buat array visited[] dan queue (LinkedList).
  • Tandai vertex awal s sebagai visited, masukkan ke queue.
  • Perulangan while selama queue tidak kosong:
    • Ambil dan hapus vertex terdepan queue (queue.poll()), cetak.
    • Untuk setiap vertex adjacent yang belum dikunjungi: tandai visited, masukkan ke queue.

3. Contoh Coding BFS

import java.io.*;
import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<Integer>();
        visited[s] = true;
        queue.add(s);
        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        System.out.println("BFS dengan vertex awal 2");
        g.BFS(2);
    }
}

4. Penjelasan Kunci BFS

• queue.poll() → mengambil dan menghapus elemen terdepan (head) dari queue.
• queue.add(n) → menambahkan vertex n ke belakang antrean.
• Perulangan while berlanjut selama queue.size() != 0.
• Output: 2 0 3 1 (traversal BFS dari vertex 2 — berdasarkan level).

B. Ilustrasi Coding BFS ke Graph

1. Graph Awal

• Sama dengan DFS: 4 vertex (0, 1, 2, 3) dengan edge yang sama.

2. Traversal BFS dari Vertex 2

• Vertex 2 → 0, 3 (adjacent) → 1. Urutan: 2, 0, 3, 1.

3. Perbedaan DFS vs BFS

• DFS: stack (rekursif), traversal ke vertex terdalam dulu. Output: 2 0 1 3.
• BFS: queue (antrean), traversal per level. Output: 2 0 3 1.