Menggunakan Struktur Data Graph untuk Memecahkan Masalah Kompleks di Aplikasi Web Anda

1. Pendahuluan

Pernahkah Anda merasa pusing saat membangun fitur di aplikasi web yang melibatkan banyak hubungan kompleks? Misalnya, sistem perizinan yang berlapis, rekomendasi produk berdasarkan preferensi teman, atau optimasi rute navigasi di aplikasi peta? Seringkali, kita mencoba menyelesaikannya dengan struktur data konvensional seperti array atau objek bersarang, yang pada akhirnya membuat kode menjadi rumit, sulit dipelihara, dan tidak efisien.

Di sinilah struktur data graph datang sebagai penyelamat! Graph adalah cara yang sangat ampuh untuk memodelkan dan memecahkan masalah yang melibatkan hubungan antar entitas. Bayangkan sebuah jejaring sosial, peta jalan, atau bahkan struktur dependensi modul di proyek Anda – semuanya bisa direpresentasikan sebagai graph.

Dalam artikel ini, kita akan menyelami dunia graph: apa itu, bagaimana merepresentasikannya dalam kode JavaScript/TypeScript, dan yang terpenting, bagaimana memanfaatkan algoritma graph esensial untuk memecahkan masalah nyata di aplikasi web Anda. Bersiaplah untuk meningkatkan kemampuan problem-solving Anda! 🚀

2. Apa Itu Struktur Data Graph?

Secara sederhana, graph adalah kumpulan dari node (atau vertex) dan edge (atau sisi) yang menghubungkan node-node tersebut.

Node (Vertex): Ini adalah entitas dasar dalam graph. Bayangkan mereka sebagai “titik” atau “objek” dalam sistem Anda. Contoh: pengguna di jejaring sosial, halaman web, kota, atau modul kode.
Edge (Sisi): Ini adalah hubungan atau koneksi antara dua node. Edge bisa memiliki arah dan bobot. Contoh: pertemanan antara dua pengguna, link dari satu halaman ke halaman lain, jalan antara dua kota, atau dependensi antara dua modul.

📌 Analogi Sederhana: Bayangkan graph seperti peta jalan.

Node adalah kota-kota.
Edge adalah jalan yang menghubungkan kota-kota tersebut.
Jika jalan itu satu arah, maka edge-nya directed.
Jika jalan itu memiliki jarak atau waktu tempuh, maka edge-nya weighted.

Jenis-Jenis Graph

Directed Graph (Digraph): Edge memiliki arah. Jika ada edge dari A ke B, itu tidak berarti ada edge dari B ke A. Contoh: link antar halaman web (Anda bisa nge-klik dari halaman A ke B, tapi belum tentu sebaliknya).
Undirected Graph: Edge tidak memiliki arah. Jika ada edge dari A ke B, itu berarti juga ada edge dari B ke A. Contoh: pertemanan di Facebook (jika A berteman dengan B, maka B juga berteman dengan A).
Weighted Graph: Setiap edge memiliki “bobot” atau “nilai”. Bobot ini bisa merepresentasikan jarak, biaya, waktu, atau kekuatan hubungan. Contoh: waktu tempuh antar kota di peta.
Unweighted Graph: Edge tidak memiliki bobot. Semua hubungan dianggap sama.
Cyclic Graph: Graph yang mengandung siklus (Anda bisa memulai dari sebuah node dan kembali ke node yang sama dengan mengikuti edge). Contoh: dependensi modul yang melingkar (modul A butuh B, B butuh C, C butuh A).
Acyclic Graph: Graph yang tidak mengandung siklus. Sering disebut juga Directed Acyclic Graph (DAG) dan sangat penting dalam banyak aplikasi (misalnya, workflow atau build system).

3. Representasi Graph di Kode Anda

Ada dua cara utama untuk merepresentasikan graph dalam struktur data di memori:

a. Adjacency Matrix

Ini adalah matriks N x N (di mana N adalah jumlah node) yang menunjukkan apakah ada edge antara dua node.

matrix[i][j] = 1 (atau true) jika ada edge dari node i ke node j.
matrix[i][j] = 0 (atau false) jika tidak ada.
Untuk graph berbobot, nilai 1 bisa diganti dengan bobot edge.

