DFS / BFS

DFS 깊이 우선 탐색 (Depth-First Search)

출처 https://developer-mac.tistory.com/64

• 그래프 전체를 탐색하는 방법(완전탐색)
  루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
  
  예를 들어 미로찾기 할 때 최대한 한 방향으로 갈 수 있을 때 까지 가고 더 이상 갈 수 없으면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길 부터 다른 방향으로 탐색을 진행하는 것

 

• 스택 또는 재귀함수로 구현
  1. 탐색 시작 노드를 스택에 삽입하고 방문처리
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
  3. 2번의 과정을 수행할 수 없을 때까지 반복
  
  
• 모든 노드를 방문하고자 하는 경우
  
• 경로의 특징을 저장해야할 경우
  각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 함
• 검색 대상 그래프가 많을 경우

 

장점	목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다 DFS가 BFS 보다 좀 더 간단함 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
단점	해가 없는 경로에 깊이 빠질 가능성이 있다 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발경하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수도 있다. 검색 속도 자체는 BFS 에 비해 느리다 얻어진 해가 최단 경로가 된다는 보장이 없다. 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수도 있다.

 

 

 

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

출처 https://developer-mac.tistory.com/64

 

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방식
  시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

 

• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용
  
  예를 들어 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우
  깊이 우선 탐색의 경우엔 모든 친구 관계를 다 살펴봐야 할지도 모르지만
  너비 우선 탐색의 경우는 Sam과 가까운 관계부터 탐색하는 것

 

• 큐를 이용하여 구현
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리
  3. 2번 반복
  특정 조건의 최단 경로 알고리즘을 계산할 때 사용
  

 

• 최단거리를 구해야 할 때
• 검색 대상 그래프 규모가 크지 않고 검색 시작 점으로 부터 원하는 대상이 멀지 않을 때

장점	출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
단점	경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요 해가 존재하지 않는다면 유한 그래프의 경우, 모든 그래프를 탐색한 후에 실패로 끝난다. 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

 

출처 : https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0