그래프에서의 DFS

깊이 우선 순회 (DFS)

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

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

3.2번 계속 반복한다.

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

5.다시 2번을 반복

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

 

아래와 같은 그림 흐름으로 깊이 우선순회가 이루어짐

DFS(G, v)
 visited[v] <- Yes; // 이노드는 내가 와본 노드 ( 중복 방문하지 않기 위해 체크)
for each node x adjacent to v do //  v 에 인접한 노드 
	if visited[x] = No then   // 방문되지 않는 노드 x 가 존재하면
		DFS(G,u); 
	end
end

어떤 노드에서 갈곳이 없으면 되돌아가야한다. 

v에 인접한 노드중에 visited = no 인게 없으면 for 문 탈출

호출했던 지점으로 돌아감

 

그래프가 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);
}

시간 복잡도 : O(n+m)

-첫번째 for문에 의해서 시간복잡도 n은 피할수없다.

-두번째 for문에 의해서 v노드와 엣지로 이어진 노드가 visited인지 체크 , 인접리스트로 표현했다면 시간복잡도는 

엣지갯수에 비례 o(m)

-최종적으로 o(n+m)의 시간복잡도를 갖는다.