Kelebihan:

Cepat untuk memeriksa apakah ada edge antara dua node (O(1)).
Mudah diimplementasikan untuk graph kecil.

Kekurangan:

Memakan banyak memori (O(N^2)), terutama untuk graph yang “jarang” (sparse graph, yaitu graph dengan sedikit edge dibandingkan node).
Sulit untuk menambahkan/menghapus node.

b. Adjacency List

Ini adalah representasi yang lebih umum di aplikasi web. Setiap node memiliki daftar node lain yang terhubung dengannya melalui edge. Biasanya diimplementasikan sebagai Map atau Object di JavaScript, di mana kunci adalah nama node dan nilai adalah array/list dari node tetangga.

Kelebihan:

Lebih efisien memori untuk sparse graph (O(N + E), di mana E adalah jumlah edge).
Lebih mudah untuk menambahkan/menghapus edge.
Cepat untuk menemukan semua tetangga dari sebuah node.

Kekurangan:

Memeriksa apakah ada edge antara dua node memerlukan waktu O(derajat node), sedikit lebih lambat dari Adjacency Matrix.

💡 Pilihan Praktis: Untuk sebagian besar aplikasi web, Adjacency List adalah pilihan yang lebih baik karena graph cenderung sparse dan kita seringkali perlu mencari tetangga sebuah node.

Mari kita lihat contoh implementasi Adjacency List dengan TypeScript:

class Graph {
    // Menggunakan Map untuk menyimpan adjacency list
    // Key: Nama node (string)
    // Value: Set dari node tetangga (Set<string>)
    private adjacencyList: Map<string, Set<string>>;

    constructor() {
        this.adjacencyList = new Map<string, Set<string>>();
    }

    /**
     * Menambahkan node baru ke graph.
     * @param node Nama node yang akan ditambahkan.
     */
    addNode(node: string): void {
        if (!this.adjacencyList.has(node)) {
            this.adjacencyList.set(node, new Set<string>());
            console.log(`✅ Node '${node}' ditambahkan.`);
        } else {
            console.log(`⚠️ Node '${node}' sudah ada.`);
        }
    }

    /**
     * Menambahkan edge (hubungan) antara dua node.
     * Untuk undirected graph, tambahkan edge di kedua arah.
     * Untuk directed graph, tambahkan hanya dari node1 ke node2.
     * @param node1 Node awal.
     * @param node2 Node tujuan.
     * @param directed True jika directed graph, false jika undirected (default: false).
     */
    addEdge(node1: string, node2: string, directed: boolean = false): void {
        if (!this.adjacencyList.has(node1) || !this.adjacencyList.has(node2)) {
            console.error(`❌ Tidak dapat menambahkan edge: Salah satu atau kedua node tidak ada.`);
            return;
        }

        this.adjacencyList.get(node1)?.add(node2);
        if (!directed) { // Jika undirected, tambahkan juga edge baliknya
            this.adjacencyList.get(node2)?.add(node1);
        }
        console.log(`✅ Edge ditambahkan antara '${node1}' dan '${node2}' (directed: ${directed}).`);
    }

    /**
     * Mendapatkan tetangga dari sebuah node.
     * @param node Nama node.
     * @returns Set dari node tetangga, atau undefined jika node tidak ada.
     */
    getNeighbors(node: string): Set<string> | undefined {
        return this.adjacencyList.get(node);
    }

    /**
     * Menampilkan graph.
     */
    printGraph(): void {
        console.log("\n--- Graph Representation ---");
        for (const [node, neighbors] of this.adjacencyList.entries()) {
            console.log(`${node} -> ${Array.from(neighbors).join(', ')}`);
        }
        console.log("----------------------------");
    }
}

// Contoh Penggunaan:
const socialNetwork = new Graph();
socialNetwork.addNode("Alice");
socialNetwork.addNode("Bob");
socialNetwork.addNode("Charlie");
socialNetwork.addNode("David");

