감자튀김 공장🍟

그래프의 탐색 그래프 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. Ex) 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 연결되어 있지 않은지 너비 우선 탐색(BFS: Breath First Search) 너비 우선 탐색이란? 너비 우선 탐색(BFS)은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 기법이다. 이러한 그래프가 있을 경우 BFS로 어떤 순서가 나오는지 확인해보자. 그래프의 시작 정점인 1에서 시작하여 v(1)을 방문한 후 v(1)에 인접한 정점 v(2)와 v(3)을 방문한 후 v(1)에 더 이상 인접한 간선이 없으므로 해당 단계는 종료된다. 다음에 정점 v(2)와 v(3)..