TOP 25 ALGORITMOS | Depth First Search (DFS)

DFS는 주어진 시작점에서 출발해 도달 가능한 모든 정점을 탐색한다.

인접리스트를 생성하고 간선을 양방향으로 추가해 그래프를 무향으로 처리한다.

visited 배열로 재처리를 방지하고 dfsRec로 인접 미방문 정점을 재귀적으로 순회한다.

예시: V = 5, 간선 [[1,2], [1,0], [2,0], [2,3], [2,4]]; 그래프에 루프가 있을 수 있다.

시간·공간 복잡도는 O(V+A), 보조공간 사용. 장점: 시간 제한·선형 메모리; 단점: 유한 그래프에서 무한 해가 발생할 수 있음.