DFS

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

그래프가 있으면 방문 안한것들이 보일 때 마다 방문하는거다.

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

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

 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]);
   }
 }

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