# 广度优先搜索(BFS)小结

```public class GraphNode{
int val;
List<GraphNode> neighbors;
}
```

## BFS for trees/graphs

```public void BFS(GraphNode start){
HasheSet<GraphNode> visited = new HasheSet<GraphNode>();
q.push(start);
while(!q.empty()){
GraphNode cur = q.poll();
System.out.println(cur.val);
for(GraphNode next: cur.children){
if(!visited.contains(next)){
q.push(next);
}
}
}//while
}
```

## BFS with distance

```//...
distq.push(0);// distance from start to start
//...
// in the while(!q.empty()) loop:
int d = distq.poll();//get distance from start to current node
for(GraphNode next: node.children){
distq.push(d+1);// distance from start to next node
//...
```

## BFS "by layer"

```public void BFS(GraphNode start){
ArrayList<GraphNode> q = new ArrayList<Tree>();
HasheSet<GraphNode> visited = new HasheSet<GraphNode>();
q.push(start);
while(!q.empty()){
ArrayList<GraphNode> newq = new ArrayList<Tree>();// create a new queue
for(GraphNode cur: q){// deal with all nodes in the queue
System.out.print(cur.val+", ");// all nodes in q are of the same distance/depth
for(GraphNode next: cur.children)
if(!visited.contains(next))
}
System.out.println();
q = newq;//replace q with newq
}//while
}
```