Dasar Teori Graf

Graf merepresentasikan sekumpulan objek beserta hubungan antarpasangannya, dan teori graf mempelajari cara menelusurinya secara sistematis. Topik ini membahas node dan sisi, representasi daftar ketetanggaan dan matriks ketetanggaan, serta dua algoritma penelusuran utama, yaitu breadth-first search (BFS) dan depth-first search (DFS). Seluruh contoh menggunakan satu graf jaringan komputer laboratorium yang sama, sehingga setiap keluaran kode dapat diperiksa ulang terhadap diagramnya. Setelah topik ini dipahami, penelusuran graf dapat ditulis dengan dict dan list Python, jalur terpendek tak berbobot dapat dihitung dengan BFS, dan peran graf pada sistem rekomendasi serta jaringan saraf dapat dikenali.

Node, sisi, dan derajat#

Graf dinyatakan secara formal sebagai pasangan $G = (V, E)$, dengan $V$ himpunan node dan $E$ himpunan sisi. Node (vertex) mewakili objek yang dihubungkan, sedangkan sisi (edge) mewakili hubungan antara dua node. Pada graf contoh sepanjang topik ini, node adalah enam komputer laboratorium bernama pc1 sampai pc6, sedangkan sisi adalah kabel yang menghubungkan dua komputer. Graf semacam ini disebut graf tak berarah (undirected graph) karena kabelnya dapat dilewati dalam dua arah, berbeda dengan graf berarah (directed graph) yang sisinya hanya mengalir satu arah seperti tautan antarhalaman web.

Dua node yang terhubung langsung oleh sebuah sisi disebut sepasang tetangga (neighbor), sedangkan banyaknya tetangga sebuah node disebut derajat (degree). Jumlah derajat seluruh node selalu sama dengan dua kali banyaknya sisi, sebab setiap sisi selalu menyentuh dua node sekaligus.

Graf contoh memiliki tujuh sisi, sehingga jumlah derajatnya 14, dan hitungan per node menegaskannya, yaitu pc1, pc2, pc5, dan pc6 berderajat dua, sedangkan pc3 dan pc4 berderajat tiga. Rangkaian sisi yang menghubungkan dua node disebut jalur (path), dan graf disebut terhubung (connected) apabila setiap pasangan node memiliki jalur di antara keduanya. Graf jaringan lab pada topik ini terhubung, sehingga setiap komputer dapat dijangkau dari pc1. Diagram berikut memperlihatkan keenam node beserta ketujuh sisinya.

Representasi adjacency list dan adjacency matrix#

Representasi graf adalah struktur data yang menyimpan node dan sisi, sehingga algoritma dapat membacanya. Dua representasi yang paling umum adalah daftar ketetanggaan (adjacency list) dan matriks ketetanggaan (adjacency matrix). Daftar ketetanggaan memetakan setiap node ke daftar tetangganya, dan pada Python bentuk alaminya adalah dict yang nilainya list. Matriks ketetanggaan menyimpan kisi dua dimensi berisi 0 dan 1, dengan baris serta kolom bernomor sesuai node, dan sel bernilai 1 apabila dua node tersebut terhubung.

Pada graf jarang sisi (sparse), yaitu graf yang banyaknya sisi jauh lebih kecil daripada banyaknya pasangan node yang mungkin, daftar ketetanggaan jauh lebih hemat memori karena ukurannya mengikuti banyaknya sisi. Matriks ketetanggaan menyimpan $V^2$ sel terlepas dari banyaknya sisi, tetapi menguji satu sisi tanpa perlu menyusuri apa pun. Sebagian besar graf nyata, termasuk jaringan komputer dan jaringan pertemanan, bersifat jarang sisi, sehingga daftar ketetanggaan menjadi pilihan bawaan pada library graf. Skrip utama topik ini pun menyimpan grafnya sebagai dict Python, sedangkan skrip berikut membangun matriks ketetanggaan dari graf yang sama agar kedua representasinya dapat dibandingkan.

import numpy as np

graf = {
    "pc1": ["pc2", "pc3"],
    "pc2": ["pc1", "pc4"],
    "pc3": ["pc1", "pc4", "pc5"],
    "pc4": ["pc2", "pc3", "pc6"],
    "pc5": ["pc3", "pc6"],
    "pc6": ["pc4", "pc5"],
}
nama = sorted(graf)
indeks = {node: i for i, node in enumerate(nama)}
matriks = np.zeros((len(nama), len(nama)), dtype=int)
for node, tetangga in graf.items():
    for t in tetangga:
        matriks[indeks[node], indeks[t]] = 1
print(nama)
print(matriks)

['pc1', 'pc2', 'pc3', 'pc4', 'pc5', 'pc6']
[[0 1 1 0 0 0]
 [1 0 0 1 0 0]
 [1 0 0 1 1 0]
 [0 1 1 0 0 1]
 [0 0 1 0 0 1]
 [0 0 0 1 1 0]]

