BFS ?

목차

1.BFS?

2.BFS의 특징

3.작동원리 및 의사코드 구현

 

1.BFS?

BFS는 너비 우선 탐색이라고도 부르며, 코딩테스트에서 빈번하게 나오는 알고리즘이다. 가까운 노드 부터 우선적으로 탐색하며, 기본적으로 그래프 탐색에 사용된다.두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고자 할 때 주로 사용된다.
BFS는 자료구조 큐(Queue)를 사용하여 구현 할 수 있다.

2.BFS의 특징

탐색 순서

• 시작 정점에서 가까운 정점부터 탐색합니다.
• 동일한 깊이에 있는 정점들을 모두 탐색한 후, 더 깊은 단계로 진행합니다.
• 계층적 탐색: 그래프를 레벨 단위로 탐색한다고 볼 수 있습니다.

자료구조

• BFS는 큐(Queue) 자료구조를 사용합니다.
  • FIFO(First In, First Out) 원칙을 따라 먼저 큐에 들어간 정점부터 탐색합니다.
  • 방문할 노드들을 큐에 차례로 넣고, 탐색이 끝난 노드들은 큐에서 제거합니다.

최단 경로 탐색

• BFS는 가중치가 없는 그래프에서 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 데 효과적입니다.
• 첫 번째로 방문하는 경로가 최단 경로라는 점에서 DFS와 차별화됩니다.

방문 순서 보장

• BFS는 그래프의 구조에 따라 방문 순서를 정확히 보장합니다.
• 동일한 레벨의 정점들은 입력 순서에 따라 탐색됩니다.

3.작동원리 및 의사코드구현

BFS의 작동원리.

 

• 초기화:
  • 시작 정점을 큐에 삽입하고 방문 처리를 합니다.
• 반복:
  • 큐에서 정점을 하나 꺼냅니다.
  • 꺼낸 정점에 연결된 인접 정점들을 확인합니다.
    • 방문하지 않은 인접 정점은 방문 처리 후 큐에 삽입합니다.
• 종료:
  • 큐가 비면 탐색을 종료합니다.

import java.util.*;

public class BFSExample {
    // 그래프를 표현하는 인접 리스트
    private Map<Integer, List<Integer>> graph;

    public BFSExample() {
        this.graph = new HashMap<>();
    }

    // 그래프에 간선 추가
    public void addEdge(int from, int to) {
        graph.putIfAbsent(from, new ArrayList<>());
        graph.get(from).add(to);
    }

    // BFS 구현
    public void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>(); // BFS를 위한 큐
        Set<Integer> visited = new HashSet<>();   // 방문한 노드를 저장

        queue.offer(start);   // 시작 노드를 큐에 삽입
        visited.add(start);   // 시작 노드를 방문 처리

        while (!queue.isEmpty()) {
            int current = queue.poll();          // 큐에서 노드 꺼내기
            System.out.println("Visited: " + current); // 현재 노드 처리

            // 현재 노드의 모든 인접 노드 탐색
            List<Integer> neighbors = graph.getOrDefault(current, new ArrayList<>());
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {   // 방문하지 않은 노드만 처리
                    visited.add(neighbor);           // 방문 처리
                    queue.offer(neighbor);           // 큐에 추가
                }
            }
        }
    }

    // 메인 메서드
    public static void main(String[] args) {
        BFSExample bfsExample = new BFSExample();

        // 그래프 정의
        bfsExample.addEdge(1, 2);
        bfsExample.addEdge(1, 3);
        bfsExample.addEdge(2, 4);
        bfsExample.addEdge(2, 5);
        bfsExample.addEdge(3, 6);
        bfsExample.addEdge(4, 7);

        // BFS 실행
        System.out.println("BFS 탐색 결과:");
        bfsExample.bfs(1); // 시작 정점: 1
    }
}

 

참고

https://velog.io/@ygy0102/Java-BFS-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-%EA%B5%AC%ED%98%84-%EC%9E%90%EB%B0%94-Java#bfs