Memahami Graf (Graph) dalam Struktur Data

Pendahuluan

Pernahkah kamu menggunakan Google Maps untuk mencari rute tercepat dari rumah ke kantor? Atau melihat fitur “Orang yang Mungkin Kamu Kenal” di media sosial? Di balik semua itu, ada sebuah struktur data yang sangat powerful bernama Graf (Graph).

Graf adalah salah satu struktur data paling fleksibel dan banyak digunakan dalam dunia nyata. Jika kamu sudah memahami konsep seperti Tree (Pohon) dalam Struktur Data, kamu akan menemukan bahwa Graf adalah generalisasinya — lebih bebas, lebih ekspresif, dan mampu merepresentasikan hubungan yang jauh lebih kompleks.

Di artikel ini, kita akan membahas apa itu Graf, bagaimana cara merepresentasikannya dalam kode, dan algoritma traversal (BFS dan DFS) yang wajib kamu kuasai.

Apa Itu Graf? Komponen dan Jenisnya

Graf adalah kumpulan node (simpul/vertex) yang saling terhubung melalui edge (sisi/arc). Tidak seperti Tree yang hierarkis dan berakar, Graf tidak memiliki batasan struktur — satu node bisa terhubung ke node mana pun.

Komponen Utama Graf

• Vertex (V): Titik atau simpul data. Contoh: kota, pengguna, halaman web.
• Edge (E): Koneksi antar dua vertex. Contoh: jalan, pertemanan, hyperlink.
• Weight: Nilai pada edge. Contoh: jarak dalam km, biaya, durasi.

Jenis-Jenis Graf

Analogi nyata: Jika kamu ingin membangun aplikasi ride-hailing seperti Gojek, setiap titik jemput dan tujuan bisa direpresentasikan sebagai vertex, sedangkan jalan-jalan yang menghubungkan titik tersebut adalah edge dengan bobot berupa jarak atau waktu tempuh.

Representasi Graf: Adjacency Matrix vs. Adjacency List

Ada dua cara utama untuk menyimpan Graf dalam memori. Pilihan yang tepat bergantung pada ukuran dan kepadatan Graf-mu.

1. Adjacency Matrix

Graf disimpan dalam array 2D berukuran V×V. Jika ada edge dari node i ke node j, maka matrix[i][j] = 1 (atau bobotnya untuk weighted graph).

class GraphMatrix:
    def __init__(self, vertices):
        # Menyimpan jumlah simpul (vertex)
        self.V = vertices

        # Membuat adjacency matrix berukuran V x V, default semua nilai 0
        self.matrix = [[0 for _ in range(vertices)] for _ in range(vertices)]

    def add_edge(self, u, v, weight=1):
        # Menambahkan edge dari u ke v dengan bobot tertentu
        self.matrix[u][v] = weight

        # Karena ini undirected graph, tambahkan juga edge dari v ke u
        self.matrix[v][u] = weight

    def display(self):
        # Menampilkan setiap baris pada adjacency matrix
        for row in self.matrix:
            print(row)


# Contoh: graph dengan 4 node (0, 1, 2, 3)
g = GraphMatrix(4)

# Menambahkan beberapa edge antar node
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

# Menampilkan adjacency matrix
g.display()

# Output:
# [0, 1, 1, 0]
# [1, 0, 0, 1]
# [1, 0, 0, 1]
# [0, 1, 1, 0]

Kelebihan: Cek apakah edge ada antara dua node → O(1).
Kekurangan: Boros memori O(V²), tidak efisien untuk graf jarang (sparse graph).

2. Adjacency List

Setiap vertex menyimpan daftar tetangganya. Ini adalah representasi paling umum digunakan.

from collections import defaultdict


class GraphList:
    def __init__(self):
        # Menyimpan graph sebagai adjacency list
        # Format: {node: [(tetangga, bobot), ...]}
        self.graph = defaultdict(list)

    def add_edge(self, u, v, weight):
        # Menambahkan sisi dari u ke v beserta bobotnya
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))  # Hapus baris ini jika ingin graph berarah

    def display(self):
        # Menampilkan isi graph per node
        for node, neighbors in self.graph.items():
            print(f"{node} -> {neighbors}")


