宽度优先搜索遍历图

AcWing 847. 图中点的层次

【题目描述】

AcWing 847. 图中点的层次

【思路】
用BFS对 图进行遍历

import java.util.*;
public class Main{
    static int N = 100010, M = 100010;
    static int h[] = new int[N];
    static int d[] = new int[N];   //记录1号点到当前点的距离
    static int e[] = new int[M];
    static int ne[] = new int[M];
    static int idx, n, m;

    static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public static int bfs(){
        Queue<Integer> q = new LinkedList<Integer>();
        Arrays.fill(d, - 1);
        q.offer(1); //1号点入队
        d[1] = 0; //1号点到1号点的距离是1

        while(! q.isEmpty()){
            int t = q.poll();

            //扩展t的邻边
            for(int i = h[t]; i != - 1; i = ne[i]){
                int j = e[i];

                if( d[j] == -1){//没有被访问过
                    d[j] = d[t] + 1;//d[j]存储j号点离起点的距离，并标记为访问过
                    q.offer(j);
                }
            }
        }

        return d[n];
    }

    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        n = reader.nextInt();
        m = reader.nextInt();
        Arrays.fill(h, - 1);
        for(int i = 0; i < m; i ++)
        {
            int a = reader.nextInt(), b = reader.nextInt();
            add(a, b);
        }
        System.out.println( bfs() );
    }
}