Apa itu graph? Graph adalah struktur data non-linear yang terdiri dari dua komponen utama yaotu vertex (simpul) dan edge (sisi). Vertex mewakili objek dan edge menggambarkan hubungan antar objek tersebut. Dalam pemrograman, graph digunakan untuk menggambarkan sistem yang kompleks dan memiliki banyak relasi. Graph dapat mengandung ratusan hingga ribuan simpul dan hubungan, tergantung kompleksitas sistem yang ada.

Beberapa istilah penting yang perlu dipahami dalam graph:

• Vertex (V): titik atau simpul yang mewakili objek.
• Edge (E): garis atau panah yang menghubungkan dua simpul.
• Degree: jumlah sisi yang terhubung ke sebuah simpul.
• Path: urutan simpul yang dilalui dari satu vertex ke vertex lain.
• Cycle: lintasan yang kembali ke simpul asal.
• Adjacent: dua vertex yang langsung terhubung oleh satu edge.
• Connected: kondisi dimana dua simpul dapat dijangkau satu sama lain.

Graf dapat dianalogikan seperti peta jalan. Setiap titik kota di peta adalah vertex, dan garis jalan antar kota adalah edge. Jika jalan ada dua arah maka mewakili graph tak berarah. Jika hanya satu arah berarti graph berarah.

Representasi Graph

1. Adjacency Matrix

Adjacency martiks merepresentasikan graph dalam bentuk matirks dua dimensi. Jika terdapat edge antar matirks maka nilainya adalah 1. Dan jika tidak ada edge, maka nilai tersebut adalah 0.

Kelebihan dan kekurangan:

• Sangat cepat untuk mengecek apakah ada edge antara dua simpul (vertex).
• Mudah diimplementasikan dan digunakan untuk graf kecil atau padat.
• Boros memori karena menggunakan ruang besar, bahkan untuk graf yang sparse (jarang edge)
• Iterasi tetangga dari satu simpul membutuhkan traversal satu baris penuh.

2. Adjacency List

Adjacency list menyimpan daftar tetangga dari setiap simpul. Setiap node menyimpan daftar node lainnya yang terhubung.

Kelebihan dan kekurangan:

• Hemat memori, terutama untuk graf sparse, karena hanya menyimpan edge yang benar-benar ada.
• Lebih efisien untuk iterasi tetangga simpul karena hanya perlu menelusuri list yang relevan.
• Fleksibel untuk graf berukuran besar atau struktur yang dinamis.
• Mengecek apakah dua simpul saling terhubung membutuhkan pencarian (O(k), dengan k = panjang list).
• Kurang cocok untuk operasi yang membutuhkan akses langsung antar simpul secara cepat.

Jenis-Jenis Graph

1. Berdasarkan arah sisi (directed vs undirected)

• Directed graph (graf berarah) adalah graf yang setiap edge-nya memiliki arah tertentu. Ditunjukkan dengan panah dari satu simpul ke simpul lain. Contohnya adalah hubungan 'mengikuti' di media sosial.
• Undirected graph (graf tak berarah) adalah graf yang tidak memiliki arah pada edge. Hubungan antara dua simpul bersifat dua arah seperti hubungan pertemanan.

2. Berdasarkan bobot sisi (weighted vs unweighted)

• Weighted graph memiliki nilai / bobot di setiap edge. Bobot bisa berupa jarak, biaya, waktu, ataupun kapasitas. Struktur ini digunakna dalam pencarian jalur terpendek atau optimasi biaya.
• Unweighted graph menganggap semua edge bernilai sama. Struktur ini digunakan ketika nilai hubungan antar simpul tidak relevan atau tidak dibutuhkan.

3. Berdasarkan keberadaan siklus (cyclic vs acyclic)

• Cyclic graph memiliki satu atau lebih jalur tertutup atau siklus yang kembali ke simpul asal. Siklus ini bisa mencerminkan proses berulang.
• Acyclic graph tidak mengandung siklus. Graph yang berarah dan tidak memiliki siklus disebut Directed Acyclic Graph (DAG) yang banyak digunakan untuk menjelaskan urutan dependensi dalam proyek.

4. Berdasarkan keterhubungan (connected vs disconnected)

