author Ahmad Muhardian

Cara Membuat Graf pada Python


Hari ini saya belajar sesuatu yang cukup menantang, yaitu graf. Bagaiaman menulis graf dalam kode? dan memahami beberapa hal tentang graf.

Menurut Wikipedia, graf dalam komputer sains (ilmu komputer) adalah sebuah tipe data abstrak. Graf terdiri dari titik-titik (nodes) yang terhubung dengan sisi/busur (edge/arcs).1

Berikut ini contoh graf yang akan kita tulis dalam kode program python:

Graph yang akan dibuat ke dalam coding

Graf tersebut merupakan graf berarah yang memiliki enam buah titik dan delapan busur (arcs). Adapun delapan busur tersebut bisa kita nyatakan seperti berikut ini.

A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C

Graf sebenarnya bisa diubah ke dalam bentuk matriks dan ditulis dalam bentuk array dua dimensi ke dalam kode. Namun, karena contoh yang saya temukan menggunakan dictionary, maka graf di atas bisa dituliskan seperti berikut ini.

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

Pada kode di atas, kita menggunakan dictionary untuk membuat graf dan menggunakan list untuk menyimpan titik yang menjadi tetangga sebuah titik. Misalkan titik A, terbuhung dengan titik B dan C. Titik B terhubung dengan titik C dan D, dan seterusnya.

Fungsi untuk Menentukan Jalur

Fungsi ini akan menemukan sebuah jalur (path) dari titik awal hingga titik akhir atau tujuan.

def temukan_jalur(graf, awal, akhir, jalur=[]):
    jalur = jalur + [awal]
    if awal == akhir:
        return jalur
    if not graf.has_key(awal):
        return None
    for titik in graf[awal]:
        if titik not in jalur:
            jalur_baru = temukan_jalur(graf, titik, akhir, jalur)
            if jalur_baru: return jalur_baru
    return None

Misalkan kita ingin mencari jalur dari titik A ke titik D, maka kita bisa menggunakan fungsi tersebut.

>>> temukan_jalur(graf, 'A', 'D')
['A', 'B', 'C', 'D']

Fungsi untuk Menentukan Semua Jalur

Pada fungsi di atas, kita hanya diberikan satu jalur saja. Sedangkan fungsi berikut ini akan mengembalikan semua jalur yang bisa dilalui dari titik awal hingga akhir.

def temukan_semua_jalur(graf, awal, akhir, jalur=[]):
    jalur = jalur + [awal]
    if awal == akhir:
        return [jalur]
    if not graf.has_key(awal):
        return []
    semua_jalur = []
    for titik in graf[awal]:
        if titik not in jalur:
            jalur_jalur = temukan_semua_jalur(graf, titik, akhir, jalur)
            for jalur_baru in jalur_jalur:
                semua_jalur.append(jalur_baru)
    return semua_jalur

Misalkan kita ingin mencari semua jalur yang mungkin bisa dilalui dari titik A ke titik D, maka fungsi tersebut akan mengembalikan semua jalur dalam bentuk list.

>>> temukan_semua_jalur(graf, 'A', 'D')
[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]

Pada hasil eksekusi fungsi tersebut, kita diberikan tiga buah jalur yang bisa dilalui dari titik A menuju titik D.

Kesimpulan

Representasi graf ke dalam kode python dapat dilakukan dengan dictionary dan list. Semua titik dalam graf dijadikan kunci (key) dalam dictionary. Kemudian menyimpan titik tetangganya dalam list.

Baca Juga ini

Program Menghitung Tahun Kabisat dengan Python

Program Menghitung Tahun Kabisat dengan Python

