그래프 최단거리(BFS)

위 그래프를 bfs로 탐색해 1번 정점에서 각 정점으로 가는 최단거리를 구해보자

 

2 : 3
3 : 1
4 : 1    
5 : 2
6 : 2

 

이렇게 결과가 나오면 된다

 

레벨 탐색과 배열을 이용해서 탐색하는 방법이 있다

 

배열을 이용해서 탐색하는 방법

 

dis 배열을 만들어서 1번정점에서 n번 정점으로 가는데 걸리는 횟수를 기록한다

dis[nv]는 dis[v]의 다음 정점이니, dis[nv] = dis[cv]+1로 구할 수 있다

이렇게 구한 dis 배열을 출력하면 된다

 

public void bfs(int v){
        ch[v] = 1;
        //시작하는 위치니까 거리는 0
        dis[v] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        while (!q.isEmpty()){
            int cv = q.poll();
            for(int nv : graph.get(cv)){
                if (ch[nv] == 0){
                    ch[nv] = 1;
                    q.offer(nv);
                    //dis[nv]는 dis[v]의 다음 정점이니, dis[v]+1로 구할 수 있다
                    dis[nv] = dis[cv]+1;
                }
            }
        }
    }

 

인접행렬로 그래프를 만들고 bfs 함수에서는 foreach문을 돌면서 해당 노드에서 갈수 있는, 방문하지 않은 정점이 있으면 거리 + 1 해주면서 쭉 탐색한다

 

레벨 탐색을 하는 방법

 

레벨을 bfs 함수 내부에 만들고 큐의 길이만큼 레벨 탐색을 하는 for문 안에서 방문 여부를 체크하고 방문하지 않앗으면 큐에 넣어준다

public void bfs(int v){
        ch[v] = 1;
        //레벨을 기록할 배열
        dis[v] = 0;
        int L = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        while (!q.isEmpty()){
            int len = q.size();
            for(int i = 0; i < len; i++){
                int cv = q.poll();
                dis[cv] = L;
                for(int nv : graph.get(cv)){
                    if (ch[nv] == 0){
                        ch[nv] = 1;
                        q.offer(nv);
                    }
                }
            }
            L++;
        }
    }

 

 

전체 코드

 

import java.util.*;
import java.io.*;


class Main {
    static int n, m;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch, dis;
    public void bfs(int v){
        ch[v] = 1;
        //레벨을 기록할 배열
        dis[v] = 0;
        int L = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        while (!q.isEmpty()){
            int len = q.size();
            for(int i = 0; i < len; i++){
                int cv = q.poll();
                dis[cv] = L;
                for(int nv : graph.get(cv)){
                    if (ch[nv] == 0){
                        ch[nv] = 1;
                        q.offer(nv);
                    }
                }
            }
            L++;
        }
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m= in.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++){
            graph.add(new ArrayList<Integer>());
        }

        ch = new int[n+1];
        dis = new int[n+1];

        for (int i = 0; i < m; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            graph.get(a).add(b);
        }

        T.bfs(1);

        for(int i =2; i <= n; i++){
            System.out.println(i + " : " + dis[i]);
        }

    }
}