BFS란?
너비 우선 검색, 너비 우선 검색
가장 가까운 노드를 찾는 알고리즘
행동 과정
하나. 검색의 시작 노드를 대기열에 추가하다 방문처리하다
2. 노드 대기열에서 빼기 이 노드 이웃 노드 사이 방문하지 않은 모든 노드를 대기열에 추가 방문처리하다
3. 2단계 더 이상 할 수 없을 때까지 반복하다.
* 방문처리: 한 번 대기하고 처리된 노드가 다시 삽입되지 않는지 확인하는 것을 의미합니다. 방문 처리를 통해 각 노드를 한 번만 처리할 수 있습니다.
자세히 살펴보기
이웃 노드 중 방문하지 않은 노드가 여러 개인 경우 번호가 낮은 순서처리하다
* 방문한 노드~이다 회색대기열에서 꺼내십시오. 노드 처리 중~이다 하늘색로 표현
하나. 시작 노드 ‘1’대기열에 추가되고 방문한 것으로 처리됩니다.
2. 대기 중 노드 ‘1’ 아웃소싱 및 무인 이웃 노드 ‘2’. ‘3’, ‘8’ 모두 대기 및 방문 편집하다
3. 대기 중 노드 ‘2’방문하지 않은 이웃 노드 ‘7’두번째 대기열에 추가 및 방문 편집하다
4. 대기 중 노드 ‘3’이사하고 한번도 방문하지 않은 이웃 노드 ‘4’ 및 ‘5’모든 목록에 추가해하다 방문처리하다
5. 대기 중 노드 ‘8’이사하고 한번도 방문하지 않은 인접 노드가 없으므로 무시하다.
6. 대기 중 노드 ‘7’이사하고 한번도 방문하지 않은 이웃 노드 ‘6’두번째 목록에 추가해하다 방문처리하다
7. 방문하지 않은 나머지 노드 인접 노드 없음.
따라서 모든 노드를 순서대로 제거하면 다음과 같이 됩니다.
노드 검색 순서
1-2-3-8-7-4-5-6
특성
하나. 대기열 데이터 구조기반 -> 구현이 간단합니다.
2. 대기열 클래스사용하기 좋습니다
삼. 데이터 개수가 N일 때 O(N)의 시간 복잡도가지다
4. 일반적인 경우 실제 실행 시간은 DFS보다 짧습니다.
구현 코드
public class BFS {
public static boolean() visited = new boolean(9);
public static ArrayList<ArrayList<Integer>> graph;
// BFS 함수 정의
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
// 현재 노드 방문 처리
visited(start) = true;
while (!q.isEmpty()) {
// 큐의 맨 앞 원소를 꺼낸 후 출력
int x = q.poll();
System.out.print(x + " ");
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 모두 큐에 삽입
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited(y)) {
q.offer(y);
visited(y) = true;
}
}
}
}
public static void main(String() args) {
// 그래프 정의
graph = new ArrayList<>() {{
add(new ArrayList<>(List.of()));
add(new ArrayList<>(List.of(2, 3, 8)));
add(new ArrayList<>(List.of(1, 7)));
add(new ArrayList<>(List.of(1, 4, 5)));
add(new ArrayList<>(List.of(3, 5)));
add(new ArrayList<>(List.of(3, 4)));
add(new ArrayList<>(List.of(7)));
add(new ArrayList<>(List.of(2, 6, 8)));
add(new ArrayList<>(List.of(1, 7)));
}};
// 정의된 BFS 함수 호출
bfs(1);
}
출력 결과
1 2 3 8 7 4 5 6
참조
코딩테스트입니다 – 나동빈