0-1 BFS
0-1 BFS은 간선 가중치가 0 또는 1인 그래프의 최단 경로를 덱으로 빠르게 구한다 최단 경로 그래프 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로...
| 분류 | 알고리즘 · 최단 경로 그래프 알고리즘 |
|---|---|
| 목적 | 간선 가중치가 0 또는 1인 그래프의 최단 경로를 덱으로 빠르게 구한다 |
| 처리 방식 | 현재 정점에서 가중치 0인 간선의 도착 정점은 덱 앞에, 가중치 1인 간선의 도착 정점은 덱 뒤에 넣는다 |
| 복잡도·성능 | 시간 O(V+E), 공간 O(V) |
| 필수 조건 | 간선 가중치가 0 또는 1이어야 한다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
0-1 BFS은 간선 가중치가 0 또는 1인 그래프의 최단 경로를 덱으로 빠르게 구한다 최단 경로 그래프 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 현재 정점에서 가중치 0인 간선의 도착 정점은 덱 앞에, 가중치 1인 간선의 도착 정점은 덱 뒤에 넣는다. 거리 완화가 발생한 정점만 처리하면 우선순위 큐 없이 거리 순서를 유지할 수 있다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 시간 O(V+E), 공간 O(V) 올바르게 적용하려면 간선 가중치가 0 또는 1이어야 한다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 가중치가 제한된 그래프에서 다익스트라보다 간단하고 빠르며, 일반적인 비가중 BFS와 가중 최단 경로의 중간 모델이다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]