너비 우선 검색 알고리즘: 개요, 중요성 및 응용

게시 됨: 2020-12-23

그래프는 우리 주변에 있습니다. 그래프는 노드와 에지의 상호 연결된 네트워크로 생각할 수 있습니다. Facebook의 친구, LinkedIn의 연결 또는 Twitter/Instagram 팔로워가 소셜 그래프를 구성합니다. 마찬가지로 A 지점에서 B 지점으로 이동하려는 경우 Google 지도에서 시각화할 수 있는 여러 경로를 통해 이동할 수 있습니다.

A 지점에서 B 지점까지의 이러한 모든 다중 경로 옵션도 그래프를 구성합니다. 그래프는 어디에나 존재하기 때문에 학계와 현실 세계에서 모두 접하게 되는 가장 일반적인 데이터 구조 중 하나입니다. 그리고 그래프에서 수행할 수 있는 가장 빈번한 작업 중 하나는 그래프 순회입니다.

그래프 순회란 무엇입니까?

Graph Traversal은 그래프의 모든 노드를 속도와 정밀도로 정확히 한 번 방문하는 방법입니다. 무한 루프에 걸리지 않고 방문한 노드의 시퀀스를 인쇄할 수 있는 고급 그래프 검색 알고리즘입니다. Depth-First Search , Breadth-First Search , Djikstra's Algorithm , A-Star 알고리즘 등과 같은 많은 그래프 탐색 알고리즘이 있습니다.

이 기사에서는 BFS( Breadth First Search Algorithm )에 대해 자세히 설명 합니다.

그래프 구조

BFS 후드 아래에서 자세히 살펴보기 전에 위의 그래프를 통해 몇 가지 그래프 용어에 익숙해지도록 합시다.

루트 노드 – 순회 프로세스를 시작하는 노드입니다. 단순화를 위해 A를 루트 노드로 간주할 수 있습니다.

레벨 – 레벨은 루트 노드에서 등거리에 있는 모든 노드의 모음입니다. 따라서 노드 A가 레벨 0에 있다고 생각하면 노드 B와 C는 레벨 1에 있고 노드 D, E, F는 레벨 2에 있습니다. 노드의 레벨 번호를 결정하기 위한 간단한 경험적 방법은 숫자를 계산하는 것입니다. 상기 노드와 루트 노드 사이의 에지. 이것은 루트 노드를 레벨 0으로 정의한 경우에만 작동합니다.

부모 노드 – 노드의 부모 노드는 한 수준 위에 있고 인접한 노드입니다. 해당 노드가 시작된 노드로 생각할 수 있습니다. A는 B와 C의 부모 노드입니다.

자식 / 자식 노드 – 분기되어 부모 노드에 인접한 노드입니다. B와 C는 A의 자식 노드입니다.

읽기: 상위 10가지 데이터 시각화 기법

너비 우선 탐색이란 무엇입니까?

BFS는 트리 또는 그래프를 효율적으로 탐색하기 위한 그래프 탐색 알고리즘입니다. 알고리즘은 초기 노드(루트 노드)로 시작한 다음 해당 분기의 모든 노드까지 특정 분기로 내려가는 깊이 우선과 반대로 너비 우선 방식으로 인접 노드를 모두 탐색합니다. 방문됩니다. 간단히 말해서, 그래프는 해당 수준의 모든 노드를 방문하고 표시할 때까지 수준 아래로 이동하지 않고 수준별로 이동합니다.

FIFO(선입 선출) 원칙에 따라 작동하며 대기열 데이터 구조를 사용하여 구현됩니다. 노드를 방문하면 대기열에 삽입됩니다. 그런 다음 기록되고 모든 자식 노드가 대기열에 삽입됩니다. 이 프로세스는 그래프의 모든 노드를 방문하여 기록할 때까지 계속됩니다.

위에 주어진 그래프에 대한 BFS 알고리즘에 대한 자세한 대기열 작업을 살펴보겠습니다.

() – 대기열을 나타냅니다.

[] – 인쇄된 출력물을 나타냅니다.

  1. 대기열에 A를 삽입합니다(a).
  2. A를 인쇄하고 B와 C를 대기열(cb)[a]에 삽입합니다.
  3. B를 인쇄하고 자식 노드 D와 E를 대기열(edc)[ba]에 삽입합니다.
  4. C를 인쇄하고 자식 노드 F를 대기열(fed)[cba]에 삽입합니다.
  5. D를 인쇄하고 자식 노드를 대기열에 삽입합니다. 아무도 없습니다. (fe)[dcba]
  6. 자식 노드 F가 이미 대기열에 삽입된 E를 인쇄합니다. (f)[edcba]
  7. 인쇄 F. [fedcba]

BFS 알고리즘이 중요한 이유

방대한 데이터 세트를 빠르게 검색하기 위한 방법으로 BFS를 배포하는 데에는 여러 가지 이유가 있습니다. 개발자와 데이터 엔지니어가 선호하는 주요 기능은 다음과 같습니다.

  • BFS는 그래프의 모든 노드를 효과적으로 탐색하고 모든 노드를 탐색할 수 있는 최단 경로를 찾을 수 있습니다.
  • 전체 그래프를 탐색하는 데 필요한 반복 횟수는 다른 검색 알고리즘보다 적습니다.
  • 대기열을 사용하여 구현되기 때문에 아키텍처가 강력하고 안정적이며 우아합니다.
  • 다른 알고리즘과 비교하여 BFS의 출력은 정확하고 오류가 없습니다.
  • BFS 반복은 무한 루프에 빠질 위험 없이 원활하게 진행됩니다.

