1. DFS (Depth-First Search) : 깊이 우선 탐색
- DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- DFS는 스택 자료구조(혹은
재귀함수)를 이용하며, 구체적 동작과정은 다음과 같음 - 탐색시작노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리
- 방문하지 않은 인접노드가 없으면(모두 방문했으면) 스택에서 최상단 노드를 꺼냄
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
1-1. DFS 동작 예시 (예시는 번호가 낮은 인접 노드 부터 방문)
- [step 0] 그래프 준비 (방문 기준 : 번호가 낮은 인접노드부터) / 시작노드 : 1
- [step 1] 시작노드인 ‘1’을 스택에 삽입하고 방문처리
- [step 2] 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접노드 ‘2’, ‘3’, ‘8’,이 있음
이 중에서 가장 작은 노드인 ‘2’를 스택에 넣고 방문처리
- [step 3] 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접노드 ‘7’이 있음
따라서, ‘7’번 노드를 스택에 넣고 방문처리
- [step 4] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접노드 ‘6’, ‘8’이 있음
이 중에서 가장 작은 노드 ‘6’번 노드를 스택에 넣고 방문처리
- [step 5] 스택의 최상단 노드인 ‘6’에 방문하지 않은 인접노드가 없음
따라서 스택에서 6번 노드를 꺼냄
- [step 6] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접노드 ‘8’이 있음
따라서 ‘8’번 노드를 스택에 넣고 방문처리
- 위와 같은 과정을 반복한다.
1-2. DFS 소스코드
def DFS(graph, v, visited):
visited[v] = True
print(v, end = " ")
for i in graph[v]:
if not visited[i]:
DFS(graph, i, visited)
N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(N+1):
graph[i].sort()
visited = [False] * (N+1)
DFS(graph, V, visited)- DFS의 핵심은 재귀...!
🐢