너비 우선 탐색 (BFS)

역추적하기 전에 각 경로를 따라 가능한 한 깊이 들어가서 그래프를 탐색합니다. 스택이나 재귀를 사용하여 구현되어 재귀적 문제에 자연스럽습니다. 경로 찾기, 순환 감지, 위상 정렬, 미로 생성에 사용됩니다.

가중치가 있는 그래프에서 단일 소스 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다. GPS 내비게이션 시스템과 네트워크 라우팅 프로토콜을 지원합니다. 우선순위 큐를 사용하는 탐욕적 접근법으로 음수가 아닌 가중치에 효율적으로 작동합니다.

휴리스틱을 사용하여 최단 경로를 찾는 최선 우선 탐색 알고리즘입니다. f(n) = g(n) + h(n)을 사용하여 다익스트라 알고리즘과 탐욕적 최선 우선 탐색을 결합합니다. 게임, 로봇 공학, GPS 내비게이션의 효율적인 경로 탐색에 널리 사용됩니다.