DFS와 BFS

• DFS는 재귀를 사용하기 때문에 콜스택에 메모리를 차지한다. 그래서 BFS보다 성능이 딸림
  • BFS를 쓸 때 큐의 자료형으로는 리스트보다 Collection의 Dequeue가 가장 성능이 좋다. (파이썬 기준)
  • pop함수를 사용할 때 list는 O(n)이고 Deque는 O(1) 의 시간복잡도를 띄기 때문
• 대신 검색 대상 그래프가 크거나 경로를 저장해야 하는 경우는 DFS가 좋다
• 검색 대상 그래프가 크지 않고 최단거리/미로찾기를 구해야 하는 경우는 BFS가 좋다

 

 

• 시간복잡도 O(V+E)
  • DFS와 BFS는 완전탐색이기 때문에 Vertex와 Edge의 개수만큼 걸린다.

 

 

tip.

시간복잡도는 대충 10^8보다만 작으면 된다