[알고리즘] 그래프 깊이 우선 탐색(Depth-First Search)

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

• 대표적인 그래프 탐색 알고리즘
• 정점의 자식 노드들을 먼저 탐색하는 방식이다.

 

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

위와 같은 형태의 그래프가 있을 때 깊이 우선 탐색은 처음 시작 정점을 방문한 뒤,  인접 정점의 자식을 타고 끝까지 방문한 후, 다시 돌아와서 다른 형제의 자식노드를 타고 모든 정점을 방문한다. 넓이 우선 탐색과 다르게 깊이 우선 탐색은 탐색할 때 스택을 이용해야 한다.

 

첫 번째 노드에서 출발하기 때문에 1번 노드를 방문예약(need_visit) 스택에 넣은 뒤 1번 노드를 방문예약 스택에서 빼고 인접한 노드인 2, 5번 노드를 방문예약 스택에 넣어준다. (이후부터 스택이라 칭함)

 

5번 노드를 방문한 후 인접 노드인 4번 노드를 스택에 넣어준다.

 

마찬가지로 4번 노드를 방문한 후 인접 노드인 6번 노드를 스택에 넣어준다.

 

6번 노드를 방문한 후 더이상 자식 노드가 없기 때문에 이후에는 2번노드를 방문하게 된다.

같은 방식으로 계속 수행하게 되면

 

 

 

더이상 방문예약스택에 남아있는 정점이 없을 때 탐색을 종료한다.

 

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

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited

 

깊이 우선 탐색(Depth-First Search) 시간 복잡도

• 노드 수: V
• 간선 수: E
• 깊이 우선 탐색의 시간 복잡도는 노드 수 + 간선 수로 표현된다. O(V+E)