19. DFS (깊이 우선 탐색)

출처: http://ejklike.github.io/2018/01/05/bfs-and-dfs.html

---

DFS 알고리즘 (깊이 우선 탐색) - Depth-first-search

DFS (깊이 우선 탐색).
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 탐색하는 방법
넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.

사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
DFS(깊이 우선 탐색)가 BFS(너비 우선 탐색)보다 좀 더 간단하다.
단순 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 느리다.

DFS (깊이 우선 탐색)의 특징.
자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
검사하지 않을 경우 무한루프에 빠질 위험이 있다.

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

---

DFS 알고리즘 플로우

출처: https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

1. a 노드(시작 노드)를 방문한다.
방문한 노드는 방문했다고 표시한다.

2. a와 인접한 노드들을 차례로 순회한다.
a와 인접한 노드가 없다면 종료한다.

3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.

4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
아직 방문이 안 된 정점이 없으면 종료한다.
있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

---

DFS 알고리즘 파이썬 코드

코드 1

def dfs(graph, start):
  visited = []
  stack = [start]
  while stack :
    n = stack.pop()
    if n not in visited:
      visited.append(n)
      stack += graph[n] - set(visited)
      print(visited)
  return visited

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B']),
         'F': set(['C'])}

start = 'A'

print(dfs(graph, start))

---

코드 2

def dfs(graph, start):
  visited = []
  stack = [start]
  while stack :
    n = stack.pop()
    if n not in visited:
      visited.append(n)
      stack += graph[n] - set(visited)
      print(visited)
  return visited

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B']),
         'F': set(['C'])}

start = 'A'

print(dfs(graph, start))

def dfs_paths(graph, start, goal):
  stack = [(start, [start])]
  result = []

  while stack:
      n, path = stack.pop()
      if n == goal:
          result.append(path)
      else:
          for m in graph[n] - set(path):
              stack.append((m, path + [m]))
  return result

print(dfs_paths(graph, 'A', 'E'))

코드 2 결과

과정 + 결과

---

DFS 알고리즘 의 시간 복잡도

인접 리스트로 표현된 그래프: O(N+E)
인접 행렬로 표현된 그래프:

---

References

• http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

• McDowell, G. L. (2016). Cracking the Coding Interview: 189 Programming Questions and Solutions. CareerCup, LLC.

• http://blog.eairship.kr/269

• 코딩 인터뷰 완전 분석, 프로그래밍 인사이트

• C언어로 쉽게 풀어 쓴 자료구조

• http://ejklike.github.io/2018/01/05/bfs-and-dfs.html