[ch 14] 그래프_2(탐색)

[주제]

- 그래프의 탐색 종류와 구현 모델

[정의]

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

- DFS 알고리즘은 어떠한 선택을 하건 잘 동작하며,

  누구를 우선 선택할 것인지에 대한 기준은 개발자가 결정해도 되는 단순한 문제

★ 핵심 3가지

- 한 사람에게만 연락하면 됨

- 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알림

- 처음 연락을 시작한 사람의 위치에서 연락은 끝이 남

■ 그림(깊이 우선 탐색의 과정)

- '나나'로부터 연락을 시작한다고 가정

- 나나는 '만수' 또는 '포포'에게 연락이 가능한데 여기서는 '포포'를 선택

- 포포는 연결되어 있는 '길동'에게 연락

- 길동은 '만수' 또는 '김민' 또는 '철수'에게 연락이 가능한데 여기서는 '철수'를 선택

- 최종적으로 '김민'까지 연락이 완료

- 김민은 더 이상 연락을 해야하는 대상이 없기 때문에 이전 대상에게 연락 기회를 넘겨줌

- 철수도 없기 때문에 계속 이동하여 '길동'에 도착

- 길동은 연결되어 있는 대상 중 '만수'가 아직 연락이 안되어 있기 때문에 만수에게 연락

- 모두에게 연락이 된 것은 맞지만 완벽하지는 않은 상태

- 시작 지점이었던 '나나'에게 위 그럼처럼 '동우' 같이 연락이 안된 대상이 존재할수도 있기 때문

- 때문에, 시작지점까지 다시 연락이 완료되었는지 확인하는 과정이 필요

■ 그림(깊이 우선 탐색의 구현 모델)

- 스택: 경로 정보의 추적을 목적으로 사용

- 배열: 방문 정보의 기록을 목적으로 사용

- '나나'로부터 시작(방문)한다는 가정

- 다음은 '포포'를 선택. 방문 정보를 기록

- 나나는 기회가 넘겨졌기 때문에 스택에 저장

- 이어서 '김민'에게 도착까지 반복적인 과정 생략

- 김민은 더 이상 연락할 대상이 없으므로 복귀를 시작

- 이전 대상을 찾을 땐 스택에서 꺼낸(POP) 대상이 이전 대상과 같음

- 철수도 연락할 대상이 없으므로 복귀하여 '길동'까지 도착

- 길동은 '만수'라는 대상이 있기 때문에 다시 스택에 저장(PUSH)됨

- 만수는 더 이상 연락할 대상이 없으므로 시작 지점인 '나나'까지 복귀를 진행

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

- 자신에게 연락 기회가 있을 때 자신에게 연결된 모든 대상에게 연결하는 방식

  ※ DFS와 다르게 복귀를 하지 않음

- 2개 이상의 연락 대상이 있을 때 순서는 중요하지 않음

■ 그림(너비 우선 탐색의 과정)

- '만수'로부터 시작한다는 가정

- 연결된 '나나'와 '길동'에게 연락

  ※ 순서 상관없음

- 포포는 '나나'와 '길동'에게 연락을 받을 수 있는 상태

- 둘 중에 하나에게 연락을 받으면 더 이상 연결된 대상이 없으므로 종료

- 길동은 연결 대상이 존재하므로 계속 진행

- 김민은 더 이상 연락 대상이 없으므로 종료

- 철수는 마지막 대상인 '민희'에게 연락

- 민희가 마지막이기 때문에 '철수'는 연락뿐만 아니라 연락 기회를 민희에게 줘야함

- 위 그림처럼 민희가 또 다른 연락 대상이 존재할 수도 있기 때문

■ 그림(너비 우선 탐색의 구현 모델)

- 큐: 방문 차례를 기록하는 목적으로 사용

- 배열: 방문 정보의 기록을 목적으로 사용

- '만수'로부터 시작(방문)한다는 가정

- 만수는 '큐'에 기록되지 않음

- 연락 가능한 대상인 '나나'와 '길동'에게 연락

- 큐에 순서대로 저장

- 나나가 '포포'에게 연락을 했으므로 큐에서 빠져나가고, '포포'가 큐에 새로 저장됨

- 포포는 더 이상 연락할 대상이 없어도 큐에서 빠져나오지 않음

- 길동은 연락 대상인 '김민'과 '철수'에게 연락. 각각 순서대로 큐에 저장

- 최종적으로 민희에게 연락이 되면, 더 이상 연락할 대상이 없으므로 큐에 저장된 모든 정보를 빼냄