BFS算法

基本框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int BFS(Node start, Node target){
    Queue<Node> q;
    Set<Node> visited;
    
    q.offer(start);
    visited.add(start);
    int step = 0;
    while(!q.isEmpty()){
        int sz = q.size();
        for(int i = 0;i < sz;i++){
            Node cur = q.poll();
            if(cur == target){
                return step;
            }
            for(Node x : cur.adj()){
                if(!visited.containsKey(x)){
                    q.offer(x);
                    visited.add(x);
                }
            }
            
        }
    }
}