Struktur Data: Graph

Halo teman-teman! Gimana kabarnya nih? Semoga selalu diberi kesehatan dan keselamatan ya. Kali ini struktur data yang akan dibahas adalah GRAPH. Graph merupakan struktur data non-linear yang terdiri dari dua komponen utama: vertex (simpul) dan edge (sisi).

Beberapa istilah penting dalam graph:

• Vertex (V): titik atau simpul 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 di mana dua simpul dapat dijangkau satu sama lain.

Representasi Graph

Representasi graph bertujuan agar grapdh dapat digunakan secara efektif dalam program komputer.

1. Adjacency Matrix

Merepresentasikan graph dalam bentuk matriks dua dimensi berukuran n x n, di mana n adalah jumlah vertex. Jika terdapat edge dari vertex i ke j, maka matrik[i][j] = 1. Jika tidak ada edge, maka nilai tersebut adalah 0. Contoh:

Setiap baris dan kolom mewakili simpul, dan isi sel menunjukkan hubungan antar simpul.

Kelebihan dari adjacency matrix yaitu sangat cepat untuk mengecek apakah ada edge antara dua simpul (kompleksitas O(1)) dan mudah diimplementasikan dan digunakan untuk graf kecil atau padat. Kekurangannya sendiri yakni boros memori karena menggunakan ruang sebesar O(n²), bahkan untuk graph yang sparse (jarang edge) dan iterasi tetangga dari satu simpul membutuhkan transversal satu baris penuh.

2. Adjacency List

Menyimpan daftar tetangga dari setiap simpul dan biasanya direpresentasikan sebagai dictionary atau list of lists, di mana setiap key atau indeks menyimpan list dari vertex yang terhubung dengannya. Contoh:

Kelebihan dari adjcency list sendiri yaitu hemat memori pada graph space karena menyimpan edge yang benar-benar ada, lebih efisien untuk iterasi tetanggga simpul dan fleksibel untuk graph berukuran besar atau struktur yang dinamis. Kekurangannya sendiri yaitu ketika mengecek dua simpul saling terhubung shingga memerlukan pencarian (O(k), k = panjang list) dan kurang cocok unttuk operasi yang membutuhkan akses langsung antar simpul secara cepat.

Jenis-Jenis Graph

1. Berdasarkan Arah Sisi

• Directed graph (graf berarah), setiap edge memiliki arah tertentu ditunjukkan dengan panah dari satu simpul ke simpul lain.
• Undirected graph (graf tak berarah), tidak memiliki arah pada edge, hubungan dua simpul bersifat dua atah atau timbal balik.

2. Berdasarkan Bobot Sisi

• Weighted graph, memiliki nilai atau bobot (jarak, biaya, waktu atau kapasitas) pada setiap edge.
• Unweighted graph, menganggap semua edge bernilai sama digunakan ketika nilai hubungan antar simpul tidak relevan atau tidak dibutuhkan.

3. Berdasarkan Keberadaan Siklus

• Cyclic graph, memiliki satu atau lebih jalur tertutup, atau siklus, yang kembali ke simpul awal dan mencerminkan proses berulang.
• Acyclic graph, tidak mengandung siklus. Jika bersifat berarah dan tidak memiliki siklus, maka disebut Directed Acyclic Graph (DAG).

4. Berdasarkan Keterhubungan

• Connected graph, semua simpul dapat dijangkau dari simpul lainnya, secara langsung atau melalui jalur tertentu.
• Disconnected graph, satu atau lebih simpul yang tidak dapat dijangkau dari simpul lain. Dalam analisis jaringan, bagian yang terpisah ini sering dianggap sebagai komponen terhubung (connected components) yang berdiri sendiri.

Transversal pada Graph

Transversal atau penelusuran merupakan proses mengunjungi setiap simpul dalam graph untuk mengevaluasi, memproses, atau mengakses informasi yang tersimpan. Terdapat dua strategi transversal yaitu Breadth First Search (BFS) dan Depth First Search (DFS).

BFS bekerja dengan menelusuri simpul-simpul yang berada di level yang sama terlebih dahulu kemudian level berikutnya dengan menggunakan queue untuk menyimpan simpul yang dikunjungi.