# Contoh penggunaan
g = GraphList()

# Menambahkan beberapa koneksi antar kota
g.add_edge("Jakarta", "Bogor", 60)
g.add_edge("Jakarta", "Tangerang", 30)
g.add_edge("Bogor", "Bandung", 120)

# Menampilkan adjacency list
g.display()

# Output:
# Jakarta -> [('Bogor', 60), ('Tangerang', 30)]
# Bogor -> [('Jakarta', 60), ('Bandung', 120)]
# Tangerang -> [('Jakarta', 30)]
# Bandung -> [('Bogor', 120)]

Kelebihan: Hemat memori O(V + E), efisien untuk iterasi tetangga.
Kekurangan: Cek edge spesifik → O(V) di kasus terburuk.

Panduan cepat: Gunakan Adjacency Matrix untuk graf kecil dan padat. Gunakan Adjacency List untuk graf besar dan jarang (kebanyakan kasus nyata).

Algoritma Traversal Umum: BFS dan DFS

Traversal Graf berarti mengunjungi semua vertex secara sistematis. Ada dua algoritma utama yang wajib dikuasai.

BFS — Breadth-First Search (Penelusuran Melebar)

BFS menjelajahi Graf lapis demi lapis menggunakan Queue. Cocok untuk mencari jalur terpendek (jumlah edge terkecil).

from collections import deque


def bfs(graph, start):
    # Validasi sederhana agar node awal ada di dalam graph
    if start not in graph:
        return []

    visited = {start}          # Menyimpan node yang sudah dikunjungi
    queue = deque([start])     # Queue untuk proses BFS
    order = []                 # Menyimpan urutan kunjungan node

    while queue:
        node = queue.popleft()  # Ambil node dari depan queue
        order.append(node)

        # Ambil semua tetangga node saat ini
        for neighbor in graph.get(node, []):
            # Jika belum dikunjungi, tandai lalu masukkan ke queue
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


# Contoh graph menggunakan adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": [],
    "E": [],
    "F": []
}

hasil = bfs(graph, "A")
print("Urutan BFS:", hasil)

# Output:
# Urutan BFS: ['A', 'B', 'C', 'D', 'E', 'F']

DFS — Depth-First Search (Penelusuran Mendalam)

DFS menjelajahi Graf sejauh mungkin ke satu arah sebelum backtrack, menggunakan Stack (atau rekursi).

def dfs(graph, start, visited=None):
    # Jika visited belum ada, buat set kosong untuk melacak node yang sudah dikunjungi
    if visited is None:
        visited = set()

    # Tandai node saat ini sebagai sudah dikunjungi
    visited.add(start)
    order = [start]  # Simpan urutan kunjungan

    # Kunjungi setiap tetangga yang belum dikunjungi
    for neighbor in graph[start]:
        if neighbor not in visited:
            order.extend(dfs(graph, neighbor, visited))

    return order


# Representasi graph menggunakan adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": []
}

# Jalankan DFS mulai dari node "A"
result = dfs(graph, "A")
print("Urutan DFS:", result)

# Output:
# Urutan DFS: ['A', 'B', 'D', 'E', 'C', 'F']

Untuk perbandingan lebih mendalam tentang kapan sebaiknya menggunakan BFS atau DFS dalam skenario tertentu, baca artikel BFS vs DFS: Perbedaan dan Kapan Menggunakannya dalam Traversal Graf.

Contoh Kasus Nyata Penggunaan Graf

Graf bukan sekadar teori — ia ada di mana-mana dalam sistem yang kita gunakan sehari-hari.

1. Sistem Rekomendasi Pertemanan (Social Network)

from collections import defaultdict


