DFS

BFS는 인접한 노드부터 탐색했지만, DFS는 그러지 않다.

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 재귀를 사용하여 구현한다.
• 모든 노드를 방문하고자 하는 경우 사용된다.
• 시간복잡도 : O(N+E)

 

void dfs(int curr){
	visited[curr] = true;
    for(int next : adj[curr]){
    	if(!visited[next]){
        	dfs(next)
        }
    }
}