Matriks pada keluaran bersifat simetris terhadap diagonal utamanya karena grafnya tak berarah, yaitu sisi antara pc1 dan pc2 tercatat sebagai 1 pada dua tempat sekaligus. Pada graf berarah, simetri itu hilang karena setiap sisi hanya tercatat pada satu arah. Bentuk kisi 0 dan 1 juga memudahkan operasi aljabar linear, misalnya perkalian matriks yang menghitung banyaknya jalur dua sisi antara setiap pasangan node. Kembali ke daftar ketetanggaan, struktur inilah yang digunakan penelusuran pada bagian berikutnya.

Menelusuri graf dengan BFS dan DFS#

Penelusuran (traversal) adalah kunjungan sistematis ke setiap node yang terjangkau dari sebuah node awal. Breadth-first search (BFS) menelusuri per lapisan dengan antrean (queue), yaitu node awal terlebih dahulu, kemudian seluruh tetangganya, kemudian tetangga dari tetangganya. Depth-first search (DFS) menelusuri sedalam mungkin dengan tumpukan (stack) atau rekursi, yaitu menyusuri tetangga dari node yang baru dicapai sebelum mundur. Keduanya mengunjungi himpunan node yang sama, tetapi urutan kunjungannya berbeda, dan perbedaan urutan itulah yang menentukan kegunaannya.

Skrip berikut menyimpan graf jaringan lab sebagai daftar ketetanggaan, lalu menelusurinya dengan BFS dan DFS mulai dari pc1. Tetangga selalu diurutkan dengan sorted() sebelum diproses, sehingga urutan kunjungannya tetap sama pada setiap eksekusi dan keluarannya dapat diperiksa terhadap diagram. BFS juga mencatat jarak dan induk (parent) setiap node pada saat node itu pertama kali ditemukan, dua data yang langsung memberikan jalur terpendek pada graf tak berbobot.

"""BFS dan DFS pada graf jaringan lab dengan adjacency list berbasis dict."""
from collections import deque

graf = {
    "pc1": ["pc2", "pc3"],
    "pc2": ["pc1", "pc4"],
    "pc3": ["pc1", "pc4", "pc5"],
    "pc4": ["pc2", "pc3", "pc6"],
    "pc5": ["pc3", "pc6"],
    "pc6": ["pc4", "pc5"],
}

def bfs(g, mulai):
    """Telusuri per lapisan, lalu catat urutan, jarak, dan induk tiap node."""
    dikunjungi = {mulai}
    antrean = deque([mulai])
    urutan = []
    jarak = {mulai: 0}
    induk = {mulai: None}
    while antrean:
        node = antrean.popleft()
        urutan.append(node)
        for tetangga in sorted(g[node]):
            if tetangga not in dikunjungi:
                dikunjungi.add(tetangga)
                jarak[tetangga] = jarak[node] + 1
                induk[tetangga] = node
                antrean.append(tetangga)
    return urutan, jarak, induk

def dfs(g, mulai):
    """Telusuri sedalam mungkin dengan tumpukan dan pemeriksaan saat dikunjungi."""
    dikunjungi = set()
    tumpukan = [mulai]
    urutan = []
    while tumpukan:
        node = tumpukan.pop()
        if node in dikunjungi:
            continue
        dikunjungi.add(node)
        urutan.append(node)
        for tetangga in sorted(g[node], reverse=True):
            if tetangga not in dikunjungi:
                tumpukan.append(tetangga)
    return urutan

def jalur(induk, tujuan):
    """Rekonstruksi jalur terpendek dari tabel induk hasil BFS."""
    lintasan = []
    node = tujuan
    while node is not None:
        lintasan.append(node)
        node = induk[node]
    return lintasan[::-1]

urutan_bfs, jarak, induk = bfs(graf, "pc1")
print("BFS dari pc1 :", " -> ".join(urutan_bfs))
print("jarak BFS    :", {node: jarak[node] for node in sorted(jarak)})
print("DFS dari pc1 :", " -> ".join(dfs(graf, "pc1")))
print("terpendek    :", " -> ".join(jalur(induk, "pc6")))

BFS dari pc1 : pc1 -> pc2 -> pc3 -> pc4 -> pc5 -> pc6
jarak BFS    : {'pc1': 0, 'pc2': 1, 'pc3': 1, 'pc4': 2, 'pc5': 2, 'pc6': 3}
DFS dari pc1 : pc1 -> pc2 -> pc4 -> pc3 -> pc5 -> pc6
terpendek    : pc1 -> pc2 -> pc4 -> pc6

Keluaran memperlihatkan karakter keduanya secara berdampingan. BFS mengunjungi pc1, kemudian lapisan berjarak satu yang berisi pc2 dan pc3, kemudian lapisan berjarak dua yang berisi pc4 dan pc5, dan terakhir pc6 pada lapisan tiga. DFS justru menyelam ke pc2 lalu pc4 lalu pc3 sebelum mencapai pc5 dan pc6, karena tumpukannya memprioritaskan tetangga yang baru saja ditemukan. Baris terakhir memperlihatkan jalur terpendek dari pc1 menuju pc6 sepanjang tiga sisi, yaitu pc1, pc2, pc4, dan pc6, yang direkonstruksi dengan menelusuri induk dari pc6 kembali ke pc1.

