목록그래프탐색 (1)

나 JAVA 봐라

BFS 너비 우선 탐색

BFS (Breadth Fisrt Search) 너비 우선 탐색 이라고 부른다. 가까운 노드부터 우선적으로 탐색하기 때문에 넓게 탐색해서 너비 우선 탐색이다. Queue 자료구조를 사용하여 구현할 수 있다. 탐색 방식 루트 노드 (혹은 다른 임의의 노드) 에서 시작하여 인접한 노드를 먼저 탐색한다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. ex) 미로 탐색 (최단 거리) 특징 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다. (거리 1 탐색 후, 2,3,4 순서로 탐색) 그래프 탐색의 경우, 어떤 노드를 방문했었는지의 여부를 반드시 검사해야한다. 그래서 노드를 큐에 담을 때에는 꼭 방문처리를 한 후에 담는다. 방문 여부를 체크하지 않으면 무..
CS/자료구조 2024. 1. 21. 18:32
이전 Prev 1 Next 다음