Algorithm - Breadth First Search(너비 우선 탐색)

Breadth-First Search(BFS, 너비 우선 탐색) :

root 노드(혹은 다른 임의의 노드)로부터 시작해서 인접한 노드를 먼저 탐색하는 방법. (최단 경로 탐색, 임의 경로 탐색) / 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어진 노드는 나중에 방문하는 traverse방법. / 깊게(deep하게) 탐색하기 전 넓게(wide하게) 탐색. / 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이 방법을 사용. / 예) facebook같은 거에 존재하는 모든 친구 관계를 그래프로 표현한 후 Hong과 Jo 사이에 존재하는 경로를 찾을때. DFS - 모든 친구 관계를 다 살펴봐야 할 수도 있음. BFS - Hong과 가까운 관계부터 탐색. / BFS가 DFS보다 좀 더 복잡함. 

 

Breadth-First Search의 특징 : 

- 직관적이지 않은 면이 있음(BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색). / 재귀적으로 동작하지 않음. / 그래프 탐색할 때 어떤 노드를 방문했는지 여부를 반드시 검사해야함. (검사하지 않을시 무한 loop에 빠질 수 있음). / BFS는 방문한 노드들을 차례로 저장한 후 꺼내는 자료 구조인 Queue를 사용 -> FIFO(선입선출)을 원칙으로 탐색, 일반적으로 Queue를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작함. / Prim Algorithm, Dijkstra Algorithm과 유사함.

장점 - 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장

단점 - 경로가 매우 길 경우에는 탐색 branch가 급격히 증가함에 따라 보다 많은 memory를 요구함 / 해가 존재하지 않는다면 유한 그래프일때, 모든 그래프를 탐색하고 나서도 찾지못하고 끝남. / 무한 그래프일때는 결코 해를 찾지도 못하고 끝내지도 못함.

 

인접 행렬(2차원 배열)로 그래프 표현 :

① -> ② , ① -> ③, ① -> ④, ② -> ③, ④ -> ③ 일때

        ①      ②      ③      ④

①     0        1       1       1

②     0        0       1       0

③     0        0       0       0

④     0        0       1       0

장점 - 구현이 쉽고 연결 여부를 확인하기 쉬움(array[i][j]가 1인지 0인지만 알면 되기 때문에)

단점 - 노드 [i]와 연결된 모든 노드들에 방문해보고 싶을때 array[i][1]부터 array[i][전체 노드 개수]를 모두 확인해봐야 되기 때문에 시간 복잡도가 큼.

인접 리스트로 그래프 표현 :

array[i]는 노드 i에 연결된 노드들을 원소로 갖는 리스트

① -> ② , ① -> ③, ① -> ④, ② -> ③, ④ -> ③ 일때

array[1] ->  ②      ③      ④

array[2] ->  ③

array[3] ->

array[4] ->  ③

 

Breadth-First Search의 과정 :

깊이가 1인 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마침.

- 1. 노드 a(시작 노드)를 방문하고 방문한 노드 체크(Queue에 방문된 노드를 삽입(enqueue) / 초기 상태의 queue에는 시작 노드만이 저장. 즉 a노드의 이웃 노드들을 모두 방문한 후 그다음으로 넘어감) > 2. queue에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문(인접한 노드가 없다면 queue의 앞에서 노드를 꺼냄(dequeue), queue에 방문된 노드를 삽입(enqueue)) > 3. queue가 소진될 때까지 계속함.

(탐색 시작 노드를 큐에 삽입하고 방문처리 -> 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리 -> 반복)