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

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

•  (방향 상관없이) 자신과 연결된 노드의 가장 아래 레벨까지 내려가 탐색하고 그 노드가 리프 노드이면 상위 노드의 다른 리프 노드를 먼저 탐색하고 올라가는 방식
• BFS와 탐색의 순서가 다르다

 

2. DFS 알고리즘 구현

• 자료구조 스택과 큐를 활용함
• need_visit 스택과 visited 큐, 두 개의 자료구조를 생성
  
  • 스택이기 때문에 pop_back()으로 앞이 아니라 뒤에 있는 데이터를 먼저 가져옴

BFS 자료구조는 두 개의 큐를 활용하고 DFS는 스택과 큐를 활용한다는 차이가 있음을 인지해야 한다

 

def dfs(graph, start_node):
    need_visit, visited = 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

dfs(graph, 'A')

출력 : ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']

 

4. 시간 복잡도

• 일반적인 BFS 시간 복잡도
  • 노드 수 : V
  • 간선 수 : E
    • 위 코드에서 while need_visit은 V + E번 만큼 수행
  • 시간 복잡도 : O(V+E)
    • BFS와 동일