DFS bekerja dengan menelusuri satu cabang sedalam mungkin sebelym kembali (backtrack) dan melanjutkan ke cabang lain yang biasanya diimplementasikan menggunakan rekursi atau stack. Berguna pada kasus yang membutuhkan eksplorasi menyeluruh.

PRAKTIKUM

1. Representasi Graf dengan Adjacency List

# Graf tak berarah adjecency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['E', 'F'],
    'F': ['C', 'E']
}

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

print_graph(graph)

# Output
A -> ['B', 'C']
B -> ['A', 'D', 'E']
C -> ['A', 'F']
D -> ['B']
E -> ['E', 'F']
F -> ['C', 'E']

Penjelasan:

• Graph tak berarah diatas menggunakan dictionary atau kamus dalam python dengan simpul atau node sebagai kuncinya dan daftar node yang terhubung langsung sebagai value. Contohnya ‘A’: [‘B’, ‘C’] artinya node A terhubung ke B dan C.
• Fungsi print_graph berguna untuk menampilkan isi dari adjenceny list graf. Baris for digunakan untuk menelusuri semua node yang kemudian akan dicetak node dan tetangganya sesuai format yang ada pada perintah print.
• Pemanggilan fungsi print_graph(graph) dengan graf yang telah didefinisikan untuk mencetak struktur graf ke layar.
• Output akan menampilkan hasil sesuai dengan kode program yang dijalankan.

2. Transversal Graf menggunakan BFS

from collections import deque

def bfs(graph, start):
  visited = set()
  queue = deque([start])

  while queue:
    vertex = queue.popleft()
    if vertex not in visited:
      print (vertex, end=" ")
      visited.add(vertex)
      queue.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])

#Contoh pemanggilan
bfs(graph, 'A')

# Output
A B C D E F 

Penjelasan:

• Import deque dari modul collections digunakan sebagai struktur antrian (queue) karena lebih efisien dibandingkan list saat pop dari depan.
• Fungsi bfs(graph, start) dengan set visited untuk menyimpan node yang sudah dikunjungi dan queue untuk menyimpan node yang akan dikunjungi berikutnya.
• Lalu pada proses transversal BFS akan dijalankan selama antrian tidak kosong dengan vertex = queue.popleft() untuk mengambil node dari depan antrian. Jika node belum dikunjungi maka node akan ditampilkan, kemudian ditandai sebagai sudah dikuunjungi oleh visited.add(vertex) dan tetangga yang belum dikunjungi akan ditambahkan ke antrian (queue.extend([…])).
• Pemanggilan fungsi bfs(graph, ‘A’) akan memulai BFS dari node ‘A’.
• Outputnya akan menampilkan urutan BFS berdasarkan level.

3. Transversal Graf menggunakan DFS

def dfs(graph, start, visited=None):
  if visited is None:
    visited = set()

  if start not in visited:
    print(start, end=" ")
    visited.add(start)
    for neighbor in graph[start]:
      dfs(graph, neighbor, visited)

# Contoh pemanggilan
dfs(graph, 'A')

# Output
A B D E F C 

Penjelasan:

• Fungsi DFS untuk melakukan Depth First Search pada garph dengan parameter garph yang akan diisi dengan data graf, start yang merupakan titik awal dari mana DFS akan dimulai dan visited=None yang digunakan untuk menyimpan node-node yang sudah dikunjungi, agar tidak dikunjungi berulang.
• Set visited untuk menyimpan node yang sudah dikunjungi supaya tidak dikunjungi ulang dan mencegah loop tak berujung.
• Inti DFS pada pengecekan node start yang belum pernah dikunjungi akan melakukan rekursi DFS ke semua tetangga node start yang belum dikunjungi dengan menjelajahi sedalam mungkin ke satu cabang sebelum pindah ke cabang lain.
• Kemudian fungsi DFS akan dipanggil dari node A dan mencetak sesuai urutannya.

4. Latihan Personal

Kode Program:

def count_neighbors(graph):
  result = {}
  for node in graph:
    result[node] = len(graph[node])
  return result

# Pemanggilan
neighbors_count = count_neighbors(graph)
print(neighbors_count)

# Output
{'A': 2, 'B': 3, 'C': 2, 'D': 1, 'E': 2, 'F': 2}

Penjelasan:

