[알고리즘] DFS(Depth-First-Search, 깊이 우선 탐색)

DFS란?

 

그래프 탐색 알고리즘으로 그래프의 모든 정점(vertex)을 깊이 탐색하는 방법(알고리즘)

 

DFS는 시작 정점에서 인접한 정점들을 방문하고, 인접 정점들의 인접 정점을 방문하는 방식으로 동작한다.

BFS와 다르게 하나의 경로를 깊이(끝)까지 탐색한 후에야 다른 경로로 되돌아와 탐색을 진행한다.

 

 

표현 방법

// 인접 리스트
1 - [2, 8]
2 - [1, 3, 6, 7]
3 - [2, 4, 5]
4 - [3, 5]
5 - [3]
6 - [2]
7 - [2]
8 - [1, 9]
9 - [8]

// 인접 행렬
   1 2 3 4 5 6 7 8 9
1 [0 1 0 0 0 0 0 1 0]
2 [1 0 1 0 0 1 1 0 0]
3 [0 1 0 1 1 0 0 0 0]
4 [0 0 1 0 1 0 0 0 0]
5 [0 0 1 1 0 0 0 0 0]
6 [0 1 0 0 0 0 0 0 0]
7 [0 1 0 0 0 0 0 0 0]
8 [1 0 0 0 0 0 0 0 1]
9 [0 0 0 0 0 0 0 1 0]

 

import Foundation

let graph = [[], [2, 8], [1, 3, 6, 7], [2, 4, 5], [3, 5], [3], [2], [2], [1, 9], [8]]
var visited = Array(repeating: false, count: graph.count)

func dfs(start: Int) {
    
    if visited[start] { return }
    
    visited[start] = true
    
    for nextNode in graph[start] {
        
        if !visited[nextNode] {
            dfs(start: nextNode)
        }
    }
}

dfs(start: 1)

 

그래프의 1에서 시작

첫 nextNode는 graph[1]의 2로 시작한다.

이 때 visited[1]로 1은 방문한 표시로 true로 변경해준다.

 

2는 방문하지 않았기 때문에 graph[1]의 다음 8이 아닌

graph[2]로 타고 들어가게 된다.

마찬가지로 visited[2]도 true로 변경된다.

 

graph[2]에는 1, 3 ,6, 7이 있지만

1은 이미 방문했기 때문에 return되고 다음 3으로 진행된다.

 

이런식으로 방문한 곳은 무시한채, 재귀적으로 깊게 타고 들어가게된다.