알고리즘 이해하기 (1)에 이어지는 글이다.

✰✰ 아래 내용들은 <Hello Coding 그림으로 개념을 이해하는 알고리즘>과 <파이썬 자료구조와 알고리즘> 등 내용을 정리한 것임을 밝힙니다. 만약 문제가 있을 시 연락 바랍니다. ✰✰

너비 우선 탐색 알고리즘은 최단 경로를 구할 때 유용하게 사용할 수 있다.
최단 경로를 구하려면 문제를 그래프로 모형화하고, 너비 우선 탐색으로 문제를 풀어야 한다.

먼저 그래프라는 개념을 알아본다.

그래프 | graph

그래프는 연결의 집합을 모형화한 것으로, 정점(node 혹은 vertex)들이 간선(edge 또는 arc)으로 연결된 추상 네트워크다. 즉 그래프는 노드와 간선의 집합으로 정의되며 이를 수식으로 표현하면 G = (V, E) 와 같다. 정점은 여러 개의 다른 정점과 바로 이어질 수 있고 바로 이어진 정점을 이웃(neighbor)이라고 한다.

그래프는 방향이 있는 그래프(directed graph, 유향 그래프)와 방향이 없는 그래프(undirected graph, 무향 그래프)가 있다.  유향 그래프의 경우 순서가 있으므로 말단(leaf) 노드가 존재한다.

너비 우선 탐색 

너비 우선 탐색은 그래프를 대상으로 하는 탐색 알고리즘이다. 주로

유형 1 : 정점 A에서 정점 B로 가는 경로가 존재하는가?
유형 2 : 정점 A에서 정점 B로 가는 최단 경로는 무엇인가?

와 같은 질문에 대답하는 데 사용된다.