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

 

 

 

 

 

1. 깊이 우선 탐색 (Depth First Search)

트리나 그래프와 같이 정점, 간선, 노드로 이루어진 구조를 순회하는 방법중의 하나이다.

특정 시작 노드 부터 연결된 노드들 중 가장 우선순위가 높은 방향으로 깊이 파고들다가,

더이상 연결되는 노드가 없을 때 시작노드로 되돌아가 다른 노드를 탐색한다. 

장점	비교적 단순한 알고리즘으로 구현이 가능하며, 트리구조 탐색에 적용이 용이하다.
단점	BFS 보다는 느리다. 깊이 혹은 목표 노드의 값이 주어지지 않은 경우 비효율적이다.

 

 

DFS 순환 알고리즘 , 백트랙(backtrack)

파이널 노드 탐색 후 다시 위로 되돌아가 탐색 하기 때문에, 자기 자신을 호출하는 순환 알고리즘(재귀)의 형태를 지닌다.

 

 

 

---

 

2. 너비 우선 탐색 (Breadth First Search)

 

트리구조 혹은 그래프 구조에서 특정 시작 노드(정점) 레벨부터 같은 레벨의 노드들을 순회하는 방법이다.

무한루프에 빠지지 않기 위해 한 레벨에서 어떤 노드를 방문했었는지, 몇번째 노드를 순회중인지를 기록하거나 파악 할 수있어야 한다.  

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용 한다. 

 

BFS 큐(queue)

해당 깊이/레벨에 있는 모든 정점들을 방문하고 난 후, 다음 깊이/레벨의 정점들을 순서대로 방문해 나가기 위해 큐(queue)자료구조를 사용한다.
방문한 노드들을 차례로 queue에 저장한 후 선입선출(FIFO) 로 꺼낸다.