[Python] BFS와 DFS 정리

BFS, DFS

• 그래프 탐색 알고리즘이다.
• 노드를 방문하는데 사용한다.

 

 

BFS (Breadth First Search)

 

BFS (너비우선탐색)

 

• BFT(breadth-first traversal)라고도 불린다.
• 너비우선탐색
• 최대한 넓게 보는 것.
• 잉크가 퍼지는 느낌으로 탐색한다.
• BFS는 큐의 개념이 사용된다.
• 장점
  • 노드가 적은 경우 최단경로를 탐색할 때 유용하다.
  • 최단경로를 찾기 적합하다.
  • 찾는 노드가 인접한 경우 효과적이다.
• 단점
  • Queue를 이용해노드를 저장하기 때문에 노드의 수가 많을수록 메모리를 많이 소비한다.
• BFS의 활용
  • 길 찾기, 라우팅
  • BitTorrent와 같은 P2P 네트워크에서 인접 노드 찾기
  • 웹 크롤러
  • 소셜 네트워크에서 멀리 떨어진 사람 찾기
  • 그래프에서 주변 위치 찾기
  • 네트워크에서 방송
  • 그래프에서 주기 감지
  • 연결된 구성 요소 찾기
  • 몇 가지 이론적 그래프 문제 풀기
• 너비우선적으로 노드를 탐색하는 경우, 큐를 활용하므로 노드가 많아지는 경우 메모리 저장공간이 증가하는 단점이 있다.
• BFS는 재귀적으로 동작하지 않는데, 인접한 노드에 대해 먼저 탐색을 하기 때문에 재귀적으로 재호출할 필요가 없다.
• Search할 노드가 가로위치로 인접한 경우, DFS보다 효과적일 수 있다.
• Queue를 이용해 노드를 저장하는데, Queue는 탐색할 모든 노드를 저장하는 특징이 있다.
• 때문에 메모리를 벗어날 정도로 노드의 갯수가 증가하는 경우 DFS보다 메모리를 많이 소비할 수 있다.

 

 

 

DFS (Depth First Search)

 

DFS (깊이우선탐색)

 

• DFT(depth-first traversal)라고도 불린다.
• 깊이우선탐색
• 최대한 깊이 들어가보는 것.
• 위에서 아래로 내려오는 느낌으로 탐색
• 장점
  • 찾는 노드의 depth가 깊을수록 빠르다.
  • 메모리를 적게차지한다.
• 단점
  • 노드가 무한한 갯수로 존재하는경우, 무한루프에 빠진다.
• DFS의 활용
  • 가중 그래프의 최소 스패닝 트리 찾기
  • 길 찾기
  • 그래프에서주기 감지
  • 미로 문제
• 그래프의 모든 노드를 방문하는 경우 사용
• 단점은 최단 경로를 찾지 못하고, 시간이 오래 걸릴 수 있다.
• 백트래킹은 노드가 있을만한 곳을 되돌아가서 모두 살펴본다는 개념이다.
• Search할 노드의 세로위치가 깊을 수록, BFS보다 노드를 찾는 속도가 빠르다.
• 노드의 갯수가 주어진 컴퓨터의 자원(메모리, 소프트웨어 등)이 감당할 수 있는 범위 이상으로 증가하는 경우, Stack과 재귀방법을 활용하여 탐색을 진행하기 때문에 무한반복(무한루프) 에러가 발생할 확률이 높아진다.