Menurut wikipedia: Tahun kabisat (bahasa Inggris: Leap year) adalah tahun yang mengalami penambahan satu hari dengan tujuan untuk menyesuaikan penanggalan dengan tahun astronomi. Dalam satu tahun tidak secara persis terdiri dari 365 hari, tetapi 365 hari 5 jam 48 menit 45,1814 detik. Jika hal ini tidak dihiraukan, maka setiap 4 tahun akan kekurangan hampir 1 hari (tepatnya 23 jam 15 menit 0,7256 detik). Maka untuk mengkompensasi hal ini, setiap 4 tahun sekali (tahun yang bisa dibagi 4), diberi 1 hari ekstra: 29 Februari.

Eksperimen dengan API Simsimi

Eksperimen dengan API Simsimi

Kali ini saya akan mengajak teman-teman bereksperimen dengan API Simsimi. Apa itu Simsimi? buat yang belum tau, silahkan instal saja aplikasi Simsimi di smarphone-nya. Oke, mari kita mulai. API Simsimi konsepnya sangat sederhana. Kita hanya melakukan request dari URL dengan query string, lalu akan mendapatkan jawaban atau respon berdasarkan data yang dimiliki Simsimi. Respon tersebut, bisa kita olah untuk membuat Simsimi versi kita sendiri. 1. Mendapatkan Kunci APIKunci API atau API Key, merupakan kunci yang digunakan untuk mengakses API Simsimi.

Operator ^ (xor) di Java bukan untuk Membuat Pangkat

Operator ^ (xor) di Java bukan untuk Membuat Pangkat

Sebuah kekeliruan saya temukan ketika memeriksa kode program milik teman. Dia mengimplementasikan rumus berikut ke dalam kode java. y = x2 + 3 Potongan kode program yang dia tulis. int x = 3;int y = x^2 + 3; Hasilnya pun 6; tidak sesuai harapan. Seharusnya menghasilkan 12. Operator ^ (Exclusive Or) disingkat xor, merupakan operator bitwise. Operator bitwise merupakan operator untuk memanipulasi bilangan biner.

Manfaat Titik Koma pada Python yang Jarang diketahui Orang

Manfaat Titik Koma pada Python yang Jarang diketahui Orang

Siapa bilang di python tidak ada titik koma? Pada bahasa pemrograman lain, titik koma digunakan untuk mengakhiri sebuah baris perintah. Kadang juga titik koma bikin kesal, karena sering menyebabkan error. Salah programmernya sih, lupa ngetik titik koma 😄 Titik koma pada python memang jarang digunakan dan hampir tidak pernah kita temukan sama sekali. Tapi, karakter ini ternyata punya manfaat yang jarang diketahui orang. Apa saja manfaatnya?

Fungsi range() di pemrograman python

Fungsi range() di pemrograman python

Fungsi range() merupakan fungsi yang menghasilkan list. Fungsi ini akan menciptakan sebuah list baru dengan rentang nilai tertentu. Contoh: 1. list dari 0 sampai 10 range(10)akan menghasilkan: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]2. list dari 4 sampai 12 range(4, 12)akan menghasilkan: [4, 5, 6, 7, 8, 9, 10, 11]3. list dari 10 sampai 50 dengan interval 5 range(10,50,5)akan menghasilkan: [10, 15, 20, 25, 30, 35, 40, 45]Dari contoh-contoh di atas, dapat kita pahami arti parameter yang diberikan untuk fungsi ini.

Manfaat fungsi max() di pemrograman python

Manfaat fungsi max() di pemrograman python

Pernahkan anda bertemu dengan kasus perbandingan suatu nilai yang terbesar? Bila menyelesaikan menggunakan if dan datanya banyak, tentu akan terasa sangat merepotkan. Karena banyak nilai yang akan dibandingkan. Fungsi max() adalah fungsi bulid-in untuk mencari nilai tertinggi. Fungsi ini dapat diberikan sebuah parameter berupa angka. Artikel ini sebenarnya dibuat untuk menjawab sebuah pertanyaan di grup Python Indonesia. Saya pemilik pabrik sepatu, saya menugaskan staff saya untuk menginput jumlah penjualan bulan Januari, Februari, dan Maret 2014.