너비 우선 탐색(BFS)

Breadeth-first search

• 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘
• 거리 : 시작 노드와 목표 노드까지의 차수(간선 가중치의 합 X)
• 먼저 발견한 노드를 방문하는 것 -> Queue 사용

1. 시작 노드를 정하고, 큐에 시작 노드를 add + 방문 처리 -> 큐에 있는 노드는 이미 방문 처리했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태
2. 큐가 비었는지 확인(큐가 비었다면 방문할 수 있는 모든 노드를 방문했다는 의미 -> 탐색 종료)
3. 큐에서 노드를 poll
4. poll한 노드와 인접한 모든 노드를 확인하고 아직 방문하지 않은 노드를 큐에 add + 방문 처리

고려할 점

1. 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 함
2. 이미 방문한 노드인지 확인할 수 있어야 함

=> 찾은 노드가 시작 노드로부터 최단 경로임을 보장

너비 우선 탐색의 사용

시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문에 찾은 노드가 시작 노드로부터 최단 경로임을 보장하는 특성이 있음

• 문제에 대한 답이 많은 경우 가장 가까운 답을 찾을 때 유용
• 미로 찾기 문제에서의 최단 경로 탐색
• 네트워크 분석 문제

package graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class dfs {
    private static ArrayList<Integer>[] adjList; // 인접 리스트를 저장할 배열
    private static boolean[] visited; // 방문 여부를 저장할 배열
    private static ArrayList<Integer> answer;

    public static void main(String[] args) {
        //그래프의 각 노드에 연결된 노드들을 저장하는 인접 리스트
        int V = 5; // 정점의 개수
        adjList = new ArrayList[V]; //각 노드에 대한 인접 리스트를 저장할 배열. 배열의 크기는 정점의 개수
        visited = new boolean[V];
        answer = new ArrayList<>();

        // 인접 리스트 초기화
        for (int i = 0; i < V; i++) {
            adjList[i] = new ArrayList<>();
        }

        // 간선 추가
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 2);
        addEdge(2, 0);
        addEdge(2, 3);
        addEdge(3, 3);
        addEdge(3, 4);

        // DFS 수행
        bfs(2); // 시작 노드를 2로 설정

        // 결과 출력
        System.out.println("BFS 결과 : " + answer);
    }

    private static void addEdge(int v, int w) {
        adjList[v].add(w); // v -> w 간선 추가
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true; //시작 노드를 방문처리
        queue.offer(start); //시작 노드를 큐에 추가

        while (!queue.isEmpty()) {
            int now = queue.poll(); //큐의 첫 번째 노드를 꺼내옴
            answer.add(now); //현재 노드를 결과 list에 추가

            //현재 노드와 인접한 노드 순회
            for (int i = 0; i < adjList[now].size(); i++) {
                int next = adjList[now].get(i);
                if(!visited[next]){
                    visited[next] = true; //방문 처리
                    queue.offer(next); //방문 노드를 큐에 추가
                }
            }
        }

    }
}