BFS / DFS

✍️ 정의

BFS 란?

• Breadth-First Search
• 시작 정점 방문 후 가까운 정점을 우선 방문한다.
• 넓게 탐색하는 방법
• 두 노드 사이의 최단 거리 및 최단 경로를 구할 때 자주 사용한다.
• 큐를 이용해서 구현
• 장점
  • 최적해 찾음을 보장한다. (미로찾기 등 최단거리 구하기)
  • 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않을 때.
• 단점
  • 경로의 특징을 가지지 못한다.

BFS

DFS 란?

• Depth-First Search
• 시작 정점 방문 후에 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식
• 스택 또는 재귀함수로 구현
• 장점
  • 최선의 경우 빠르게 해를 찾을 수 있다.
  • 검색 대상 그래프가 정말 크다면 DFS를 고려
• 단점
  • 찾은 해가 최적의 해가 아닐 가능성이 있다.

DFS

⏰ 시간복잡도

• 시간복잡도는 동일하며, 그래프 구현에 따라서 시간복잡도가 달라진다.
• 연결 리스트로 구현한 그래프 : O(n+m)
• 행렬로 구현한 그래프 : O(n^2)

인용

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-BFS-DFS

[알고리즘/Java] BFS / DFS

https://blog.naver.com/newbongman/222987762797

DFS, BFS의 설명, 차이점