개발 알다가도 모르겠네요

DFS & BFS 특 본문

자료구조/그래프

DFS & BFS 특

이재빵 2021. 1. 15. 01:20
728x90

DFS

  • 넓게(wide) 탐색하기 전에 깊게(deep) 탐색합니다.
  • 모든 노드를 방문하고자 할 때 이 방법을 선택합니다.
  • BFS보다 좀 더 간단합니다.
  • 검색 속도 자체는 BFS보다 느립니다. 

 

BFS

  • 깊게(deep) 탐색하기 전에 넓게(wide) 탐색합니다.
  • 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고자 할 때 이 방법을 선택합니다.
  • BFS는 재귀적으로 동작하지 않으며 선입선출(FIFO) 원칙으로 탐색합니다.
  • 간선의 가중치가 1이거나, 정점과 간선의 개수가 적을 때 사용하면 효율적입니다. 

 

 

'자료구조 > 그래프' 카테고리의 다른 글

이분 그래프 (Bipartite Graph) 를 간단하게 알아보자.  (0) 2021.01.17
BFS (너비 우선 탐색) 를 간단하게 알아보자.  (0) 2021.01.15
DFS (깊이 우선 탐색) 를 간단하게 알아보자.  (0) 2021.01.14
'자료구조/그래프' Related Articles more