넓이 우선 탐색

넓이 우선 탐색 (BFS : Breadth Frist Search) - JAVA

깊이 우선 탐색(DFS : Depth First Search) 너비 우선 탐색은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 입니다. FIFO(First In First Out) 방식으로 큐를 이용하여 구현하며 탐색 시작 노드와 가까운 노드를 우선하여 탐색하기 때문에 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다. 장단점 장점 시작 노드부터 목표 노드 까지의 최단 경로를 보장 단점 큐를 이용해 다음에 탐색 할 노드를 저장하기 때문에 노드의 수가 많을 수로 많은 저장 공간을 필요로함 노드의 수가 늘어나면 탐색해야 하는 노드가 많아지기 때문에 비효율적 구현 방법 BFS를 사용하기 위해서는 먼저 그래프를..