너비 우선 탐색

너비 우선 탐색을 사용하면 두 항목간의 최단 경로를 찾을수 있습니다.

그래프 알고리즘은 가장 유용한 알고리즘 입니다.

예 )

체커 게임에서 가장 적은수로 승리할수 있는 방법을 계산하는 인공지능

맞춤법 검사기(실제 단어에서 가장 적은 개수의 글자를 고쳐서 올바른 단어를 만드는 방법을 찾는다)

우리 주변에 가까운 맛집 , 병원 , 편의점등을 찾는다

최단 경로 문제를 푸는 알고리즘을 너비 우선 탐색이라고 합니다.

그래프란 무엇인가 ?

그래프란 연결의 집합을 모형화 한것이다.
그래프는 정점과 간선으로 이루어집니다

정점은 여러개의 다른 정점과 바로 이어질수 있습니다.
이렇게 바로 이어진 정점을 이웃이라고 합니다.

너비 우선 탐색은 그래프를 대상으로 하는 다른 종류의 탐색 알고리즘 입니다.
너비 우선 탐색은 다음과 같은 두가지 종류의 질문에 대답하는데 도움이 됩니다.

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

질문유형 1 경로가 존재하는가의 대한 예시

내가 망고농장의 주인이라고 했을떄 내 친구들중에 판매상이 있는지 살펴보고 싶다
친구목록에서 각각의 사람이 망고 판매상인지 아닌지 확인해 본다
만약 내 친구중에 망고 판매상이 없다고 하면 이제 나의 친구의 친구를 찾아본다
최종적인 목표는 망고 판매상을 찾는것이다
만약 내 친구가 망고 판매상이 아니라면 내 친구의 친구도 목록에 올려 그 친구가 판매상인지 찾아본다 그럼 결과적으로
그녀의 친구, 그녀 친구의 친구, 이런식으로 망고 판매상에 도달할떄까지 전체 네트워크를 탐색하게 된다, 이러한 알고리즘이 너비 우선 탐색이다.

너비 우선 탐색이 진행될수록 탐색 범위는 출발점에서 멀어집니다. 그러니까 2촌 관계를 확인하기 이전에 1촌 관계부터 확인해야한다.