socialNetwork.addEdge("Alice", "Bob");       // Alice dan Bob berteman (undirected)
socialNetwork.addEdge("Bob", "Charlie");
socialNetwork.addEdge("Charlie", "David");
socialNetwork.addEdge("David", "Alice");

socialNetwork.printGraph();
// Output:
// Alice -> Bob, David
// Bob -> Alice, Charlie
// Charlie -> Bob, David
// David -> Charlie, Alice

// Contoh directed graph (misalnya, A mengikuti B)
const followGraph = new Graph();
followGraph.addNode("User1");
followGraph.addNode("User2");
followGraph.addNode("User3");
followGraph.addEdge("User1", "User2", true); // User1 mengikuti User2
followGraph.addEdge("User2", "User3", true); // User2 mengikuti User3
followGraph.printGraph();
// Output:
// User1 -> User2
// User2 -> User3
// User3 ->

4. Algoritma Graph Esensial dan Aplikasinya

Setelah bisa merepresentasikan graph, selanjutnya adalah bagaimana “menjelajahi” dan “menganalisis” graph tersebut menggunakan algoritma.

a. Traversal: Menjelajahi Graph

Algoritma traversal memungkinkan kita mengunjungi setiap node dalam graph. Dua yang paling dasar adalah Depth-First Search (DFS) dan Breadth-First Search (BFS).

Depth-First Search (DFS)

DFS menjelajahi sejauh mungkin di sepanjang setiap cabang sebelum melakukan backtracking. Mirip seperti menjelajahi labirin, Anda masuk sedalam mungkin ke satu jalur sampai buntu, baru kemudian mundur dan mencoba jalur lain.

🎯 Kapan Digunakan:

Mencari jalur antara dua node.
Mendeteksi siklus dalam graph (penting untuk dependensi).
Topological Sort (untuk DAG).
Menemukan komponen terhubung dalam graph.

// Lanjutan dari kelas Graph sebelumnya
class GraphWithTraversal extends Graph {
    /**
     * Melakukan Depth-First Search (DFS) dari node awal.
     * @param startNode Node awal.
     * @param visited Set untuk melacak node yang sudah dikunjungi.
     * @param path Array untuk melacak jalur saat ini (opsional, untuk debugging/visualisasi).
     */
    dfs(startNode: string, visited: Set<string> = new Set(), path: string[] = []): void {
        if (!this.adjacencyList.has(startNode)) {
            console.error(`❌ Node awal '${startNode}' tidak ada.`);
            return;
        }

        visited.add(startNode);
        path.push(startNode);
        console.log(`Mengunjungi: ${startNode} (Jalur: ${path.join(' -> ')})`);

        const neighbors = this.adjacencyList.get(startNode);
        if (neighbors) {
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    this.dfs(neighbor, visited, path);
                }
            }
        }
        path.pop(); // Backtrack
    }
}

// Contoh Penggunaan DFS:
console.log("\n--- DFS Traversal ---");
const socialNetworkDFS = new GraphWithTraversal();
socialNetworkDFS.addNode("Alice");
socialNetworkDFS.addNode("Bob");
socialNetworkDFS.addNode("Charlie");
socialNetworkDFS.addNode("David");
socialNetworkDFS.addNode("Eve");
socialNetworkDFS.addEdge("Alice", "Bob");
socialNetworkDFS.addEdge("Alice", "Charlie");
socialNetworkDFS.addEdge("Bob", "David");
socialNetworkDFS.addEdge("Charlie", "Eve");
socialNetworkDFS.dfs("Alice");

// Studi Kasus: Deteksi Dependensi Melingkar (Cyclic Dependency)
// Misalnya, di sebuah build system atau modul JavaScript
// Modul A butuh B, B butuh C, C butuh A. Ini adalah siklus!
const dependencyGraph = new GraphWithTraversal();
dependencyGraph.addNode("ModuleA");
dependencyGraph.addNode("ModuleB");
dependencyGraph.addNode("ModuleC");
dependencyGraph.addEdge("ModuleA", "ModuleB", true); // A depends on B
dependencyGraph.addEdge("ModuleB", "ModuleC", true); // B depends on C
dependencyGraph.addEdge("ModuleC", "ModuleA", true); // C depends on A (cyclic!)

