깊이 우선 탐색. DFS. Depth First Search.

그래프의 탐색 방법 중에는 크게 깊이우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다.

이 탐색 방법들의 목적은 모든 정점을 1번씩 방문하는 것이다.

 

DFS는 최대한 깊숙히 탐색.

BFS는 최대한 넓게 탐색한다.

 

DFS는 스택을 이용하고 BFS는 큐를 이용한다.

 

BFS는 모든 간선의 가중치가 1일 때 최단거리를 탐색하는 알고리즘이 된다.

 

*DFS

 

check[i] =1 or 0 을 사용해 방문 여부를 저장한다. 

 

시간복잡도는 인접행렬을 사용했을 때는 O(V^2), 인접리스트를 사용하면 O(V+E)이다.

 

*BFS

 

시간복잡도 인접행렬 : O(V^2) 리스트: O(V+E)