DFS / BFS

DFS (깊이 우선 탐색)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식

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

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림 

 

 

 

BFS (너비 우선 탐색)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

 

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.
ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

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

 

 

DFS (깊이우선탐색)	BFS (너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 스택 또는 재귀함수로 구현	현재 정점에 연결된 가까운 점들부터 탐색 큐를 이용해서 구현
검색대상의 그래프가 큰 경우에 DFS를 고려	검색대상의 규모가 크지않고, 검색 시작지점으로부터 원하는 대상이 멀지 않다면 BFS를 고려

 

DFS와 BFS 의 시간복잡도 

(*시간복잡도: 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 걸리는 시간) 

[Algorithm] 시간 복잡도(Time complexity) 학습

※ 두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간복잡도는 동일함

 

DFS와 BFS의 시간복잡도를 구하는 방법

= 다음 노드가 방문하였는지를 확인하는 시간 +  각 노드를 방문하는 시간  

 

 

 

 

 

 

참고링크)

DFS, BFS의 설명, 차이점