DFS

DFS 깊이 우선 탐색(Depth First Search)은 쉽게 말해서 한 우물만 깊게 파다가 막히면 그때 돌아가서 다른 우물을 파는 것이라고 할 수 있다.

DFS로는 이어져있지 않은 정점은 방문할 수 없다.
이 점을 이용하여 그래프에서 연결요소(Component)를 찾는데 사용할 수 있다.

Component
연결요소 안에 속한 정점은 모두 이어져있으며, 다른 연결요소와는 이어져있지 않다. 그리고 컴포넌트는 항상 최대 크기여야 한다.
(연결그래프는 그래프의 컴포넌트가 단 하나인 경우이다.)

DFS를 한 번 하면, 시작점이 속한 컴포넌트의 정점들만 다 방문하고 나머지는 절대 방문하지 못한다. 따라서 모든 정점을 방문하려면 각 컴포넌트에 속한 정점들 중 하나씩은 방문을 해줘야 한다. 이때 방문을 시도하는 횟수가 컴포넌트의 개수가 된다.

DFS의 시간복잡도는 O(V+E)이다. 한 번 방문한 정점은 다시 방문하지 않고, 한 정점에서 다음으로 방문하는 횟수가 그 정점의 차수와 같기 때문이다.
이것은 인접 리스트의 경우이고, 인접 행렬로 구현을 한다면 O(V^2)가 된다.

DFS의 활용중에는 앞서 말한 연결요소의 개수를 구하는 것과, 사이클에 속한 정점을 구하는 것이 있다.
사이클에 속한 정점을 구하는방법은

1. 정점 방문을 시작했는지를 나타내는 visited 배열
2. 그 정점의 방문 함수가 완전히 끝났는지를 나타내는 finished 배열

이 필요하다. 그리고 사이클이 발생하는 조건은 visited[v] == True and finished[v] == False인 경우이다.