BFS(Breadth-First Search)는 단순 알고리즘과 고급 알고리즘 모두에서 매우 자주 사용되는 그래프 순회 방법입니다. Breadth-First Search는 소스 노드에서 시작하여 점진적으로 멀어지는 그래프의 개별 수준을 통해 작동합니다. 이것은 애니메이션에서 명확하게 보여집니다.
간단한 BFS를 작성하려면 처음부터 끝까지 가져갈 수 있는 데이터 구조인 대기열로 작업할 수 있어야 하며 그래프를 다음 형식으로 저장할 수 있어야 합니다. 인접 목록의.
알고리즘에 대한 공식적인 설명
1) 검색이 시작되는 꼭지점의 번호를 초기 빈 큐에 배치합니다.
2) 큐의 시작 부분에서 정점 U를 추출하고 별도의 배열에서 사용된 것으로 표시합니다.
3) 대기열의 끝에서 정점 U의 가장자리를 사용하여 도달할 수 있고 아직 표시되지 않은 모든 정점을 추가합니다.
4) Queue가 비어 있으면 연결된 그래프의 모든 노드를 스캔한 것이며 그렇지 않으면 2단계로 돌아갑니다.
작업의 어려움
최악의 경우 알고리즘은 그래프의 모든 노드를 방문하므로 그래프를 인접 리스트 형태로 저장할 때 알고리즘의 시간 복잡도는 O(|V| + |E|)이며, 여기서 V는 집합 그래프의 꼭짓점의 집합이고 E는 가장자리 집합입니다.
즉, 알고리즘은 모서리 수 + 정점 수에 대해 최악의 경우에 작동합니다.