• Connected graph adalah graph dimana semua simpul dapat dijangkau dari simpul lainnya, baik secara langsung maupun melalui jalur tertentu.
• Disconnected graph memiliki satu atau lebih simpul yang tidak dapat dijangkau simpul lain.

Traversal pada Graph

Traversal (penelusuran) yaitu proses mengunjungi setiap simpul dalam graph untuk mengevaluasi, memproses, atau mengakses informasi yang tersimpan. Dalam menelusuri simpul, traversal memperlukan strategi tertentu karena graph bukan struktur linear. Strategi yang sering digunakan yaitu Breadth First Search (BFS) dan Depth First Search (DFS).

BFS menelusuri simpul yang berada di level yang sama terlebih dahulu sebelum lanjut ke level selanjutnya. BFS menggunakan queue untuk menyimpan simpul yang akan dikunjungi. Simpul pertama yang ditemukan akan diproses terlebih dahulu, kemudian tetangganya dimasukkan ke queue. Proses ini berulang hingga semua simpul terkunjungi. Di sisi lain DFS bekerja menelusuri satu cabang sedalam mungkin sebelum kembali dan melanjutkan ke cabang lain. Perbedaan antara BFS dan DFS terletak pada urutan eksplorasi, BFS menjelajah secara menyebar, mendahulukan simpul tetangga. Sedangkan DFS menyelam dalam ke satu arah sampai mentok, baru kembali ke atas.

Pemilihan metode tergantung pada kebutuhan aplikasi. Jika tujuannya untuk menemukan jalan pendek, maka gunakan BFS. Namun jika ingin mengeksplor seluruh kemungkinan gunakan DFS.

Praktikum

1. Representasi graf dengan adjacency list

#Membuat graph tak berarah menggunakan adjacency list
graph = {
    'A': ['B', 'C'], #node A terhubung dengan node B dan C
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

#Menampilkan graph
def print_graph(graf):
  for node in graf:
    print(f'{node} -> {graf[node]}')

print_graph(graph)

Penjelasan: Graf didefinisikan sebagai dictionary. Di mana setiap simpul menyimpan nilai yang terhubung dengannya. Fungsi print_graph digunakan untuk mencetak seluruh hasil graph.

2. Traversal Graf menggunakan BFS

from collections import deque #mengimpor deque untuk membuat antrian

def bfs(graph, start):
  visited = set() #menyimpan simpul yang telah dikunjungi agar tidak berulang
  queue = deque([start])

  while queue:
    vertex = queue.popleft() #fungsi mengambil simpul terdepan
    if vertex not in visited: #mengecek simpul apakah sudah pernah dikunjungi
      print(vertex, end=' ') #menampilkan node
      visited.add(vertex) #menandai node yang sudah dikunjungi
      queue.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])

#Contoh pemanggilan
bfs(graph, 'A')

Penjelasan: deque digunakan untuk efisiensi antrian. Fungsi diatas mencetak urutan kunjungan dari simpul paling awal.

3. Traversal Graf menggunakan DFS

def dfs(graph, start, visited=None):
  if visited is None: #jika belum ada data yang dikunjungi, maka set kosong 
    visited = set() #mencegah kunjungan berulang

  if start not in visited:
    print(start, end=' ') #menampilkan node
    visited.add(start) #menandai node yang sudah dikunjungi
    for neighbor in graph[start]:
      dfs(graph, neighbor, visited)

#Contoh pemanggilan
dfs(graph, 'A') #menjalankan DFS mulai dari node 'A'

Penjelasan: DFS menggunakan rekursi untuk menjelajahi simpul. Fungsi mencetak simpul sesuai urutan DFS.

4. Latihan Personal

#Lengkapi fungsi untuk menghitung jumlah tetangga dari tiap simpul dalam graph

def count_neighbors(graph):
  result = {}
  for node in graph:
    #hitung jumlah tetangga
    result[node] = len(graph[node])
  return result #hasilnya disimpan ke result

#Contoh pemanggilan
print(count_neighbors(graph))

Penjelasan: Fungsi count_neighbors() merupakan fungsi untuk menghitung jumlah tetangga dari setiap simpul. Program melakukan perulangan pada setiap node, lalu menggunakan len() untuk menghitung banyaknya tetangga yang terhubung pada node tersebut. Hasilnya disimpan ke dalam dictionary result lalu ditampilkan menggunakan print().

Tugas

