DFS, BFS

DFS??

Deep-First Search의 줄임말로, 깊이 우선 탐색이라고 한다. 트리나 그래프를 탐색할때 다른 브렌치로 가기 전에 해당 브렌치를 완벽하게 탐색하는 방법이다.

1. 미로를 탐색할때 갈 수 있을때까지 가다가 더 이상 갈 수 없을때 다시 가장가까운 갈림길로 와서 다른 방향으로 탐색하는 방법과 유사하다.
2. 넓게 탐색하기 전에 깊이 탐색한다.
3. 모든 노드를 방문하고자 하는 경우에 이 방법을 사용한다.
4. DFS이 BFS보다 간단하다.
5. 검색속도는 BFS보다 느리다.

DFS의 특징

• 자기 자신을 호출하는 순환알고리즘 형태이다.

• 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.(이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)

  DFS의 시간 복잡도

• DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함

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

BFS??

Breadth-First Search의 줄임말로서 너비우선탐색이라고 하며 인접한 노드를 먼저 탐색하는 방법이다.

1. 시작점으로부터 가까운 곳부터 탐색하는 방법이다.
2. 즉 깊에 탐색하기전에 넓게 탐색하는 방법.
3. 두 노드 사이에 최단거리를 찾을때 혹은 임의의 경로를 찾고 싶을 때 사용한다.

예를 들어서 지구상의 인간관계를 그래프로 그린 후 A의 친구 B를 찾을려고 한다. 그랬을때에 깊이우선탐색은 전부다 탐색할수도 있는 반면, 너비우선탐색은 A의 주변 친구들부터 탐색한다.

BFS의 특징

• 재귀적으로 동작하지 않는다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
• BFS 는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
• 즉 선입선출(FIFO) 원칙으로 탐색.