[알고리즘] 깊이우선탐색(DFS)

깊이우선탐색(Depth First Search)

그래프를 탐색할 때 쓰는 알고리즘으로 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 반복하지 않고 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘이다.

DFS PseudoCode

DFS(u, adj)
    u.visited = true
    for each v ∈ adj[u]
        if v.visited == false
            DFS(v, adj)

• 어떠한 정점 U의 visited를 참으로 바꾸고 연결되어있는 V지점을 탐색한다.
• 이 때 방문되지 않은 노드에 대해 재귀적으로 DFS를 호출한다.

DFS 탐색 예제

graph TD; 1((1)) --> 2((2)); 2((2)) --> 4((4)); 1((1)) --> 3((3)); 2((2)) --> 5((5)); 4((4)) --> 2((2)); style 1 stroke:#333,stroke-width:3px,font-size:30px style 2 stroke:#333,stroke-width:3px,font-size:30px style 3 stroke:#333,stroke-width:3px,font-size:30px style 4 stroke:#333,stroke-width:3px,font-size:30px style 5 stroke:#333,stroke-width:3px,font-size:30px

• 1 -> 2 -> 4 -> 5 -> 3

let n: Int = 6
var adj: [[Int]] = Array(repeating: [Int](), count: n)
var visited: [Bool] = Array(repeating: false, count: n)

func dfs(_ here: Int) {
    visited[here] = true
    print(here, terminator: " ")
    
    for there in adj[here] {
        if visited[there] { continue }
        dfs(there)
    }
}

@main
struct Main {
    static func main() {
        adj[1].append(2)
        adj[1].append(3)
        adj[2].append(4)
        adj[4].append(2)
        adj[2].append(5)
        dfs(1)
    }
}

// 결과: 1 2 3 4 5 3