너비 우선 탐색(BFS)

🟩 루트 노드에서 시작하여 인접한 노드에서 시작해서 인접한 노드를 먼저 탐색

지금 위치에서 갈 수 있는 것들을 모두 큐(queue)에 넣는 방식

큐에 넣을 시점에 해당 노드를 방문했다고 체크해야 한다. cf. DFS는 일단 들어가서 체크

큐와 while 반복문 활용

 

🟩 방법

그래프를 순차적으로 방문할 수 있어야 하고, 방문한 노드들은 다시 탐색할 일이 없도록 방문 처리되어야 한다.

 

1) 시작 정점 A를 큐에 넣고 방문 처리한다. A
2) 큐에서 A를 꺼내고, 인접 노드 B, C를 큐에 삽입 후 방문 처리한다. B C
3) 큐에서 B를 꺼내고, 인접 노드 D, E를 큐에 삽입 후 방문 처리한다. C D E
4) 큐에서 C를 꺼내고, 인접 노드 F, G를 큐에 삽입 후 방문 처리한다. D E F G
5) 위 과정을 스택에 아무것도 남지 않을 때까지 반복한다.

 

🟩 시간복잡도

깊이 우선 탐색(DFS)와 동일

V : 정점(노드)의 수, E : 간선의 수

 

인접 행렬에서의 시간 복잡도 O(V^2)

인접 리스트에서의 시간 복잡도 O(V+E)

 

🟩 장점

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

 

🟩 단점

경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기어거 공간을 필요로 한다.

해가 존재하지 않는다면 모든 그래프를 탐색한 후에도 실패로 끝난다.

무한 그래프의 경우에는 해를 찾지도 못하고, 끝내지도 못한다.

 

🟩 활용

1. 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 활용

2. 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 많이 멀지 않은 경우