Graph

Kegiatan Belajar 1: Pengantar Graph

A. Definisi dan Sejarah Graph

1. Pengertian Graph

• Graph: cara merepresentasikan hubungan antara pasangan objek (Goodrich, 2014). Koleksi objek (vertex) dan koleksi relasi (edge) antar vertex.
• Perbedaan dengan tree: termasuk non-linear data structure, tetapi graph tidak mengenal konsep level dan dapat memiliki cycle.
• Contoh: peta jalan (vertex = persimpangan, edge = jalan), kerjasama peneliti menulis paper, peta jembatan Königsberg.

2. Sejarah Graph

• Leonhard Euler (abad ke-18) memecahkan masalah Jembatan Königsberg di Polandia.
• Terdapat 4 land area (vertex A, B, C, D) dan 7 jembatan (edge a, b, c, d, e, f, g).

B. Terminologi Graph

1. Komponen Dasar

• Vertex: titik/node pada graph yang merepresentasikan objek.
• Edge: garis yang menghubungkan dua vertex.
• Adjacent: dua vertex yang terhubung langsung oleh edge. Vertex yang adjacent disebut neighbor.
• Weight: nilai/bobot pada edge yang menghubungkan vertex adjacent (misal: jarak, waktu, biaya).
• Path: rangkaian edge dari satu vertex menuju vertex lain (contoh: I → H → G → F).
• Cycle: path yang berakhir pada vertex awal. Graph tanpa cycle = tree. Jika graph non-directed dengan N vertex memiliki > N-1 edge, maka terdapat cycle.

C. Jenis-Jenis Graph

1. Berdasarkan Konektivitas

• Connected graph: setiap vertex memiliki minimal satu path menuju setiap vertex lainnya.
• Non-connected graph: terdapat vertex yang tidak memiliki path menuju vertex lain.

2. Berdasarkan Weight

• Weighted graph: edge memiliki label numerik (weight). Definisi: w(e) untuk setiap edge e, dengan w(u,v) = w(e) untuk edge e = (u,v).
• Unweighted graph: edge tanpa label/bobot.

D. Representasi Awal Graph

1. Adjacency Matrix

• Matriks N×N untuk graph ber-N vertex. Isi 1 jika ada relasi, 0 jika tidak.
• Identity diagonal: relasi vertex terhadap dirinya sendiri selalu 0.
• Contoh: graph 4 vertex (A,B,C,D) → matriks 4×4 dengan baris dan kolom A,B,C,D.

2. Adjacency List

• Tabel dengan kolom Vertex dan List. Setiap baris mencantumkan vertex yang berelasi.
• Contoh: vertex A berelasi B,C,D → List: B → C → D.

---

Kegiatan Belajar 2: Representasi Graph

A. Representasi Graph Menjadi Matriks

1. Proses Pembuatan Matriks

• Untuk graph dengan 12 vertex (0-11), buat matriks 12×12.
• Aturan: baris = vertex asal, kolom = vertex tujuan. Isi 1 jika ada edge, 0 jika tidak.
• Contoh relasi: vertex 0 → vertex 1,4; vertex 1 → vertex 0,2,5,6; vertex 5 → vertex 1,2,4,6,9; dst.
• Matriks bersimetri untuk undirected graph (nilai [i][j] = [j][i]).

B. Representasi Graph Menjadi Tabel

1. Proses Pembuatan Tabel

• Buat kolom sesuai jumlah vertex (0-11). Setiap kolom berisi vertex yang berelasi, ditulis menurun ke bawah.
• Contoh: kolom 0 berisi 1 (baris 1), 4 (baris 2). Kolom 5 berisi 1, 2, 4, 6, 9.

C. Edge List Structure

1. Konsep Edge List

• Dibagi dua bagian: V (vertex) dan E (edge).
• Setiap vertex di bagian V mengarahkan panah ke edge yang dimilikinya.
• Contoh graph 4 vertex (u,v,w,z), 4 edge (e,f,g,h):
  • vertex u → edge e, g
  • vertex v → edge e, f
  • vertex w → edge f, g, h
  • vertex z → edge h

D. Adjacency List Structure