console.log("\n--- DFS untuk Deteksi Siklus ---");
// Untuk deteksi siklus, kita butuh melacak node di "stack rekursi" saat ini
// Jika kita mengunjungi node yang sudah ada di stack rekursi, maka ada siklus.
function detectCycleDFS(graph: GraphWithTraversal, node: string, visited: Set<string>, recursionStack: Set<string>): boolean {
    visited.add(node);
    recursionStack.add(node);

    const neighbors = graph.getNeighbors(node);
    if (neighbors) {
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                if (detectCycleDFS(graph, neighbor, visited, recursionStack)) {
                    return true;
                }
            } else if (recursionStack.has(neighbor)) {
                console.warn(`⚠️ Siklus terdeteksi: ${node} -> ${neighbor}`);
                return true;
            }
        }
    }
    recursionStack.delete(node); // Hapus dari stack saat backtracking
    return false;
}

const allVisited = new Set<string>();
const currentRecursionStack = new Set<string>();
let hasCycle = false;
for (const node of dependencyGraph.adjacencyList.keys()) {
    if (!allVisited.has(node)) {
        if (detectCycleDFS(dependencyGraph, node, allVisited, currentRecursionStack)) {
            hasCycle = true;
            break;
        }
    }
}
console.log(`Graph memiliki siklus: ${hasCycle}`); // Output: Graph memiliki siklus: true

Breadth-First Search (BFS)

BFS menjelajahi graph lapis demi lapis (level by level) dari node awal. Mirip seperti gelombang yang menyebar dari sebuah titik.

🎯 Kapan Digunakan:

Mencari jalur terpendek dalam graph yang tidak berbobot (misalnya, jumlah “hop” paling sedikit).
Pencarian tetangga terdekat (misalnya, semua teman dari teman).
Routing di aplikasi web (misalnya, mencari jalur navigasi minimal antar halaman).

// Lanjutan dari kelas Graph sebelumnya
class GraphWithBFS extends Graph {
    /**
     * Melakukan Breadth-First Search (BFS) dari node awal.
     * @param startNode Node awal.
     */
    bfs(startNode: string): void {
        if (!this.adjacencyList.has(startNode)) {
            console.error(`❌ Node awal '${startNode}' tidak ada.`);
            return;
        }

        const queue: string[] = [startNode];
        const visited: Set<string> = new Set<string>();
        visited.add(startNode);

        console.log(`Mengunjungi (BFS): ${startNode}`);

        while (queue.length > 0) {
            const currentNode = queue.shift()!; // Ambil node pertama dari antrian

            const neighbors = this.adjacencyList.get(currentNode);
            if (neighbors) {
                for (const neighbor of neighbors) {
                    if (!visited.has(neighbor)) {
                        visited.add(neighbor);
                        console.log(`Mengunjungi (BFS): ${neighbor}`);
                        queue.push(neighbor);
                    }
                }
            }
        }
    }

    /**
     * Mencari jalur terpendek (jumlah hop) antara dua node.
     * @param startNode Node awal.
     * @param endNode Node tujuan.
     * @returns Array of strings yang merepresentasikan jalur, atau null jika tidak ada jalur.
     */
    shortestPathBFS(startNode: string, endNode: string): string[] | null {
        if (!this.adjacencyList.has(startNode) || !this.adjacencyList.has(endNode)) {
            return null;
        }
        if (startNode === endNode) {
            return [startNode];
        }

        const queue: string[] = [startNode];
        const visited: Set<string> = new Set<string>();
        visited.add(startNode);
        const predecessors: Map<string, string | null> = new Map(); // Untuk merekonstruksi jalur

        while (queue.length > 0) {
            const currentNode = queue.shift()!;

            const neighbors = this.adjacencyList.get(currentNode);
            if (neighbors) {
                for (const neighbor of neighbors) {
                    if (!visited.has(neighbor)) {
                        visited.add(neighbor);
                        predecessors.set(neighbor, currentNode);
                        if (neighbor === endNode) {
                            // Jalur ditemukan, rekonstruksi
                            const path: string[] = [];
                            let current: string