체크아웃: 복제할 수 있는 데이터 시각화 프로젝트

BFS 알고리즘의 응용

BFS 알고리즘은 간단하고 설정이 용이하기 때문에 다양한 주요 실제 상황에서 널리 사용됩니다. 몇 가지 두드러진 응용 프로그램을 살펴보겠습니다.

검색 엔진 크롤러 – Google이나 Bing이 없는 세상을 상상해 보십시오. 당신은 할 수 없습니다. 검색 엔진은 인터넷의 중추입니다. 그리고 BFS 알고리즘은 검색 엔진의 중추입니다. 웹 페이지를 색인화하는 데 사용되는 기본 알고리즘입니다. 알고리즘은 소스 페이지(루트 노드)에서 여정을 시작한 다음 해당 소스 페이지의 모든 링크를 광범위한 방식으로 따릅니다. 각 웹 페이지는 그래프에서 독립적인 노드로 생각할 수 있습니다.

가중되지 않은 그래프 탐색 – BFS는 가중되지 않은 그래프에서 최단 경로와 최소 스패닝 트리를 식별할 수 있습니다. 최단 경로를 찾는 것은 BFS가 이상적으로 적합한 최소한의 에지를 갖는 경로를 찾는 것에 관한 것입니다. 최소한의 노드를 방문하여 작업을 완료할 수 있습니다.

GPS 탐색 – BFS는 GPS 시스템을 활용하여 시작 지점에서 가능한 모든 인접 위치를 표시하여 지점 A에서 B로 원활하게 탐색할 수 있습니다.

브로드캐스팅 – 브로드캐스트 네트워킹은 신호와 데이터를 전달하는 단위로 패킷을 사용합니다. BFS 알고리즘은 이러한 패킷이 도달해야 하는 네트워크의 모든 노드로 이동하도록 조정합니다.

P2P 네트워크 – 토렌트 또는 기타 파일 공유 네트워크는 P2P 통신에 의존합니다. BFS는 데이터 전송이 더 빨리 일어날 수 있도록 가장 가까운 노드를 찾는 데 탁월합니다.

읽어보기: 데이터 시각화의 이점

결론

따라서 너비 우선 탐색 알고리즘 은 현대 인터넷의 가장 중요한 알고리즘 중 하나입니다. 이 블로그가 검색 알고리즘 탐색의 편리한 출발점이 되기를 바랍니다.

upGrad에서 호스팅되는 IIIT Bangalore가 제공하는 데이터 과학 PG 디플로마를 선택하는 것이 좋습니다. 여기에서 코스 강사와 1-1로 질문을 받을 수 있기 때문입니다. 이론 학습에 중점을 둘 뿐만 아니라 학습자가 실제 프로젝트에 직면할 준비를 하고 데이터 과학 분야에서 고임금 직업을 얻는 데 도움이 되는 인도 최초의 NASSCOM 인증서를 제공하는 데 필수적인 실용적인 기반 지식을 중요시합니다.

너비 우선 탐색 알고리즘을 사용할 때의 단점은 무엇입니까?

BFS는 '블라인드' 검색이라는 단점이 있습니다. 즉, 검색 공간이 크면 다른 휴리스틱 검색에 비해 검색 성능이 떨어집니다. 이진 우선 탐색 알고리즘이 제대로 작동하려면 연결된 모든 정점을 메모리에 저장해야 합니다. 즉, 더 많은 메모리를 사용합니다. 또 다른 단점은 대상에 대한 모든 경로가 거의 동일한 검색 깊이를 가지고 있음에도 불구하고 광범위한 경로가 있다는 것입니다.

BFS 알고리즘은 DFS 알고리즘과 어떻게 다릅니까?

BFS는 특히 트리의 분기 요소가 높을 때 많은 메모리를 사용합니다. 반면에 DFS는 트리의 깊이가 크면 추가로 가까운 노드를 방문하는 데 오랜 시간이 걸릴 수 있지만 공간 복잡도는 더 낮습니다. BFS는 지정된 소스에 가까운 정점을 찾을 때 잘 작동합니다. 소스에서 사용할 수 없는 솔루션이 있는 경우 DFS를 사용하는 것이 좋습니다. 역추적은 BFS와 달리 DFS에서 필수적입니다. BFS는 트리 수준을 기반으로 탐색하지만 DFS는 트리 깊이를 기반으로 탐색합니다.

A-Star 알고리즘은 어떻게 작동합니까?

A-Star 알고리즘은 시작 상태와 끝 상태 사이의 최단 경로를 찾는 경로 찾기 방법입니다. 소스(초기 상태)와 목적지(최종 상태)(최종 상태) 사이의 최단 거리를 찾는 데 도움이 되는 맵을 포함하여 다양한 용도로 사용됩니다. Dijkstra 방법과 마찬가지로 A-Star 탐색 알고리즘은 시작 노드에서 목표 노드까지 가장 저렴한 경로 트리를 생성합니다.