[그래프 탐색] 너비 우선 탐색, 깊이 우선 탐색

너비우선탐색: 정점을 탐색할 때 시작점에 가까운 정점부터 탐색하는 방식, 시작점부터 가까운 순으로 너비를 넓혀 가며 탐색하는 방식, 목표가 시작점에 가까이 있으면 탐색이 빨리 종료

가장 먼저 후보가 된 정점을 선택하며, 시작점에 가까운 정점이 빨리 후보가 되므로 시작점에서 가까운 것 부터 탐색하게 됨 

 

깊이 우선 탐색: 정점을 탐색할 때 하나의 길을 끝까지 따라가며 더 이상 진행할 수 없는 곳에 다다르면 다음 후보가 되는 길을 따라감, 하나의 길을 깊이 있게 찾아가는 방식 

가장 최근에 후보가 된 정점이 선택되므로 이 정점을 따라 새로운 길을 찾아 나가게 됨