Graf: daftar ketetanggaan, BFS, dan DFS

Graf terdiri atas simpul dan sisi yang menghubungkan dua simpul. Halte dan rute bus, akun dan hubungan pertemanan, serta halaman dan tautannya adalah graf. Sisi berarah hanya bisa dilalui satu arah; sisi tak berarah bisa dua arah. Di Python graf paling mudah disimpan sebagai daftar ketetanggaan: dict yang memetakan setiap simpul ke list tetangganya. Graf tak berarah menulis setiap sisi dua kali, sekali di tiap ujungnya.

Penelusuran melebar (breadth-first search, BFS) memakai antrean. Mulai dari simpul awal, kunjungi semua tetangganya, lalu tetangga dari tetangga, tingkat demi tingkat. Karena simpul dikunjungi menurut tingkat, BFS memberi jumlah sisi paling sedikit dari simpul awal ke setiap simpul lain pada graf tanpa bobot. Graf yang sisinya berbobot, seperti jarak dalam kilometer, butuh algoritma Dijkstra yang dibahas di kelas Riset Operasi Dasar.

from collections import deque

halte = {"Terminal": ["Pasar", "RSUD"], "Pasar": ["Alun"], "RSUD": ["Alun"], "Alun": []}

def terjangkau(graf, awal):
    dikunjungi = {awal}
    antre = deque([awal])
    while antre:
        v = antre.popleft()
        for w in graf[v]:
            if w not in dikunjungi:
                dikunjungi.add(w)
                antre.append(w)
    return dikunjungi

Penelusuran mendalam (depth-first search, DFS) memakai tumpukan, atau rekursi yang memakai tumpukan panggilan. DFS mengikuti satu jalur sejauh mungkin sebelum mundur dan mencoba cabang lain. Urutannya tidak menjamin jalur terpendek, tetapi cukup untuk pertanyaan terjangkau atau tidak, dan untuk menghitung komponen: kelompok simpul yang saling terhubung. Biaya kedua penelusuran O(V + E), sebanding dengan banyaknya simpul ditambah sisi.