Graph adalah struktur data non-linear yang terdiri dari dua komponen utama: vertex(simpul) dan edge(sisi). Vertex mewakili entitas atau objek, sementara edge menggambarkan hubungan antar objek tersebut. Dalam pemrograman, graph digunakan untuk memodelkan sistem yang kompleks dengan banyak relasi, seperti jaringan sosial, koneksi jaringan komputer, sistem jalan, atau rute penerbangan.

Graph ditulis sebagai G = (V, E) dengan V sebagai vertex atau simpul dan E sebagai edge atau sisi penghubung. Edge dapat berupa undirected untuk hubungan dua arah atau directed untuk hubungan satu arah. Beberapa istilah 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 di mana dua simpul dapat dijangkau satu sama lain.

Representasi Graph

Representasi graph digunakan agar graph dapat diproses dan dimanipulasi dalam program komputer. Dua bentuk representasi graph yang paling umum adalah adjacency matrix dan adjacency list.

Adjacency Matrix

Adjacency matrix merepresentasikan graph dalam bentuk matriks n x n, di mana nilai 1 menunjukan adanya hubungan antar simpul dan 0 berarti tidak ada hubungan.

Kelebihan:

• Pengecekan hubungan antar simpul lebih cepat.
• Mudah diimplementasikan dan dipahami.

Kekurangan:

• Boros memori karena membutuhkan ruang besar.
• Pencarian tetangga simpul kurang evisien.

Adjacency List

Adjacency list menyimpan daftar tetangga dari setiap simpul dalam bentuk list atau dictionary. Representasi ini lebih cocok untuk graph sparse karena hanya menyimpan edge yang ada.

Kelebihan:

• Lebih hemat memori.
• Efisien untuk menelusuri tetangga satu ismpul.
• Cocok digunakan pada graph besar dan dinamis.

Kekurangan:

• Pengecekan hubungan antar simpul lebih lambat karena perlu pencarian.
• Kurang cocok untuk akses langsung yang cepat.

Jenis-Jenis Graph

1. Berdasarkan Arah Sisi

• Directed Graph merupakan graph yang memiliki arah pada setiap edge, seperti hubungan follow di media sosial atau aliran proses.
• Undirected Graph tidak memiliki arah sehingga hubungan antar simpul bersifat dua arah, seperti pertemanan atau koneksi jaringan.

2. Berdasarkan Bobot Isi

• Weighted Graph memiliki bobot pada edge, misalnya jarak, waktu, dan biaya.
• Unweighted Graph tidak menggunakan bobot sehingga semua edge dianggap sama.

3. Berdasarkan Siklus

• Cyclic Graph memungkinkan semua simpul saling terhubung melalui jalur tertentu.
• Disconnected Graph memiliki simpul yang tidak dapat dijangkau dari simpul lain.

Traversal pada Graph

Traversal pada graph merupakan proses mengunjungi setiap simpul untuk mengakses atau memproses data. Graph berstruktur linear, maka dari itu diperlukan metode khusus agar simpul dapat ditelusuritanpa terjebak dalam siklus. Metode traversal yang sering digunakan adalah BFS untuk menelusuri graph berdasarkan level terdekat menggunakan queue sehingga cocok untuk mencari jalur terpendek. DFS untuk menelusuri satu jalur secara mendalam sebelum kembali ke cabang seblumnya.

Penjabaran Praktikum

Representasi Graph dengan Adjacency List

Dalam Python, graph dapat dipresentasikan menggunakan dictionary yang berisi daftar adjacency dari setiap simpul, seperti contoh penggunaan kode:

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


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


print_graph(graph)

Fungsi print_graph() digunakan untuk menampilkan isi graph ke layar. Fungsi tersebut melakukan perulangan pada setiap simpul lalu mencetak nama simpul beserta daftar lainnya.

Traversal Graph Menggunakan BFS