1. Buatlah graf tak berarah baru dengan minimal 5 simpul dan 7 sisi, lalu tampilkan dengan fungsi print_graph.
2. Implementasikan BFS dan DFS dari simpul awal pilihan anda.
3. Modifikasi fungsi BFS agar mengembalikan list urutan kunjungan, bukan hanya mencetak.
4. Buat fungsi find_path(graph, start, end) yang mengembalikan satu jalur dari start ke end jika ada, menggunakan DFS.
5. Tambahkan fungsi is_connected(graph) untuk mengecek apakah semua simpul dalam graf saling terhubung (gunakan kombinasi DFS + logika).

#1. Membuat graf tak berarah dengan adjacency list
graph = {
    'A': ['B', 'C', 'E'], #node A terhubung dengan node B, C, dan E
    'B': ['A', 'D'],
    'C': ['A', 'F'],
    'D': ['B', 'D'],
    'E': ['A', 'F'],
    'F': ['C', 'D', 'E']
}

#Menampilkan graph
def print_graph(graf):
  for node in graf:
    print(f'{node} -> {graf[node]}')

print_graph(graph)


#2. BFS
from collections import deque #mengimpor deque untuk membuat antrian

def bfs(graph, start):
  visited = set() #menyimpan simpul yang telah dikunjungi agar tidak berulang
  queue = deque([start])

  while queue:
    vertex = queue.popleft() #fungsi mengambil simpul terdepan
    if vertex not in visited: #mengecek simpul apakah sudah pernah dikunjungi
      print(vertex, end=' ') #menampilkan node
      visited.add(vertex) #menandai node yang sudah dikunjungi
      queue.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])

#Contoh pemanggilan
print('\nHasil BFS: ')
bfs(graph, 'A')

#DFS
def dfs(graph, start, visited=None):
  if visited is None: #jika belum ada data yang dikunjungi, maka set kosong
    visited = set() #mencegah kunjungan berulang

  if start not in visited:
    print(start, end=' ') #menampilkan node
    visited.add(start) #menandai node yang sudah dikunjungi
    for neighbor in graph[start]:
      dfs(graph, neighbor, visited)

#Contoh pemanggilan
print('\nHasil DFS: ')
dfs(graph, 'A') #menjalankan DFS mulai dari node 'A'


#3. Modifikasi BFS agar mengembalikan list
def bfs_list(graph, start):
  visited = set() #node yang sudah dikunjungi disimpan disini
  queue = deque([start])
  result = [] #urutan kunjungan disimpan ke result

  while queue:
    vertex = queue.popleft()
    if vertex not in visited:
      visited.add(vertex)
      result.append(vertex)
      queue.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])

  return result #mengembalikan hasil akhir

print('\nBFS dalam bentuk list: ')
print(bfs_list(graph, 'A'))


#4. Membuat fungsi find_path menggunakan DFS yang mengembalikan satu jalur dari start ke end
def find_path(graph, start, end, path=[]):
  path = path + [start] #menambahkan node yang sedang dikunjungi 
  if start == end: #jika node awal sama dengan tujuan, jalur dikembalikan
    return path
  for neighbor in graph[start]: #perulangan ke semua tetangga
    if neighbor not in path: #mengecek agar node yang sama tidak dikunjungi ulang
      new_path = find_path(graph, neighbor, end, path)
      if new_path:
        return new_path
  return None

print('\nJalur dari start ke end: ')
print(find_path(graph, 'A', 'F'))

#5. Mengecek apakah semua simpul dalam graf saling terhubung
def is_connected(graph):
  visited = set()

  def dfs_check(node): #fungsi dfs untuk penelusuran
    visited.add(node)
    for neighbor in graph[node]:
      if neighbor not in visited:
        dfs_check(neighbor)

  start_node = list(graph.keys())[0] #mengambil satu node awal dari graph
  dfs_check(start_node) #menjalankan dfs mulai dari node awal

#mengecek apakah jumlah node yang dikunjungi sama dengan jumlah seluruh node pada graph.
  return len(visited) == len(graph) 

print('\nApakah semua simpul dalam graf saling terhubung?')
print(is_connected(graph))

And yap! that's all untuk materi kali ini, thanks for reading and see u next week!

Github: https://github.com/Rosifaaulia/Praktikum-Struktur-Data.git