너비우선탐색 (1) 썸네일형 리스트형 BFS(Breadth Firsh Search) 그래프를 탐색하는 방법은 2가지가 있음 - 깊이 우선 탐색(DFS) - 너비 우선 탐색(BFS) BFS - 탐색 시작점의 인접한 정점부터 먼저 다 방문한 후, 그 방문한 정점을 시작으로 다시 인접한 정점들을 차례로 방문하는 방식 - 인접한 정점에 대해 탐색 후 다시 BFS를 진행하므로, FIFO인 큐를 활용함 BFS 예제 1. 초기 상태 visited 배열 초기화 Q 생성 시작점을 enqueue 2. A점부터 시작(root=1) dequeue : A A visited A의 인접점들을 enqueue 3. 탐색 진행(A의 인접점인 B,C,D를 순차적으로)(root=2) dequeue : B , B visited , B의 인접점들을 enqueue dequeue : C , C visited , C의 인접점들을 .. 이전 1 다음
