BFS(Breadth-First Search)의 정의와 특징
정의
BFS는 너비 우선 탐색 알고리즘이며, 그래프의 모든 정점을 방문하는 방법 중 하나입니다. 시작 정점에서 시작하여 가까운 정점부터 차례로 방문하고, 그 다음으로 인접한 정점들을 방문하는 방식으로 진행됩니다.
특징
- 단계별 탐색: 가까운 정점을 먼저 방문하고, 그 다음 인접한 정점을 방문합니다.
- 큐(Queue) 사용: 방문할 정점을 큐에 저장하여 처리합니다.
- 탐색 순서 기록: 각 정점이 방문되는 순서가 레벨별로 이루어집니다.
- 최단 경로: 시작 정점에서 다른 정점까지의 최단 경로를 찾을 때 사용할 수 있습니다.
- 시간 복잡도: 일반적으로 (O(V + E))입니다. 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.
장점
- 최단 경로 보장: 시작점에서 각 정점까지의 최단 경로를 찾을 수 있습니다.
- 구현이 상대적으로 간단: 큐를 사용하는 것 외에 추가적인 자료 구조가 필요 없습니다.
- 결과의 일관성: 동일한 그래프와 시작 정점에서는 항상 동일한 탐색 순서를 보장합니다.
단점
- 메모리 사용량: 모든 정점을 저장해야 하기 때문에 메모리 사용량이 클 수 있습니다.
- 시간 복잡도: 대형 그래프에서는 시간이 오래 걸릴 수 있습니다.
사용 예
- 최단 경로 문제: 두 노드 사이의 최단 경로를 찾을 때
- 네트워크 크롤링: 웹 페이지의 연결 관계를 분석할 때
- 소셜 네트워크: 친구 추천 시스템 등에서 가까운 친구 관계를 찾을 때
C와 Python에서의 비교
C
Python
정리
C는 성능과 메모리 관리 측면에서 이점이 있을 수 있지만, 구현이 복잡합니다. Python은 직관적이고 간결한 코드로 빠르게 구현할 수 있으며, 라이브러리를 활용할 수 있는 장점이 있습니다.
