알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search)

알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search)

DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 미로에서 갈림길로 돌아가서 길을 찾는 것을 생각하면 된다. DFS를 설명하기 전에, 먼저 그래프의 기본 구조를 알아야 한다.

https://jina-developer.tistory.com/108

자료구조 - 그래프

 

모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. BFS보다 좀 더 간단하지만 검색 속도는 BFS보다 느리다.

 

[ DFS의 활용 ]

백트래킹, 단절선 찾기, 단절점 찾기, 위상정렬, 사이클 찾기 등

 

[ pseudocode로 DFS 구현 ]

DFS(G):
	for each vertex u ∈ G.V
        u.color = WHITE	// 모든 정점들의 상태를 WHITE로,
        u. parent = NIL	// 부모를 NIL로 초기화
    time = 0
    for each vertex u ∈ G.V	// 정점 u에 대하여
        if u.color == WHITE	// 그 정점의 상태가 WHITE이면
            DFS_VISIT(G, u)	// DFS 함수를 호출함

DFS_VISIT(G, u):		// 정점 u를 방문하면
	time = time + 1 // 시간을 1 증가 시키고
    u.d = time
	u.color = GRAY	// 상태를 gray로 변경
    for each v ∈ G.Adj[u] 	// 현재 정점의 인접한 모든 정점에 대하여
    	if v.color == WHITE	// 그 정점의 상태가 WHITE이면
        v.parent = u
        DFS(G, v)			// 깊이 탐색을 위해 재귀호출함
	u.color = BLACK	//인접한 모든 정점들의 방문이 끝나면 back tracking이 되어 상태를 black으로 변경하고
    time = time + 1 // 정점 방문한 시간을 기록함
    u.f = time

 

[ 시간 복잡도 ]

초기화하는 과정은 |V| 번 수행되며 DFS 함수를 호출하면 |Adj[u]| 번 수행된다. (u의 인접 정점들의 개수)

따라서  θ(V + E)의 시간복잡도가 나온다.

 

[ 동작 과정 ]

DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복하다.

=> 방문 처리는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

 

[ 코드 ]

def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=" ")
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7], 
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

# 1 2 7 6 8 3 4 5