江津区网站建设,深圳制作网站流程,google play下载安卓,老版本hao123上网导航广度优先算法(BFS 算法)
广度优先算法#xff08;BFS#xff09;是一种图遍历算法#xff0c;用于在一个图中从给定的起始节点开始#xff0c;按照广度优先的顺序遍历图中的所有节点。它通过逐层遍历图中的节点#xff0c;先访问离起始节点最近的节点#xff0c;然后再依…广度优先算法(BFS 算法)
广度优先算法BFS是一种图遍历算法用于在一个图中从给定的起始节点开始按照广度优先的顺序遍历图中的所有节点。它通过逐层遍历图中的节点先访问离起始节点最近的节点然后再依次访问离起始节点更远的节点。
BFS的基本思想是使用队列来存储待访问的节点。首先将起始节点加入队列然后从队列中取出一个节点进行访问并将其未访问过的邻居节点加入队列。重复这个过程直到队列为空即所有节点都被访问过。
BFS算法的步骤如下
创建一个空队列将起始节点加入队列。创建一个空集合用于存储已访问过的节点。当队列不为空时执行以下操作 从队列中取出一个节点并将其标记为已访问。访问该节点并进行相应的操作。将该节点的未访问过的邻居节点加入队列。 重复步骤3直到队列为空。
BFS算法的时间复杂度为O(VE)其中V为节点数E为边数。由于需要遍历图中的所有节点和边因此时间复杂度与图的规模成正比。
BFS算法常用于解决以下问题
图的遍历可以用BFS算法遍历图中的所有节点。最短路径在无权图中BFS算法可以用于找到两个节点之间的最短路径。连通性问题可以用BFS算法判断图中两个节点是否连通或者找到图中的连通分量。
总之广度优先算法是一种简单而有效的图遍历算法可以用于解决多种问题。在实际应用中我们可以根据具体问题的需求灵活运用BFS算法来解决各种图相关的问题。
其实 BFS 算法就是回溯算法通常采用队列进行操作。
问题描述1
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
实现代码1
/*** 树的最小深度** param treeNode 树根节点* return 最小深度*/public static int minDepth(TreeNode treeNode) {QueueTreeNode treeNodeQueue new LinkedList();treeNodeQueue.offer(treeNode);int step 1;while (!treeNodeQueue.isEmpty()) {int size treeNodeQueue.size();for (int i 0; i size; i) {TreeNode curr treeNodeQueue.poll();if (curr.left null curr.right null) {return step;}if (curr.left ! null) {treeNodeQueue.add(curr.left);}if (curr.right ! null) {treeNodeQueue.add(curr.right);}}step;}return 0;}问题描述2
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字 ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转例如把 ‘9’ 变为 ‘0’‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ 一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字一旦拨轮的数字和列表里的任何一个元素相同这个锁将会被永久锁定无法再被旋转。
字符串 target 代表可以解锁的数字你需要给出解锁需要的最小旋转次数如果无论如何不能解锁返回 -1 。
实现代码1
/*** 打开锁最小次数** param deadends 黑名单* param target 目标数字* return 最小次数*/public static int openLock(String[] deadends, String target) {QueueString queue new LinkedList();SetString visited new HashSet();SetString deadendSet new HashSet();for (String s : deadends) {deadendSet.add(s);}queue.offer(0000);visited.add(0000);int step 0;while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) {String curr queue.poll();if (deadendSet.contains(curr)) {continue;}if (target.equals(curr)) {return step;}for (int j 0; j 4; j) {queue.offer(up(curr, j));queue.offer(down(curr, j));}}step;}return -1;}/*** curr第j位向上加** param curr 当前数字* param j 位数从0开始* return 调整后数字*/private static String up(String curr, int j) {char[] arr curr.toCharArray();if (arr[j] 9) {arr[j] 0;} else {arr[j] (char) (arr[j] 1);}return new String(arr);}/*** curr第j位向上减** param curr 当前数字* param j 位数从0开始* return 调整后数字*/private static String down(String curr, int j) {char[] arr curr.toCharArray();if (arr[j] 0) {arr[j] 9;} else {arr[j] (char) (arr[j] - 1);}return new String(arr);}
