[알고리즘] DFS와 BFS 정리

DFS: Depth First Search

깊이를 우선으로 하는 검색 방법이다.

재귀 함수, 스택으로 구현한다.

 

BFS: Breadth First Search

너비를 우선으로 하는 검색 방법이다.

큐로 구현한다.

TREE에서 DFS, BFS 작동 방식

위의 그림은 7을 찾아가는 과정을 DFS, BFS로 표현한 그림이다.

 

DFS는 빨간색으로, BFS는 파란색으로 그려봤다.

 

DFS는 tree의 level과 관계 없이 최상단(1)부터 각각의 leaf node까지를 찾아본 후,

다음 leaf node까지를 계속해서 검색하다 7이 나오면 종료한다.

 

BFS는 같은 level의 node들을 모두 검색하고, 검색한 node들의 하위 node들을 검색하는 방식으로 작업이 수행된다.

 

그래서 DFS의 경우 5번, BFS의 경우 6번만에 7을 찾아 작업을 종료했다.