[Java] 그래프 최단거리 (BFS)

 

 

 

그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요

 

 

 

 

import java.util.*

class Main {
	static int n, m;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch, dis;
    
    public void BFS(int v) {
    	Queue<Integer> q = new LinkedList<>();
        ch[v] = 1;
        dis[v] = 0;
        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] + 1;
                }
            }
        }
    
    }
    
    public static void main(String[] args) {
    	Main T = new Main();
        Scanner in = new Scanner();
        int n = in.nextInt();
        int m = in.nextInt();
        
        for(int i=0; i<=n; i++) {
        	graph.add(new ArrayList<Integer>());
        }
        
        ch = int[n+1];
        dis = int[n+1];
        
        for(int i=0; i<m; i++) {
        	int a = nextInt();
            int b = nextInt();
            graph.get(a).add(b);
        }
        
        T.BFS(1);
        for(int i=2; i<=n; i++) {
        	System.out.println(i + " : " + dis[i]);
        }
    }
}

 

 

 

출력값

2 : 3

3 : 1

4 : 1

5 : 2

6 : 2