[알고리즘 개념] BFS(너비 우선 탐색)

BFS는 Breadth First Search의 약자로 DFS와 비슷하면서 다른 특징을 가지고 있다.DFS처럼 한 방향으로 갈 수 있는 곳 까지 탐색하지 않고, 인접한 정점들을 모두 차례로 방문한 후, 방문한 정점을 다시 시작점으로 하여 다시 인접한 정점을 차례로 방문한다. 인접한 정점을 차례로 모두 탐색해야 하므로, 선입후출 방식인 스택대신, 선입선출 형태의 큐를 활용하는 것이다. 다음과 같은 그래프가 있을 때, BFS를 이용한다면 A-B-C-D-E-F-G-H-I 순으로 정점을 방문한다.아래는 BFS의 로직을 나타낸다.위 로직을 바탕으로 BFS 실행 과정을 따라가보자.1. 초기화visited 리스트를 초기화하고 방문할 정점을 담을 queue를 생성한뒤 시작점을 q..........

[알고리즘 개념] BFS(너비 우선 탐색)에 대한 요약내용입니다.

자세한 내용은 아래에 원문링크를 확인해주시기 바랍니다.

원문링크 : [알고리즘 개념] BFS(너비 우선 탐색)