class SocialNetwork:
    def __init__(self):
        # defaultdict(set) membuat setiap user otomatis punya himpunan teman
        self.graph = defaultdict(set)

    def add_friendship(self, user1, user2):
        # Pertemanan dua arah: user1 berteman dengan user2, dan sebaliknya
        self.graph[user1].add(user2)
        self.graph[user2].add(user1)

    def suggest_friends(self, user):
        # Ambil semua teman langsung dari user
        direct_friends = self.graph[user]
        suggestions = set()

        # Cek teman dari setiap teman langsung
        for friend in direct_friends:
            for friend_of_friend in self.graph[friend]:
                # Jangan sarankan diri sendiri atau teman yang sudah terhubung langsung
                if friend_of_friend != user and friend_of_friend not in direct_friends:
                    suggestions.add(friend_of_friend)

        return suggestions


net = SocialNetwork()

# Menambahkan hubungan pertemanan
net.add_friendship("Andi", "Budi")
net.add_friendship("Budi", "Citra")
net.add_friendship("Budi", "Doni")
net.add_friendship("Andi", "Eka")

# Menampilkan rekomendasi teman untuk Andi
hasil = sorted(net.suggest_friends("Andi"))
print("Rekomendasi teman untuk Andi:", hasil)

# Output:
# Rekomendasi teman untuk Andi: ['Citra', 'Doni']

2. Pencarian Jalur Terpendek — Contoh Sederhana

Bayangkan kamu ingin membangun fitur navigasi seperti yang ada di aplikasi Maps. Di sini kita menggunakan BFS untuk menemukan rute dengan jumlah langkah terkecil:

from collections import deque


def shortest_path_bfs(graph, start, end):
    # Jika titik awal dan tujuan sama, jalurnya langsung ditemukan
    if start == end:
        return [start]

    # Cek apakah node awal dan tujuan ada di graph
    if start not in graph or end not in graph:
        return None

    visited = {start}         # Menyimpan node yang sudah dikunjungi
    queue = deque([[start]])  # Queue berisi jalur, bukan hanya node

    while queue:
        path = queue.popleft()       # Ambil jalur paling depan
        current_node = path[-1]      # Node terakhir pada jalur saat ini

        # Ambil semua tetangga dari node saat ini
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                new_path = path + [neighbor]  # Bentuk jalur baru

                # Jika tujuan ditemukan, langsung kembalikan jalurnya
                if neighbor == end:
                    return new_path

                visited.add(neighbor)
                queue.append(new_path)

    # Jika BFS selesai dan tujuan tidak ditemukan
    return None


city_graph = {
    "Jakarta":   ["Bogor", "Tangerang", "Bekasi"],
    "Bogor":     ["Jakarta", "Bandung"],
    "Tangerang": ["Jakarta"],
    "Bekasi":    ["Jakarta", "Karawang"],
    "Bandung":   ["Bogor", "Cirebon"],
    "Karawang":  ["Bekasi"],
    "Cirebon":   ["Bandung"],
}

path = shortest_path_bfs(city_graph, "Tangerang", "Cirebon")

if path:
    print("Jalur terpendek:", " -> ".join(path))
else:
    print("Jalur tidak ditemukan")

# Output:
# Jalur terpendek: Tangerang -> Jakarta -> Bogor -> Bandung -> Cirebon

Untuk kasus pencarian rute dengan bobot jarak nyata (bukan sekadar jumlah langkah), kamu bisa mempelajari lebih lanjut di artikel Implementasi Algoritma Dijkstra: Mencari Rute Terpendek dalam Graf.

3. Deteksi Ketergantungan (Dependency Resolution)

Sistem build, package manager seperti pip atau npm, hingga task scheduler menggunakan Directed Acyclic Graph (DAG) untuk menentukan urutan eksekusi:

def topological_sort(tasks):
    # Menyimpan node yang sudah selesai diproses
    visited = set()
    # Menyimpan urutan hasil topological sort
    result = []

    def dfs(task):
        # Tandai task sebagai sudah dikunjungi
        visited.add(task)

        # Kunjungi semua dependensi lebih dulu
        for dep in tasks.get(task, []):
            if dep not in visited:
                dfs(dep)

        # Setelah semua dependensi selesai, simpan task ini
        result.append(task)

    # Jalankan DFS untuk setiap task
    for task in tasks:
        if task not in visited:
            dfs(task)

    # Dependensi sudah ditambahkan lebih dulu, tidak perlu dibalik
    return result


