graph(graf)

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

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.