dfs/bfs 정리(1)

dfs와 bfs는 역할은 비슷하지만 그 표현방법이 다릅니다.

대표적으로 dfs는 스택으로 표현하고

              bfs는 큐로 표현을 합니다.

 

bfs와 dfs를 들어가기에 앞서 스택과 큐를 간단하게 알아보겠습니다.

 스택 : push(), pop()

으로 데이터를 넣고 뺍니다.

즉, 박스 쌓기와 비슷합니다.

하지만 프로그래밍의 특이성 때문에 실제처럼 구현하기는 어렵습니다.

그래서 

하얀게 박스이고 노란게 pop, 초록색이 push라 생각했습니다.

즉, 스택은 한쪽에서 pop과 push가 진행이 된다는 것을 알 수 있었습니다.

또, 스택은 선입 후출입니다.

그러면 큐는 어떨까요?

큐 : append(), pop()

 스택과 마찬가지로 위의 명령어로 데이터를 넣고 빼는 형식입니다.

(언어마다 조금씩 다른것 같군요.)

아무튼 큐는 어떻게 동작하게 될까요?

큐는 종종 줄 서기와 비유가 되곤합니다.

하지만 이 역시도 프로그래밍상에서는 실제와 조금은 다를 수 있습니다. (그래도 큐는 그래도 비슷해보이는군요)

그래서

 

아까와 마찬가지로 초록색이 넣는 부분이고 노란색이 빼는 부분입니다.

즉, 먼저 들어온게 먼저 나오게 되는 선입 선출 구조로 되어있습니다.

이건 딱히 중요하지는 않지만 저는 큐를 볼때 관통한다는 느낌을 받았습니다.

스택은 한쪽에서 넣고 빼고를 진행하지만.

큐는 한쪽에서는 넣고 다른 한쪽에서 빼는걸 진행하기 때문이죠.

이 다음에는 인접행렬과 인접 리스트를 자바로 구현하는 시간을 가져보도록 하겠습니다.