# "deploy" bergantung pada "build" dan "test"
# "build" dan "test" sama-sama bergantung pada "install_deps"
tasks = {
    "deploy":       ["build", "test"],
    "build":        ["install_deps"],
    "test":         ["install_deps"],
    "install_deps": [],
}

sorted_tasks = topological_sort(tasks)
print("Urutan eksekusi task:", sorted_tasks)

# Output:
# Urutan eksekusi task: ['install_deps', 'build', 'test', 'deploy']

Pertanyaan yang Sering Diajukan

Apa perbedaan Graf dan Tree?

Tree adalah Graf khusus yang bersifat terhubung, tidak memiliki siklus (acyclic), dan punya tepat satu jalur antara dua node mana pun. Graf lebih umum — boleh memiliki siklus, boleh tidak terhubung, dan bisa ada banyak jalur antar dua node. Singkatnya, semua Tree adalah Graf, tetapi tidak semua Graf adalah Tree.

Kapan sebaiknya menggunakan Adjacency Matrix dibanding Adjacency List?

Gunakan Adjacency Matrix jika grafmu padat (jumlah edge mendekati V²) atau jika perlu mengakses keberadaan sebuah edge dengan cepat dalam O(1). Adjacency List cocok untuk kebanyakan kasus nyata karena graf di dunia nyata cenderung sparse — jumlah edge jauh lebih kecil dari V², sehingga Adjacency List lebih hemat memori.

Apakah Graf selalu perlu terhubung sepenuhnya?

Tidak. Graf yang tidak semua node-nya terhubung disebut Disconnected Graph. Ini valid dan sering ditemui, misalnya pada peta kota yang terpisah oleh lautan. Dalam kode, BFS/DFS dari satu node tidak akan mengunjungi komponen yang terputus — kamu perlu mengulangi traversal dari setiap node yang belum dikunjungi untuk menjangkau seluruh graf.

Apa bedanya BFS dan DFS, dan kapan memilih masing-masing?

BFS cocok ketika kamu mencari jalur terpendek dalam arti jumlah edge minimum, atau perlu menjelajahi node yang paling dekat terlebih dahulu. DFS lebih cocok untuk mendeteksi siklus, melakukan topological sort, atau menjelajahi semua kemungkinan jalur hingga kedalaman tertentu. Jika solusi ada di level yang tidak terlalu dalam, BFS lebih efisien; jika perlu menjelajahi seluruh ruang kemungkinan, DFS lebih praktis.

Bagaimana cara mendeteksi siklus dalam Graf?

Untuk Undirected Graph, gunakan DFS dan tandai node sebagai “sedang dikunjungi”. Jika ditemukan tetangga yang sudah ditandai dan bukan parent dari node saat ini, berarti ada siklus. Untuk Directed Graph, gunakan DFS dengan tiga status: belum dikunjungi, sedang dikunjungi, dan selesai dikunjungi — jika saat traversal menemukan node yang berstatus “sedang dikunjungi”, itu menandakan adanya siklus.

Kesimpulan

Graf adalah struktur data yang sangat kuat dan ada di mana-mana — dari navigasi, media sosial, manajemen dependensi, hingga sistem rekomendasi. Poin utama yang perlu kamu ingat:

• Graf terdiri dari Vertex dan Edge; bisa directed/undirected, weighted/unweighted.
• Adjacency List cocok untuk kebanyakan kasus nyata (graf sparse); Adjacency Matrix untuk graf padat.
• BFS ideal untuk mencari jalur terpendek (jumlah edge) atau penelusuran lebar; DFS cocok untuk menjelajahi semua kemungkinan, deteksi siklus, atau topological sort.
• Banyak masalah dunia nyata — routing, rekomendasi, dependency resolution — pada dasarnya adalah masalah Graf.

Langkah selanjutnya: coba implementasikan sendiri algoritma Dijkstra untuk weighted graph, atau eksplorasi bagaimana konsep Graf berkaitan dengan Greedy vs Dynamic Programming: Perbedaan dan Kapan Menggunakannya untuk menyelesaikan masalah optimasi jalur yang lebih kompleks.