Breadth-First Search

Menjelajahi semua tetangga di kedalaman saat ini sebelum turun lebih dalam, memakai queue untuk memproses node level demi level.

Kompleksitas

Waktu (Terburuk)

O(V + E)

Memori

O(V)

Poin Penting

›Memproses node level demi level, sehingga menjamin jalur terpendek pada graph tanpa bobot
›Memakai queue (FIFO) untuk menyimpan frontier
›Tandai node sebagai visited sebelum di-enqueue agar tidak diproses dua kali
›Ruang O(V): di kasus terburuk queue bisa menampung semua vertex
›Penerapan: jalur terpendek, level-order traversal, tetangga terdekat, pengecekan bipartite

Contoh Kode

Swift

func bfs(graph: [Int: [Int]], start: Int) -> [Int] {
    var visited = Set<Int>()
    var queue = [start]
    var result = [Int]()

    visited.insert(start)

    while !queue.isEmpty {
        let node = queue.removeFirst()
        result.append(node)
        for neighbor in graph[node] ?? [] where !visited.contains(neighbor) {
            visited.insert(neighbor)
            queue.append(neighbor)
        }
    }
    return result
}

let graph = [0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2]]
print(bfs(graph: graph, start: 0))  // [0, 1, 2, 3, 4, 5]

Latihan Soal

Binary Tree Level Order Traversal

SedangLeetCode ↗

Number of Islands

SedangLeetCode ↗

Course Schedule

SedangLeetCode ↗

Word Ladder

SulitLeetCode ↗