• Fungsi count_neighbors untuk menghitung tetangga dari setiap simpul dengan parameter graf.
• Dictionary kosong bernama result yang akan diisi dengan pasangan node: count_neighbors.
• Perulangan akan melakukan loop ke setiap simpul dalam graf.
• Untuk menghitung panjang tetangga yang akan masuk ke dalam dictionary result menggunakan len(graph[node]) yang berguna menghitung berapa banyak node yang terhubung ke simpul tersebut.
• Ketika node telah diproses hasilnya akan dikembalikan sebagai hasil fungsi.
• Pemanggilan fungsi count_neighbors dipanggil dengan data graph kemudian hasilnya disimpan pada variabel neighbors_count. Lalu hasilnya dicetak.

Jadi, menghitung panjang daftar tetangga cukup menggunakan dungsi bawaan python yaitu len(graph[node]).

TUGAS

1. Buatlah graf tak berarah baru dengan minimal 5 simpul dan 7 sisi, lalu tampilkan dengan fungsi print_graph.

Kode Program:

Output:

Penjelasan:

graph = { 
    'A': ['B', 'C', 'D'],    
    'B': ['A', 'D', 'E'],
    'C': ['A', 'E', 'D'],   
    'D': ['B', 'A', 'C'],
    'E': ['B', 'C']
}

• Inisialisasi graph yang merupakan graf yak berarah dengan 5 simpul (A-E) dan lebih dari 7 sisi, sehingga memenuhi syarat soal poin 1.

def print_graph(graph):
    for node in graph:
        print(f"{node}: {graph[node]}")

• Fungsi print_graph akan mencetak isi graf dengan format Sumpul: Daftar Tetangga. Sesuai untuk melihat struktur graf.

print_graph(graph)

• Pemanggilan fungsi untuk menampilkan struktur graf sebagai output.

2. Implementasikan BFS dan DFS dari simpul awal pilihan Anda.

Kode program:

Output:

Penjelasan:

from collections import deque

• deque digunakan untuk membuat antrian BFS lebih efisien.

Fungsi BFS

def bfs(graph, start):
    visited = set()
    queue = deque([start])

• Set visited digunakan untuk menyimpan simpul yang sudah dikunjungi, agar tidak dikunjungi lagi.
• Antrian simpul yang akan dikunjugi mulai dari simpul awal akan disimpan dalam queue.

    while queue:
        node = queue.popleft()

• Akan mengambil simpul depan jika antrian tidak kosong.

        if node not in visited:
            print(node, end=' ')
            visited.add(node)

• Ketika simpul belum dikunjungi maka nama simpul akan dicetak dan ditandai sebagai simpul yang sudah dikunjungi.

            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

• Akan menambahakan tetangga dari node ke antrian jika belum dikunjungi.

Fungsi DFS

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

• Fungsi DFS ini bersifat rekursif. Jika belum dikunjungi mana akan membuat set kosong untuk menyimpan simpul yang dikunjungi.

    if start not in visited:
        print(start, end=' ')
        visited.add(start)

• Akan mengunjungi simpul start jika belum dikunjungi, kemudian simpul akan dicetak dan ditandai sudah dikunjungi.

bfs(graph, 'A')

• Memanggil fungsi yang akan memulai penelusuran BFS dari simpul awal.

3. Modifikasi fungsi BFS agar mengembalikan list urutan kunjungan, bukan hanya mencetak.

Kode Program:

Output:

Penjelasan:

def bfs_list(graph, start):
    visited = set()
    queue = deque([start])
    result = []

• Fungsi BFS untuk mengembalikan list urutan simpul yang dikunjungi dan dimulai dari start.
• Set visited digunakan untuk menyimpan simpul yang sudah dikunjungi, untuk mencegak pengunjungan sebanyak dua kali.
• Antrian simpul yang akan dikunjungi disimpan pada queue.
• result berisi list kosong untuk menyimpan urutan kunjungan simpul selama BFS berlangsung.

Proses BFS

    while queue:
        node = queue.popleft()

• Selama queue tidak kosong, simpul pertama dalam antrian akan diambil.

        if node not in visited:
            visited.add(node)
            result.append(node)

• Jika simpul belum dikunjungi maka akan akan ditandai sebagai sudah dikunjungi dan hasilnya akan disimpan dalam urutan kunjungan (result).

            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

