DFS, BFS

in Algorithm


개요

DFS, BFS 자료구조에 대해 공부합니다.

DFS(Depth FirstSearch, 깊이 우선 탐색)

개념

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 back-tracking에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다.

  • 장점
    • 현 경로상의 노드만 기억하면 되므로 저장공간이 비교적 적게 필요하다.
    • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
  • 단점
    • 해가 없는 경로에 깊이 빠질 위험이 있다 ( -> 깊이 제한으로 완화가 가능 )
    • 얻어진 해가 최단 경로가 된다는 보장이 없다.
    • 단순 검색 속도 자체는 BFS에 비해서 느리다.

BFS(Breath-First-Search, 너비 우선 탐색)

개념

루트 노드를 방문한 후 루트 노드에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 일반적으로 Queue를 사용하여 구현한다

  • 장점
    • 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
  • 단점
    • DFS보다 많은 기억 공간을 필요로 하게 된다.
    • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.