2025-07-28 00:17
Status:
Tags:알고리즘
깊이 우선 탐색 DFS Depth-First-Search
- 최대한 깊게 탐색하고 못가는 지점에서 이전 분기점으로 돌아와 탐색 반복하는 알고리즘
원리
- 시작 정점 선택
- 현재 정점을 방문 처리
- 미방문 인접 정점을 재귀 혹은 스택으로 탐색
- 재귀는 코드 간단하지만 오버플로우 위험
- 스택은 약간 더 복잡해질 수 있지만 안전, 그렇게 어려운 건 아님
- 인접 정점 없으면 백트래킹
- 모든 정점 방문 시 종료
파이썬 코드
2.2 재귀(Implicit Stack) vs. 명시적 스택(Explicit Stack)
# 재귀
def dfs(v,visited,adj):
visited[v] = True;
for u in adj[v]:
if not visited[u]:
dfs(u, visited, adj)
def dfs(start,adj):
visited = set()
stack = [start]
visited.add(start)
while stack:
v = stack.pop()
for u in adj[v]:
if u not in visited:
visited.add(u)
stack.append(u)시간 복잡도 O(V+E)
- V 정점수, E 간선수, 모든 정점과 간선 한번씩만 조사하므로 선형 시간