DFS와 BFS

DFS와 BFS는 탐색 알고리즘입니다.

 

● DFS == > 깊이 우선 탐색

● BFS ==> 너비 우선 탐색

 

 

DFS와 BFS는 스택과 큐 기반으로 흘러가기 때문에 

스택과 큐의 일부분을 먼저 설명하겠습니다.

(자세한 스택과 큐 설명은 따로 정리해 둠)

 

●스택 => push와 pop만 가능

스택은 가장 마지막에 들어간 애가 먼저 나오는 후입선출 구조입니다.

(LIFO 혹은 FILO) <-- 자세한 것은 2월 3일 작성된 글 참고

 

 

● 큐 ==> 먼저 들어온 아이가 먼저 나가는

선입선출 방식입니다.

 

이해를 돕기 위해  스택 선언만 간단하게 작성한 코드를 보여드리겠습니다.

 

#include<stido.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100 //스택의 사이즈 선언
typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
    	int top;
}Stack Type;

 

이제 두 탐색 알고리즘입니다.

 

 

우선 DFS

DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완전히 탐색하는 방법입니다. (스택 사용)

또 DFS는 자기 자신을 호출할 수 있기 때문에 순환 알고리즘에 속합니다.

생각보다 복잡하게 구성되어 있기에 무한루프에 빠질 가능성이 있음으로

어떤 노드를 방문했는지 검사하는 것이 필요합니다.

 

BFS

 

시작 정점으로부터 가까운 노드부터 방문하고 멀리 떨어진 노드는 나중에 방문합니다. (큐 사용)

BFS는 DFS와 다르게 자기 자신을 호출하지 않습니다.

BGS는 단계별로 처리하기 때문에 막히는 일은 자주 발생하지 않습니다.

 

++ 그리디 

 

 

그리디는 다음 상황까지 냐다보지 않고 현 상황만 판단하여 비효율적입니다.