Struktur Bercabang · Pelajaran 9 dari 10
Graf dan cara menyimpannya
9 menit baca · BelajarCode
Graf terdiri dari simpul (vertex) dan sisi (edge) yang menghubungkan pasangan simpul. Graf memodelkan hubungan: jalan antarkota, pertemanan di media sosial, prasyarat mata kuliah, atau tautan antarhalaman web.
| Jenis | Ciri | Contoh |
|---|---|---|
| Tak berarah | Sisi berlaku dua arah | Pertemanan, jalan dua arah |
| Berarah | Sisi punya arah | Mengikuti akun, prasyarat mata kuliah |
| Berbobot | Sisi punya nilai | Jarak atau waktu tempuh antarhalte |
Dua cara menyimpan graf
1sisi = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]2simpul = ["A", "B", "C", "D", "E"]34daftar = {s: [] for s in simpul}5for u, v in sisi:6 daftar[u].append(v)7 daftar[v].append(u)89print("Daftar ketetanggaan:")10for s in simpul:11 print(f" {s}: {daftar[s]} derajat {len(daftar[s])}")1213indeks = {s: i for i, s in enumerate(simpul)}14matriks = [[0] * len(simpul) for _ in simpul]15for u, v in sisi:16 matriks[indeks[u]][indeks[v]] = 117 matriks[indeks[v]][indeks[u]] = 11819print("Matriks ketetanggaan:")20print(" " + " ".join(simpul))21for s in simpul:22 print(f" {s} " + " ".join(str(x) for x in matriks[indeks[s]]))Daftar ketetanggaan:
A: ['B', 'C'] derajat 2
B: ['A', 'D'] derajat 2
C: ['A', 'D'] derajat 2
D: ['B', 'C', 'E'] derajat 3
E: ['D'] derajat 1
Matriks ketetanggaan:
A B C D E
A 0 1 1 0 0
B 1 0 0 1 0
C 1 0 0 1 0
D 0 1 1 0 1
E 0 0 0 1 0| Matriks ketetanggaan | Daftar ketetanggaan | |
|---|---|---|
| Memori | O(V²) | O(V + E) |
| Cek apakah u dan v terhubung | O(1) | O(derajat u) |
| Menelusuri semua tetangga u | O(V) | O(derajat u) |
| Cocok untuk | Graf padat atau kecil | Graf jarang, seperti jaringan jalan atau pertemanan |
V adalah banyak simpul dan E banyak sisi. Kebanyakan graf di dunia nyata jarang (setiap simpul hanya terhubung ke sedikit simpul lain), sehingga daftar ketetanggaan lebih sering dipakai.
Graf berbobot
Untuk graf berbobot, daftar ketetanggaan menyimpan pasangan tetangga dan bobotnya:
1jalur = {2 "Kampus": [("Asrama", 2), ("Perpustakaan", 1)],3 "Asrama": [("Kampus", 2), ("Kantin", 3)],4 "Perpustakaan": [("Kampus", 1), ("Kantin", 1)],5 "Kantin": [("Asrama", 3), ("Perpustakaan", 1)],6}7for tujuan, menit in jalur["Kampus"]:8 print(f"Kampus -> {tujuan}: {menit} menit")Kampus -> Asrama: 2 menit Kampus -> Perpustakaan: 1 menit
Graf berbobot seperti ini menjadi masukan algoritma jalur terpendek Dijkstra, yang dibahas di kursus Desain dan Analisis Algoritma.
Cek pemahaman
Sebuah media sosial punya 100 juta pengguna, dan rata-rata setiap pengguna punya 200 teman. Representasi mana yang masuk akal?
Latihan
Graf prasyarat mata kuliah
Mata kuliah dan prasyaratnya: Algoritma 1 adalah prasyarat Struktur Data, Struktur Data adalah prasyarat Algoritma Lanjut, Matematika Diskrit adalah prasyarat Algoritma Lanjut. Buat graf berarah dalam bentuk daftar ketetanggaan, lalu tampilkan mata kuliah yang tidak punya prasyarat.
Pembahasan
1prasyarat = [2 ("Algoritma 1", "Struktur Data"),3 ("Struktur Data", "Algoritma Lanjut"),4 ("Matematika Diskrit", "Algoritma Lanjut"),5]6graf = {}7masuk = {}8for dari, ke in prasyarat:9 graf.setdefault(dari, []).append(ke)10 graf.setdefault(ke, [])11 masuk[ke] = masuk.get(ke, 0) + 112 masuk.setdefault(dari, 0)1314for mk, tujuan in graf.items():15 print(f"{mk} -> {tujuan}")16print("Tanpa prasyarat:", [mk for mk in graf if masuk[mk] == 0])Algoritma 1 -> ['Struktur Data'] Struktur Data -> ['Algoritma Lanjut'] Algoritma Lanjut -> [] Matematika Diskrit -> ['Algoritma Lanjut'] Tanpa prasyarat: ['Algoritma 1', 'Matematika Diskrit']
Banyaknya sisi yang masuk ke sebuah simpul disebut derajat masuk. Mata kuliah dengan derajat masuk 0 bisa diambil di semester pertama. Mengurutkan semua mata kuliah dengan cara ini disebut topological sort.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.