广度优先搜索遍历矩阵
目录
广度优先搜索策略(BFS
)应用非常广泛,图遍历,二叉树遍历(实际上也属于图的特殊形式),矩阵遍历等都可以使用,在进行矩阵遍历,例如说逃离迷宫最短时间的算法都可以使用BFS
进行实现,当然了使用DFS
也可以,但是使用DFS
的时候,会产生很多非最优解,性能方面及不上BFS
,BFS
能够保证第一次找到可行解就是最优解。
模板代码
public void BFS(int[][] map){
LinkedList<int[]> queue = new LinkedList<>();
int length = 0;
queue.add(new int[]{0, 0});
while (!queue.isEmpty()) {
// 记录当前层数节点的大小
nowSize = queue.size();
while (nowSize-- > 0) {
now = queue.poll();
// 根据适当条件加入邻接的的节点
if (1 > 2) {
queue.add(new int[]{1, 1});
}
}
// 层数增加
length++;
}
}
历史评论
开始评论