알고리즘
[알고리즘] BFS(Breadth-First Search)
1. BFS란? BFS란 루트 노드(Node)에서 시작하여 인접한 노드를 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 이때 한 번 방문한 정점은 다시 방문하지 않는다. 노드 사이의 최단 경로를 구하고자 할 때, 혹은 임의의 경로를 찾고자 할 때 BFS를 이용한다. 2. BFS를 코드로 구현하려면? 1️⃣ 시작하는 정점을 큐에 삽입하여 방문했다는 표시를 남긴다. 2️⃣ 큐의 제일 앞에 있는 원소를 삭제한 후, 해당 원소에 연결돼 있으면서 아직 방문하지 않은 정점을 큐에 삽입한다. 3️⃣ 큐가 비어있을 때까지 2️⃣를 반복한다. 이때 모든 정점(Node)을 한 번, 모든 간선(Edge)을 두 번씩 방..
