DFS, BFS 구현 및 정리

DFS는 Depth First Search  깊이 우선 탐색으로

 

그래프가 있으면 그것을 전체적으로 탐색하는 방법중 하나이다.

 

DFS를 쓰는 이유로는

목표로 하는 노드가 깊은 단계에 있을 경우 해를 빨리 구할수있고, 경로상의 노드만 기억하면 되기에 저장공안의 수요가

비교적 적기 때문에 사용을 한다.

 

 

해가 없는 경로에 깊이 빠질수 있기에 실제의 경우에는 미리 지정한 임의의 깊이 까지만 탐색을 하고 목표로 하는 노드를 발견하지 못하였을 경우 다음 경로를 따라 탐색을 하도록 한다.

얻어진 해는 최적이 아닐 수도 있다.

 

작동 방식

 

처음 스택의 최상단 노드를 확인을 합니다.

그 다음 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리를 한다음,

방문 하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 뺍니다.

위와 같은 방법으로1, 2, 3, 6 , 7 , 4 ,5 순으로 탐색을 합니다.

 

재귀함수를 이용한 코드

 

 

BFS는 Breath First Search 너비 우선 탐색으로

 

너비를 우선으로 하여 탐색을 수행하고, 맹목적인 탐색을 하고자 할 경우에 사용하는 탐색 기법입니다.

최단 경로를 찾아 줍니다.

데이터 구조를 Queue를 사용하며, FIFO 원칙으로 검사를 진행합니다.

 

큐에서 하나의 노드를 꺼내고

해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 삽입을 하며 반복 진행 합니다.

 

위와 같은 방식으로 1, 2, 3, 4, 5, 6, 7

순서대로 탐색

 

소스 코드 구현

BFS자체로는 큰의미가 없기에 다른 알고리즘에 적용을 하여 사용하는 것이 핵심

 

Reference : https://www.youtube.com/watch?v=l0Rsu7dziws