1. Konsep Adjacency List

• Hanya menggunakan bagian V (vertex). Setiap vertex mencantumkan edge yang dimiliki.
• Contoh: u → (e g), v → (e f), w → (f g h), z → (h).

E. Adjacency Map Structure

1. Konsep Adjacency Map

• Setiap vertex menunjukkan vertex lain yang berelasi beserta edge penghubungnya.
• Contoh:
  • u → v/e, w/g (vertex u terhubung ke v melalui edge e, ke w melalui edge g)
  • v → u/e, w/f
  • w → u/g, v/f, z/h
  • z → w/h

---

Kegiatan Belajar 3: Traversal Graph

A. Definisi Traversal

1. Pengertian Traversal

• Traversal: prosedur sistematis untuk mengeksplorasi graph dengan menjelajahi seluruh vertex dan edge (Goodrich et al., 2014).
• Dilakukan menggunakan algoritma tertentu untuk menemukan jalur dari vertex awal ke vertex tujuan.

B. Lintasan Terpendek (Shortest Path)

1. Konsep Shortest Path

• Mencari traversal dengan total weight edge terkecil dari vertex awal ke vertex tujuan.
• Contoh: weighted graph 4 vertex (A,B,C,D) dengan edge: A-B=6, A-C=10, B-C=4, B-D=2, C-D=2.
  • A→B→D = 6+2 = 8 ✓ (terpendek)
  • A→C→D = 10+2 = 12
  • A→B→C→D = 6+4+2 = 12
  • A→C→B→D = 10+4+2 = 16

C. Minimum Spanning Tree (MST)

1. Konsep MST

• MST: tree khusus yang meminimalkan jumlah edge untuk menghubungkan semua vertex.
• Formula: jumlah edge E = V - 1 (V = jumlah vertex).
• Contoh: perusahaan telepon ingin memasang kabel ke beberapa rumah dengan jumlah kabel minimum → menghemat biaya.
• Terdapat banyak MST mungkin untuk satu set vertex.

D. Topological Sorting dan Directed Graph

1. Directed Graph

• Directed graph: edge memiliki arah (ditunjukkan panah). Hanya bisa berjalan satu arah sepanjang edge.
• Undirected graph: edge tidak memiliki arah. Tidak semua vertex dapat dilewati secara berurutan.
• Perbedaan pada matriks: directed graph matriks tidak simetris (nilai [i][j] ≠ [j][i]).

2. Topological Sorting

• Mengatur item/kejadian dalam urutan tertentu menggunakan directed graph.
• Contoh: urutan mata kuliah prerequisite untuk mendapat gelar sarjana matematika (Algebra → Advanced Algebra → Senior Seminar).

3. Konektivitas Directed Graph

• Menelusuri vertex dari awal hingga tidak bisa lanjut, tuliskan rangkaiannya.
• Contoh graph 5 vertex (A,B,C,D,E):
  • A → C → selesai = AC
  • B → A → C → selesai, B → E → C → selesai (C ditulis 1x) = BACE
  • C → tidak ada keluar = C
  • D → E → C = DEC
  • E → C = EC

E. Tipe Data Abstrak (ADT) Graph

1. Operasi ADT Graph

• numVertices(): jumlah vertex pada graph.
• vertices(): iterasi seluruh vertex.
• numEdges(): jumlah edge pada graph.
• edges(): iterasi seluruh edge.
• getEdge(u,v): mengembalikan edge dari u ke v (null jika tidak ada).
• endVertices(e): mengembalikan array dua vertex ujung edge.
• opposite(v,e): mengembalikan vertex lain pada edge e yang berelasi dengan v.
• outDegree(v): jumlah edge keluar dari v.
• inDegree(v): jumlah edge masuk ke v.
• outgoingEdges(v): iterasi semua edge keluar dari v.
• incomingEdges(v): iterasi semua edge masuk ke v.
• insertVertex(x): buat vertex baru dengan elemen x.
• insertEdge(u,v,x): buat edge baru dari u ke v dengan elemen x.
• removeVertex(v): hapus vertex v dan semua edge terkait.
• removeEdge(e): hapus edge e dari graph.