介绍
遍历图时，用两种方法：BFS和DFS
BFS
广度优先搜索，基于队列的搜索方式，在访问节点的孙子节点之前，要求先访问它所有的子节点。
伪代码
void search(Node root){
Queue<Node> q = new LinkedList<Node>();
n.visited=true;
visit(root);
q.offer(root);//入队尾
while(q.isEmpty()){
Node r = q.poll();//取队头
for(Node n : r.adjacent()){
if(n.visited==false){
visit(n);
visitedMap.put(n,true);
q.offer(n);
}
}
}
}
DFS
深度优先搜索，基于递归的搜索方式，一条路径走到底，撞了南墙才回头。
伪代码
void search(Node root){
if(root==null) return;
visit(root);
for(Node n : r.adjacent()){
if(n.visited==false){
search(n);
}
}
}
对比
-
BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。（二叉树的层次遍历，Dijkstra单元最短路径算法）
-
DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高。（求二叉树的所有路径）
-
坐标类型搜索,联想到用DFS、BFS求解。