깊이우선탐색(DFS)

1. 출발점 s에서 시작한다.

2. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다.

3. 2번을 계속 반복한다.

4. 만약 unvisited인 이웃노드가 존재하지 않는 동간 계속해서 직전 노드로 되돌아간다.

5. 다시 2번을 반복한다.

6. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다.

DFS(G, v)

visited[v] <- Yes;

for each node u adjacent to v do

if visited[u] = No then

DFS(G,u);

end

end

그래프가 disconnected이거나 혹은 방향그래프라면 DFS에 의해서 모든 노드가 방문되지 않을 수도 있음

DFS를 반복하여 모든 노드 방문

DFS-ALL(G)

{

for each v∈ V

visited[v] <- no;

for each v∈ V

 if(visited[v] = no ) then

     DFS(G,v);

}