ETC./Algorithm
2020.10.09
2
[Algorithm] BFS 알고리즘 (Breadth-First Search)
너비 우선탐색 (BFS)란? BFS는 그래프 전체를 탐색하는 방법 중 하나로써 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회함으로써 노드를 넓게(wide) 탐색합니다. 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다. 주로 구현은 큐라는 자료에 이웃하는 정점을 다 담아놓고 차례대로 POP을 하는 방식으로 구현합니다. [Algorithm] 자료구조 그래프(Graph)란 무엇인가? BFS의 장점 1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다. 2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름 3.너비를 우선 탐..
