DFS & BFS

오늘 유튜브에서 DFS와 BFS를 쉽게 설명하는 영상을 봐서 

BFS와 DFS에 대한 포스팅을 하려고 한다

 

넷플릭스에서 한개의 드라마가 16화까지 나오면 한번에 끝까지 보는것을 DFS

여러개의 드라마를 1회씩 나올때마다 보는것을 BFS 아주 이해가 쉬웠다.

 

3이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 비교

 

출처 https://namu.wiki/w/BFS

 

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

💡DFS와 BFS의 시간복잡도

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

DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.

 

N은 노드, E는 간선일 때

인접 리스트 : O(N+E)
인접 행렬 : O(N²)

일반적으로 E(간선)의 크기가 N²에 비해 상대적으로 적기 때문에

인접 리스트 방식이 효율적임

 

출처 : https://devuna.tistory.com/32