[그래프]넓이 우선 탐색(BFS)

넓이 우선 탐색이란?

그래프 G와 시작점 S가 주어졌을 때 S에서 도달 가능한 모든 간선을 찾는 과정

동작 원리

먼저 거리가 1인 정점을 모든 찾은 후 2인 정점을 찾는 식으로 거리를 늘려가며 탐색

탐색을 하면서 시작점으로부터의 거리와 바로 직전 정점을 계산

직전정점 그래프(넓이 우선 탐색 트리)

시작점으로부터 각 정점에 들려야 하는 정점으로 만든 하위 그래프로 트리 형태

모든 정점이 연결되어 있고 nE(간선의 수) = nV(vertex의 수) - 1

예시)

주어진 그래프

1을 시작점으로한 넓이 우선 탐색 트리

코드 구현

public class BfsExample {
    
    /*
     * 인접리스트로 구현된 그래프의 넓이우선 탐색
     */
    
    static int nV; //총 vertex 개수
    static int nE; //총 edge 개수
    static ArrayList<ArrayList<Integer>> adList = new <ArrayList<Integer>> ArrayList();
    //그래프 구현을 위한 인접리스트
 
    static int[] visit; //방문여부와 완료여부를 표시
    // 0 - 방문 안함,   1 - 방문했지만 아직 탐색 안됨 , 2 - 탐색완료
    static int[][] vertexInfo; //vertex의 위치 정보를 담는 2차원 배열
                               //i번쨰 vertex의 정보 - vertexInfo[i][0] = distance
                               //                   vertexInfo[i][1] = preVertex(상위 vertex)
    
    public static void bfs(int i) {
        visit = new int[nV];
        vertexInfo = new int[nV][2];
        Queue<Integer> q = new LinkedList();
 
        q.offer(i); //탐색 시작 위치의 vertex를 큐에 넣는다.
        visit[i] = 1;
        vertexInfo[0][i] = 0;
        while(!q.isEmpty()) { //Queue의 모든 작업이 없을때 까지
            int temp = q.poll(); //Queue에서 작업(탐색을 위한 데이터)을 가져온다.
            int tempDistance = vertexInfo[temp][0]; 
            for(int j:adList.get(temp)) { //인접리스트에서 temp번째 vertex가 가지고 있는 간선 수만큼 반복
                if(visit[j]==0) { //vertex에 한번도 방문 안했을떄
                    visit[j] = 1; //방문 체크를 한다.
                    vertexInfo[j][0] = tempDistance + 1;
                    vertexInfo[j][1] = temp; //상위 vertex 정보를 넣는다.
                    System.out.println(temp + "에서 " + j + "로 이동");
                    q.offer(j); //새로 찾은 vertex를 탐색하기 위해 Queue에 삽입
                }
            }
            visit[temp] = 2; //탐색 완료된 vertex 플래그
        }    
    }
 
    public static void main(String[] args) {
        
        //인접리스트를 이용한 그래프 구현
        Scanner scan = new Scanner(System.in);
 
        nV = scan.nextInt();
        nE = scan.nextInt();
 
 
        for(int i=0;i<nV;i++) adList.add(new<Integer> ArrayList());
        //adList에 담을 리스트(각 vertex마다 인접한 vertext를 표현한 리스트)
 
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
 
            adList.get(vertex1).add(vertex2);
            adList.get(vertex2).add(vertex1);
        }
        
        //넓이우선 탐색시작
        bfs(1);
        
        int i = 0;
        for(int[] vertex:vertexInfo) {
            System.out.print(i++ + "-");
            System.out.print("distance" + vertex[0] + ", ");
            System.out.println("preVertex" + vertex[1]);
        }
    }
}