DFS

주의. 이 문서는 공머생들이 좋아하는 주제 혹은 공머생 그 자체에 대해 다룹니다. 본 문서가 다루는 내용에 지나치게 탐닉할 경우 필연적으로 여성들과 멀어지게 됩니다. 이는 조무위키가 책임지지 않습니다.

Depth First Search, 다른 말로 깊이 우선 탐색이라고 한다.

그래프가 있으면 방문 안한것들이 보일 때 마다 방문하는거다. BFS처럼 가까운 거 먼저 탐색하는게 아니라서 깊은 지점에 있는 것을 탐색할때는 유용하다.

구현할 때 스택 아니면 재귀로 구현하는데 재귀가 훨씬 편하다.

의사코드로 표현하면 다음과 같다.

 FUNCTION DFS(int src):
   Mark src as visited
   FOR i in graph[src]:
     IF i is not visited:
       VISIT i

C++로 표현하면 다음과 같다.

 void DFS(int src){
   Mark src as visited
   for(int i = 0;i<graph[src].size();i++){
     if(visited[graph[src][i]] == false) DFS(graph[src][i]);
   }
 }

그래프 탐색에서는 존나게 중요한 알고리즘 중 하나로 너비 우선 탐색하고 같이 많이 쓰인다. 보다시피 코드가 짧아서 사실 너비우선탐색보다 구현은 편하다.