[알고리즘] #6_3 DFS

** DFS 알고리즘 구현

• 자료구조 스택과 큐를 활용함
  • need_visit 스택과 visited 큐, 두 개의 자료 구조를 생성

 

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

• 큐와 스택 구현은 별도 라이브러리를 활용할 수도 있지만, 간단히 파이썬 리스트를 활용할 수도 있음

 

 

---

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()  # BFS와 차이: 스택 정책
        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']

# 그래프 그림 상으로 우 -> 좌

---

 

** 시간 복잡도

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