• Akan menambahkan tetangga dari node ke antrian jika belum dikunjungi.

    return result

• Mengembalikan semua simpul jika sudah selesai dikunjungi sesuai urutan sebagai list.

print("BFS List:", bfs_list(graph, 'A'))

• Memanggil fungsi BFS dari simpul A, lalu mencetaknya.

4. Buat fungsi find_path(graph, start, end) yang mengembalikan satu jalur dari start ke end jika ada, menggunakan DFS.

Kode program:

Output:

Penjelasan:

def find_path(graph, start, end, path=None):
    if path is None:
        path = []
    path = path + [start]

• Mendefisinikan fungsi find_path, path merupakan list yang menyimpan jalur yang sedang dibentuk.
• Untuk path pada awalnya dibuat list kosong karena belum terdapat isinya.
• Start ditambah ke dalam path yang merupakan posisi simpul tersebut saat ini.

    if start == end:
        return path

• Jika simpul sekarang (start) merupakan tujuan (end), maka akan dikembalikan jalur yang ditemukan tersebut. Jalur dari start ke end sudah lengkap.

    for neighbor in graph[start]:
        if neighbor not in path:
            new_path = find_path(graph, neighbor, end, path)
            if new_path:
                return new_path

• Menelusuri semua tetangga dari simpul sekarang. Apabila tetangga belum ada di path, akan memanggil find_path() lagi secara rekursif. Jika hasil new_path ditemukan, langsung kembalikan jalurnya pada jalur pertama yang ditemukan.

    return None

• Ketika semua tetangga telah dikunjungi namun tidak menemukan end, maka tidak ada jalur dari start ke end.

print("Path A ke E:", find_path(graph, 'A', 'E'))

• Memanggil fungsi find_path untuk mencari jalur dari simpul A ke E kemudian mencetaknya.

5. Tambahkan fungsi is_connected(graph) untuk mengecek apakah semua simpul dalam graf saling terhubung (gunakan kombinasi DFS + logika).

Kode program:

Output:

Penjelasan:

def is_connected(graph):
    visited = set()

• Fungsi is_connected dan set visited digunakan untuk menyimpan simpul yag sudah dikunjungi.

    def dfs(node):
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                dfs(neighbor)

• Fungsi DFS rekursif digunakan untuk menelusuri semua simpul yang bisa dicapai dari node. Semua tetangga juga akan ditelusuri secara menyeluruh.

    start_node = next(iter(graph))
    dfs(start_node)

• Akan mengambil satu simpul awal secara acak dari graf kemudian DFS akan dimulai dari simpul tersebut.

    return len(visited) == len(graph)

• Setelah DFS selesai akan menyamakan jumlah simpul yang dikunjungi dengan total simpul. Jika sama, artinya semua simpul bisa dijangkau yang menandakan graf terhubung.

print("Apakah graf terhubung?:", is_connected(graph))

• Mengeksekusi fungsi dan mencetak hasilnya. Apabila graf terhubung akan menampilkan True dan False ketika graf tidak terhubung.

Graf tak berarah bisa direpresentasikan dengan struktur data dictionary yang menyimpan daftar tetangga tiap simpul. Dengan algoritma BFS dan DFS, kita bisa menelusuri simpul-simpul tersebut secara teratur. Fungsi pencarian jalur digunakan untuk melihat apakah dua simpul saling terhubung, sementara fungsi konektivitas memastikan semua simpul bisa dijangkau dari simpul mana pun. Pemahaman dasar ini berguna saat membangun sistem yang melibatkan hubungan antar elemen, misalnya dalam jaringan komputer atau peta lokasi.

Link Latihan:

[embed]praktikumsemester2_strukturdata/2410506008_Strukdat_Graph.ipynb at main ·… Contribute to Rahma-dwi-kartika-sari/praktikumsemester2_strukturdata development by creating an account on GitHub.github.com

Link Tugas:

[embed]praktikumsemester2_strukturdata/2410506008_Tugas_Strukdat_Graph.ipynb at main ·… Contribute to Rahma-dwi-kartika-sari/praktikumsemester2_strukturdata development by creating an account on GitHub.github.com

REFERENSI:

Wardhani, O., & Alfath, I. (2024/2025). Modul Praktikum Struktur Data: Graph. Universitas Tidar.