要么改变世界,要么适应世界

广度优先搜索遍历矩阵

2020-08-24 19:12:00
134
目录

广度优先搜索策略(BFS)应用非常广泛,图遍历,二叉树遍历(实际上也属于图的特殊形式),矩阵遍历等都可以使用,在进行矩阵遍历,例如说逃离迷宫最短时间的算法都可以使用BFS进行实现,当然了使用DFS也可以,但是使用DFS的时候,会产生很多非最优解,性能方面及不上BFSBFS能够保证第一次找到可行解就是最优解。

模板代码

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++;
    }
}
历史评论
开始评论