기록공간

너비 우선 탐색 (Breadth Firest Search : BFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 모든 간선을 우선적으로 검사하며, 그 중 방문하지 않은 정점을 찾아 순차적으로 방문해 나아간다. 더이상 방문할 수 없을때 까지 반복하며, 인접한 간선을 우선적으로 검사하기 위하여 Queue를 사용한다. 어떻게 진행되는지를 그림을 통해 살펴보자. 1을 방문하면서 인접한 정점인 2, 3, 그리고 7을 큐에 넣어준다. 그리고 큐에 들어간 순서대로 방문하면서 큐가 빌때까지 반복 수행해준다. 이 작업을 모든 정점이 방문되었을때까지 반복해주면 된다. 구현 위 그래프 정보를 바탕으로 깊이 탐색을 구현해보자. #include #include #includ..