스택, 큐, DFS, BFS

스택 (Stack)

• 박스구조와 같음 
• 선입후출

큐 (Queue)

• 입구와 출구가 모두 뚫려있는 형태
• 선입선출

재귀함수 (Recursive Function)

• 자기자신을 다시 호출하는 함수
• 반복문을 이용하여 동일한 기능을 구현할 수 있음
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임
  • 그래서 스택을 사용해야 할 때 스택 라이브러리 대신에 재귀 함수를 이용하는 경우 많음

DFS (Depth-First-Search)

• 깊이우선 탐색
• 그래프의 깊은 부분을 우선 탐색하는 알고리즘
• 스택 자료구조(혹은 재귀 함수)를 이용

구체적인 동작과정 

1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

3. 더 이상 2번의 과정을 수행할 수 없을 떄 까지 반복

예시 이미지

시작노드 1을 방문처리

2,3,8중 가장 작은 노드인 2를 스택에 넣고 방문처리

그 다음 7 

그 다음 6 (더 이상 깊게 갈 수 없음 => 스택에서 6을 꺼냄)

... 

최종 탐색 순서 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

BFS(Breadth-Firsh-Search)

• 너비 우선 탐색
• 그래프에서 가까운 노드부터 우선적으로 탐색
• 큐 자료구조 이용

구체적인 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리

3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복

예시 이미지

시작노드 1을 큐에 삽입 후 방문처리

큐에서 노드 1꺼내 방문하지 않은 인접 노드 2 3 8 큐에 삽입하고 방문 처리

...

최종 탐색 순서 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6