DFS (Depth-First Search)

DFS (Depth-First Search)

✔ 그래프 탐색 알고리즘

탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미

 

 

✔ DFS 특징

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로, 깊이 우선 탐색이라고도 불림
• 재귀적으로 구현 또는 후입선출 구조의 스택을 적용
• 트리일 경우 순회 방향 (번호 순서대로 진행)
• 시간복잡도는 O(V+E) 👉 V : 노드 수,  E : 에지 수

DFS 순회

✔ 동작 과정

1️⃣ 탐색 시작 노드를 스택에 삽입하고 방문 처리

2️⃣ 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼내기

3️⃣ 더 이상 2️⃣번의 과정을 수행할 수 없을 때까지 반복 (재귀)

 

✔ 예시

DFS 동작 과정

1️⃣ 시작 노드 1을 스택에 삽입하고 방문처리 (스택의 최상단 노드 = 1)

2️⃣ 스택의 최상단 노드인 1에 방문하지 않은 인접노드 2, 3 중 가장 작은 노드인 2를 스택에 넣고 방문 처리 (스택의 최상단 노드 = 2)

3️⃣ 스택의 최상단 노드인 2에 방문하지 않은 인접노드 5를 스택에 넣고 방문 처리 (스택의 최상단 노드 = 5)

4️⃣ 스택의 최상단 노드인 5에 방문하지 않은 인접노드 3을 스택에 넣고 방문 처리 (스택의 최상단 노드 = 3)

5️⃣ 스택의 최상단 노드인 3에 방문하지 않은 인접노드 4를 스택에 넣고 방문 처리 (스택의 최상단 노드 = 4)

6️⃣ 스택의 최상단 노드인 4에 방문하지 않은 인접노드 6을 스택에 넣고 방문 처리 (스택의 최상단 노드 = 6)

위의 과정에서 만약 스택의 최상단 노드번호에 방문하지 않은 인접 노드가 없다면 스택에서 해당 노드번호를 꺼냄

👉 이러한 과정을 반복하였을 때 전체 노드의 탐색 순서(스택에 들어간 순서)는 1>2>5>3>4>6

 

 

✔ 슈도 코드 (pseudocode)

G : 그래프
DFS(v) // v: 탐색 정점

    visited[v] ← TRUE  // v 방문 처리

    FOR each all w in adjacency(G,v)  // 모든 인접 정점을 순회
        IF visited[w] ≠ TRUE  // 방문 처리가 되지 않은 노드라면
            DFS(w)  // DFS() 실행

👉 기저조건 : 모든 인접 정점이 방문이 된 경우

 

 

⚠ DFS에서 유의할 점

👉 실제 구현 시 재귀 함수를 이용하므로 스택오버플로우(StackOverFlow)가 발생할 수 있어 주의해야 함