14-3강. 그래프에서의 DFS

DFS(Depth-First Search) 깊이 우선 탐색

 

level order traversal (BFS)

 

inorder traversal (DFS)

pre-order traversal (DFS)

post-order traversal (DFS)

 

그래프에서의 DFS

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

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

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

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

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

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

 

이 그래프에서는 1-3-7-8-7-3-5-2-4-2-5-6 순서로 간다.. (하지만 순서는 바뀔 수 있다)

(s=1에서 3이 아닌 2를 먼저 방문할 수도 있다.)

 

// 가장 첫 호출은 DFS(G, s)가 될 것이다.

DFS (G, v)
	visited[v] <- YES;	// 방문된 노드를 yes로 표기한다.
    for each node x adjacent to v do	// node v의 인접한 노드 x에 대해서 반복 검사를 한다..
    	if visited[x] = NO then	// visited[x]가 방문되지 않은 노드라면,
        	DFS(G, x);	// DFS 함수 호출을 반복한다.
    end.
end.

 

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

 

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

 

 

공부 자료

www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4107?tab=curriculum

영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런