[그래프] 너비 우선 탐색 BFS

BFS (너비 우선 탐색)특징

• 계층적 탐색: BFS는 시작 노드에서 가까운 노드부터 탐색을 시작하여 점차 거리가 먼 노드들을 탐색합니다. 노드를 "너비"를 기준으로 탐색합니다.
• 큐(Queue) 사용: BFS는 큐를 이용하여 노드를 저장하고 순차적으로 처리합니다. 큐는 FIFO(First In, First Out) 방식으로, 먼저 삽입된 노드를 먼저 처리합니다.
• 최단 경로 보장: 무가중치 그래프에서는 BFS가 시작 노드로부터 모든 다른 노드까지의 최단 경로를 보장합니다.
• 방문 여부 체크: BFS는 동일 노드를 여러 번 방문하지 않도록 방문 여부를 체크합니다. 이를 위해 방문 여부를 기록하는 배열이나 집합(Set)을 사용합니다.

장단점

• 장점:
  • 최단 경로 탐색에 유용합니다.
  • 모든 노드를 확실히 탐색할 수 있습니다.
• 단점:
  • 큐와 방문 목록을 관리해야 하므로, 노드 수가 많을 경우 공간 복잡도가 증가할 수 있습니다.

시간 및 공간 복잡도

• 시간 복잡도: O(V+E)O(V + E)O(V+E), 여기서 VVV는 정점의 수, EEE는 간선의 수입니다. 각 노드를 한 번씩 방문하고, 각 간선을 한 번씩 처리하기 때문입니다.
• 공간 복잡도: O(V)O(V)O(V), 큐와 방문 여부를 기록하는 데 필요한 공간 때문입니다.

• BFS는 그래프나 트리에서 노드를 탐색하는 알고리즘으로, 시작 노드에서부터 가까운 노드부터 차례대로 탐색합니다. 현재 노드의 인접 노드를 먼저 탐색한 후, 그 다음 단계에서 인접 노드의 이웃들을 탐색하는 방식으로 진행됩니다.

의사 코드 + Java 코드

BFS(graph, startNode):
    1. 큐(Queue) 생성
    2. 방문 여부를 기록할 리스트 또는 배열 생성
    3. 시작 노드를 큐에 추가하고 방문 처리
    4. 큐가 빌 때까지 다음을 반복:
        a. 큐에서 노드를 하나 꺼냄
        b. 해당 노드의 모든 인접 노드를 확인
        c. 방문하지 않은 인접 노드를 큐에 추가하고 방문 처리

// BFS 구현
public void bfs(int startNode) {
    // 방문한 노드를 기록하기 위한 집합
    Set<Integer> visited = new HashSet<>();

    // BFS에 사용할 큐
    Queue<Integer> queue = new LinkedList<>();

    // 시작 노드를 큐에 넣고 방문 표시
    queue.add(startNode);
    visited.add(startNode);

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

        // 현재 노드의 이웃들을 확인
        List<Integer> neighbors = graph.getOrDefault(currentNode, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                queue.add(neighbor);
                visited.add(neighbor);
            }
        }
    }
}

 

• BFS의 활용 예시
  • 최단 경로 탐색: 미로 찾기, 네트워크에서 최소 홉 수 찾기 등 무가중치 그래프에서 최단 경로를 찾는 데 유용합니다.
  • 그래프 연결성 검사: 그래프가 모든 노드와 연결되어 있는지 확인하는 데 사용됩니다.
  • 레벨 순회: 트리에서 특정 레벨에 있는 모든 노드를 탐색할 때 사용됩니다.