Breadth-First Search menjelajahi graph secara level demi level, dimulai dari simpul awal, kemudian mengunjungi simpul tetangganya, seperti contoh kode program:

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')

Fungsi bfs(graph, start) dimulai dengan visited untuk menyimpan simpul yang sudah dikunjungi dan queue untuk antrian simpul yang belum tersentuh. Sementara fungsi bfs(graph, 'A') untuk memunculkan output yang dimulai dari simpul A. Bentuk utuh outpu -> A, B, C, D, E, F.

Traversal Graph Menggunakan DFS

Depth-First Search (DFS) menelusuri graf dengan cara menyelam sedalam mungkin ke satu jalur sebelum menelusuri cabang arus lainnya. Contong penggunaan kode:

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')

Dimulai dari fungsi dfs() memakai rekrusi untuk mengunjungi setiap simpul dan visited untuk menyimpan cabang yang sudah dikunjungi. Saat fungsi dfs(graph, 'A') dijalankan, traversal dimulai dari ismpul A, lalu menelusuri satu jelur terdalam sebelum menelusuri jalur lainnya sehingga menghasilkan output utuh -> A, B, D, E, F, C.

Latihan personal

# Fungsi untuk menghitung jumlah tetangga dari tiap simpul dalam graph
def count_neighbors(graph):
    result = {}
    for node in graph:
        result[node] = len(graph[node])
    return result

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

# Menampilkan hasil
hasil = count_neighbors(graph)
print(hasil)

Fungsi count_neighbors() untuk menghitung jumlah tetangga dari setiap simpul dalam graph, panjang list akan dihitung menggunakan fungsi len(graph[node]). Hasilnya akan ditampilkan menggunakan print(hasil) seperti di samping -> {'A': 2, 'B': 3, 'C': 2, 'D': 1}

Tugas

Mahasiswa diberikan tugas untuk membuat sebuah program dengan beberapa ketentuan seperti berikut:

1. Buatlah graf tak berarah baru dengan minimal 5 simpul dan 7 sisi, lalu tampilkandengan fungsi print_graph.
2. Implementasikan BFS dan DFS dari simpul awal pilihan Anda.
3. Modifikasi fungsi BFS agar mengembalikan list urutan kunjungan, bukan hanyamencetak.
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).

from collections import deque

# Membuat graph tak berarah

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

# Fungsi untuk menampilkan graph

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

# BFS (mengembalikan list urutan kunjungan)

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

    while queue:
        node = queue.popleft()

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

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

    return order

# DFS

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

    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Mencari jalur menggunakan DFS

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

    path = path + [start]

    if start == end:
        return path

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

            if new_path:
                return new_path

    return None

# Mengecek apakah graph terhubung

def is_connected(graph):
    start_node = next(iter(graph))
    visited = set()

    def dfs_visit(node):
        visited.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs_visit(neighbor)

    dfs_visit(start_node)

    return len(visited) == len(graph)

# Program Utama

# Menampilkan graph
print_graph(graph)

# BFS
print("\nHasil BFS dari simpul A:")
print(bfs(graph, 'A'))

# DFS
print("\nHasil DFS dari simpul A:")
dfs(graph, 'A')

# Cari jalur
print("\n\nJalur dari A ke E:")
print(find_path(graph, 'A', 'E'))

# Cek konektivitas
print("\nApakah graf terhubung?")
print(is_connected(graph))

Fungsi utama pada program di atas yaotu bfs() dan dfs(), fungsi find_path() digunakan untuk mencari jalur dari satu simpul ke simpul lain menggunakan DFS, serta is_connected() digunakan untuk mengecek apakah seluruh simpul dalam graph saling terhubung. Pada program utama, semua fungsi dijalankan untuk menampilkan hasil traversal BFS dan DFS. Output utuh dari program di atas seperti berikut.

Sekian penjabaran mengenai graph dan implementasinya ke dalam python, semoga dapat dimengerti. Adios!

github: https://github.com/dhyazka12-gif/praktikum-basis-data.git