루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완전하게 탐색하는 방법

모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.

• 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

• DFS 과정

  

  

  깊이 우선 탐색(DFS)의 시간 복잡도

  • DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.
    • 인접 리스트로 표현된 그래프: O(N+E)
    • 인접 행렬로 표현된 그래프: O(N^2)
    • 즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

  

  # DFS - 깊이 우선 탐색 -> 스택을 이용. 파이썬에서 리스트는 스택으로 구현되어 있음!
  graph = [
      [],
      [2, 3, 8],
      [1, 7],
      [1, 4, 5],
      [3, 5],
      [3, 4],
      [7],
      [2, 6, 8],
      [1, 7]
  ]
  
  # 방문노드
  visited = [False] * len(graph)
  
  def dfs(graph, v, visited):
      visited[v] = True
      print(v, end=' ')
      
      for i in graph[v]:
          if not visited[i]:
              dfs(graph, i, visited)
  
  # 0번 노드가 없으니 1번 노드부터 탐색
  dfs(graph, 1, visited)