Jaminan jalur terpendek BFS berlaku pada graf tak berbobot, yaitu graf yang setiap sisinya bernilai sama. Penyebabnya ada pada antrean, karena node diolah menurut jaraknya dari node awal, mulai dari yang terdekat, sehingga saat sebuah node pertama kali ditemukan, tidak ada jalur lain yang lebih pendek menuju node itu. Pada graf berbobot, misalnya sisi yang membawa nilai latensi kabel, BFS tidak lagi menjamin hasilnya, dan algoritma seperti Dijkstra mengambil alih. Kompleksitas BFS maupun DFS pada daftar ketetanggaan adalah $O(V + E)$, karena setiap node dimasukkan antrean sekali dan setiap sisi diperiksa paling banyak dua kali.

Di mana hal ini ditemui dalam kode#

Struktur graf paling sederhana pada Python adalah dict yang nilainya list atau set, persis seperti skrip pada topik ini, dan struktur tersebut sudah cukup untuk banyak kebutuhan. Pada jaringan komputer lab, BFS dari satu komputer menghasilkan urutan pemindaian yang menyentuh setiap perangkat dengan lompatan paling sedikit, dan jarak BFS-nya menghampiri banyaknya perangkat perantara yang dilalui paket. Router pada jaringan nyata bekerja pada graf berbobot dengan algoritma yang lebih lengkap, tetapi pola penelusurannya tetap sama. Pencarian jalur terpendek tak berbobot pada labirin, papan permainan, dan struktur menu juga menggunakan BFS yang sama.

Sistem rekomendasi membaca graf yang nodenya pengguna dan sisinya hubungan pertemanan atau kesamaan minat. Rekomendasi koneksi yang umum adalah kandidat yang belum berteman tetapi paling banyak berbagi tetangga, karena banyaknya tetangga bersama menandakan kedekatan. Skrip berikut menghitung skor tersebut untuk pengguna ali pada graf pertemanan kecil.

graf = {
    "ali": ["budi", "citra"],
    "budi": ["ali", "dewi", "eka"],
    "citra": ["ali", "eka"],
    "dewi": ["budi"],
    "eka": ["budi", "citra"],
}

skor = []
for kandidat in sorted(graf):
    if kandidat == "ali" or kandidat in graf["ali"]:
        continue
    bersama = sorted(set(graf["ali"]) & set(graf[kandidat]))
    if bersama:
        skor.append((len(bersama), kandidat, bersama))

for banyak, kandidat, bersama in sorted(skor, reverse=True):
    print("rekomendasi untuk ali:", kandidat,
          f"({banyak} tetangga bersama: {', '.join(bersama)})")

rekomendasi untuk ali: eka (2 tetangga bersama: budi, citra)
rekomendasi untuk ali: dewi (1 tetangga bersama: budi)

Keluaran menempatkan eka di urutan pertama karena berbagi dua tetangga dengan ali, sedangkan dewi hanya berbagi satu. Pola hitungan tetangga bersama yang sama digunakan sistem rekomendasi materi belajar, artikel, dan video pada layanan berskala besar, dengan graf yang jauh lebih besar dan skor yang lebih halus. Pada jaringan saraf tiruan, graf muncul sebagai graf komputasi, yaitu node berupa operasi atau unit hitung dan sisi berupa aliran tensor antara keduanya, sehingga propagasi maju dan propagasi mundur adalah penelusuran yang mengikuti arah sisi graf tersebut. Model bahasa dan mesin pencari juga menyimpan relasi antarentitas sebagai graf pengetahuan (knowledge graph), sehingga struktur node dan sisi terus muncul di luar topik ini.

Ringkasan#

• Graf $G = (V, E)$ menyimpan objek sebagai node dan hubungan sebagai sisi, dengan derajat sebagai banyaknya tetangga, serta jumlah derajat seluruh node yang selalu dua kali banyaknya sisi.
• Daftar ketetanggaan berbasis dict berbiaya memori $O(V + E)$ dan cocok untuk graf jarang sisi, sedangkan matriks ketetanggaan berbiaya $O(V^2)$ tetapi menguji satu sisi dalam $O(1)$.
• BFS menelusuri per lapisan menggunakan antrean dan menghasilkan jalur terpendek pada graf tak berbobot, sedangkan DFS menyelam sedalam mungkin menggunakan tumpukan, dan keduanya berkompleksitas $O(V + E)$.
• Graf muncul pada kode sebagai jaringan komputer, graf pertemanan untuk rekomendasi berbasis tetangga bersama, serta graf komputasi jaringan saraf yang sisinya mengalirkan tensor.

Referensi#

• collections — Python Software Foundation — Dokumentasi deque yang digunakan BFS sebagai antrean berkinerja tetap.
• Contemporary Mathematics — OpenStax — Buku teks terbuka dengan bab graf yang membahas node, sisi, derajat, dan model jaringan.
• NumPy Documentation — NumPy Developers — Dokumentasi NumPy yang digunakan contoh matriks ketetanggaan.