그래프최단거리

코드

//각 정점으로 가는 최소 이동 간선수
class 그래프최단거리BFS {
    static int n, m, answer=0;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    static int[] ch, dis;
    
    public void BFS2(int v){
        LinkedList<Integer> q = new LinkedList<Integer>();
        ch[v] = 1;
        dis[v] = 0;
        
        q.offer(v);
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            
            for(Integer next : graph.get(cur)) {
                if(ch[next] == 0) {
                    ch[next] = 1;
                    dis[next] = dis[cur]+1;
                    q.add(next);
                }
            }
        }
    }

    
    public static void main(String[] args){
        그래프최단거리BFS T = new 그래프최단거리BFS();
        n=6;//최대 노드
        ch=new int[n+1];
        dis=new int[n+1];
        int[] aArr= {1,1,2,2,3,4,4,6,6};
        int[] bArr= {3,4,1,5,4,5,6,2,5};
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0; i<bArr.length; i++){
            int a= aArr[i];
            int b= bArr[i];
            graph.get(a).add(b);
        }
        T.BFS2(1);
        for(int i=1; i<=n; i++){
            System.out.println(i+" : "+dis[i]);
        }
        System.out.println(Arrays.toString(dis));
    }   
}

---

결과

1 : 0
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2
[0, 0, 3, 1, 1, 2, 2]

---

시작 정점에서 각 정점으로 가는 최소 횟수

 

간선 시각화

ch체크를 적용한 상태 트리, 각 레벨 별 횡단은 Q에 저장된 노드다.

브레이크 포인트를 지정하고 디버깅 해보면, 확실히 알 수 있다.

2 지점 큐 상태