Depth-First Search

Menjelajahi setiap cabang sedalam mungkin sebelum mundur (backtracking), memakai rekursi atau stack eksplisit.

Kompleksitas

Waktu (Terburuk)

O(V + E)

Memori

O(V)

Poin Penting

›Menelusuri satu jalur sampai habis sebelum mencoba alternatif lain
›Bisa diimplementasikan secara rekursif (call stack) atau dengan stack eksplisit
›Ruang O(V) untuk stack rekursi di kasus terburuk (graph berbentuk garis)
›Tidak menjamin jalur terpendek; gunakan BFS untuk itu
›Penerapan: topological sort, deteksi cycle, connected components, menyelesaikan labirin

Contoh Kode

Swift

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

    func explore(_ node: Int) {
        visited.insert(node)
        result.append(node)
        for neighbor in graph[node] ?? [] where !visited.contains(neighbor) {
            explore(neighbor)
        }
    }

    explore(start)
    return result
}

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

Latihan Soal

Number of Islands

SedangLeetCode ↗

Clone Graph

SedangLeetCode ↗

Path Sum

MudahLeetCode ↗

Course Schedule II

SedangLeetCode ↗