DFS 깊이 우선 탐색

알고리즘 - DFS 깊이 우선 탐색

그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법 ! 탐색의 각 과정에서 가능한 한 그래프 안으로 ‘깊이’ 들어가려고 시도하며, 막힌 정점에 도달하지 않는 이상 뒤로 돌아가지 않는다

📝풀어볼 문제

• DFS와 BFS
• 연결 요소의 개수
• 순열 사이클

깊이 우선 탐색 (DFS)

⚠️ 가장 중요한 특정은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 것

1. 깊이 우선 탐색 구현할 경우 : 스택(stack)의 성질을 활용 → 방문하는 순서대로 정점을 스택에 쌓고 방문이 끝나면 스택에서 pop
2. 알고리즘 해결할 경우 : 재귀 호출을 이용 → 재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문

✔️ 깊이 우선 탐색은 그래프 전체의 구조를 파악하기 위해 사용되므로, 그래프의 구조상 한 번에 모든 정점을 다 볼 수 없는 경우에도 모든 정점을 다 방문할 필요가 있음

시간 복잡도

✔️ 정점의 집합 : V, 간선의 집합 : E 로 표현

✔️ 그래프 종류

• 무방향 그래프(undirected graph) : 간선의 방향이 없어 양 방향으로 이동 가능
• 방향 그래프(directed graph) : 간선의 방향으로만 이동

1. 인접 리스트 : O(|V| + |E|)
   1. dfs() 는 한 정점마다 한 번씩 호출되므로, 정확히 |V|번 호출됨
   2. 모든 정점에 대해 dfs()를 수행한 후, 모든 간선을 정확히 한 번(방향 그래프) 혹은 두 번(무향 그래프) 확인하는 것을 알 수 있음
2. 인접 행렬 : O(|V|^2)
   1. dfs() 호출 횟수는 |V|번
   2. 인접 행렬을 사용할 때는 dfs() 내부에서 다른 모든 정점을 순회하며 두 정점 사이에 간선이 있는가를 확인해야하기 때문에 한 번의 실행에 O(|V|)의 시간이 걸림

그래프 순회 과정

최종 방문 경로 : 1 2 4 5 3 6 7