首页 > Java > java教程 > 正文

广度优先搜索 (BFS)

WBOY
发布: 2024-08-10 15:33:42
转载
637人浏览过

图的广度优先搜索会逐级访问顶点。第一层由起始顶点组成。每个下一个级别都由与前一个级别中的顶点相邻的顶点组成。图的广度优先遍历类似于树遍历中讨论的树的广度优先遍历。通过广度优先遍历树,逐级访问节点。首先访问根,然后访问根的所有子代,然后访问根的孙子,依此类推。类似地,图的广度优先搜索首先访问一个顶点,然后访问它的所有相邻顶点,然后访问与这些顶点相邻的所有顶点,依此类推。为了确保每个顶点仅被访问一次,如果已经访问过该顶点,则会跳过该顶点。

广度优先搜索算法

下面的代码描述了从图中的顶点 v 开始广度优先搜索的算法。

输入:g = (v, e) 和起始顶点 v
输出:一棵以 v 为根的 bfs 树 1 棵树 bfs(顶点 v){
2 创建一个空队列,用于存储要访问的顶点;
3 将v添加到队列中;
4 马克 v 访问过;
5
6 while (队列不为空) {
7 将一个顶点(例如 u)从队列中出队;
8 将u添加到遍历顶点列表中;
u 的每个邻居 w 为 9 个
10 如果 w 尚未被访问过 {
11 将w添加到队列中;
12 将 u 设置为树中 w 的父级;
13 马克访问过;
14}
15}
16}

考虑下图 (a) 中的图表。假设从顶点 0 开始广度优先搜索。首先访问 0,然后访问其所有邻居 1、2 和 3,如下图 (b) 所示。顶点 1 有三个邻居:0、2 和 4。由于 0 和 2 已经被访问过,所以您现在将只访问 4,如下图 (c) 所示。顶点 2 有 3 个邻居:0、1 和 3,它们都已被访问过。顶点 3 有 3 个邻居:0、2 和 4,它们都已被访问过。顶点 4 有两个邻居:1 和 3,它们都已被访问过。至此,搜索结束。

广度优先搜索 (BFS)

由于每条边和每个顶点仅被访问一次,因此

bfs方法的时间复杂度为o(|e| + |v|),其中|e|表示边数,|v | 顶点数量。

广度优先搜索的实现

bfs(int v) 方法在 graph 接口中定义,并在 abstractgraph.java 类中实现(第 197-222 行)。它返回以顶点 v 作为根的 tree 类的实例。该方法将搜索到的顶点存储在列表searchorder(第198行)中,将每个顶点的父节点存储在数组parent(第199行)中,使用链表作为队列(第203-204行),并使用isvisited 数组,指示顶点是否已被访问(第 207 行)。搜索从顶点v开始。 v 在第 206 行被添加到队列中,并被标记为已访问(第 207 行)。该方法现在检查队列中的每个顶点u(第210行)并将其添加到searchorder(第211行)。该方法将u的每个未访问的邻居e.v添加到队列(第214行),将其父级设置为u(第215行),并将其标记为已访问(第216行)。

广度优先搜索 (BFS)

下面的代码给出了一个测试程序,显示从芝加哥开始的上图图表的 bfs。


public class TestBFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree bfs = graph.bfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = bfs.getSearchOrder();
        System.out.println(bfs.getNumberOfVerticesFound() + " vertices are searched in this BFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(bfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(bfs.getParent(i)));
    }

}

登录后复制

按以下顺序搜索 12 个顶点:

芝加哥 西雅图 丹佛 堪萨斯城 波士顿 纽约
旧金山 洛杉矶 亚特兰大 达拉斯 迈阿密 休斯顿
西雅图的父母是芝加哥
旧金山的父母是西雅图
洛杉矶的父母是丹佛
丹佛的父母是芝加哥
堪萨斯城的母校是芝加哥
波士顿的父母是芝加哥
纽约的父母是芝加哥
亚特兰大的父母是堪萨斯城
迈阿密的父母是亚特兰大
达拉斯的父母是堪萨斯城
休斯顿的父母是亚特兰大

bfs 的应用

dfs 解决的很多问题也可以用 bfs 解决。具体来说,bfs可以用来解决以下问题:

    检测图是否连通。如果图中任意两个顶点之间存在路径,则该图是连通的。
  • 检测两个顶点之间是否存在路径。
  • 寻找两个顶点之间的最短路径。可以证明bfs树中根到任意节点的路径都是根到节点的最短路径。
  • 找到所有连接的组件。连通分量是最大连通子图,其中每对顶点都通过路径连接。
  • 检测图中是否存在环路。
  • 在图中找到一个循环。
  • 测试图是否是二分图。 (如果图的顶点可以分为两个不相交的集合,使得同一集合中的顶点之间不存在边,则该图是二分图。)

广度优先搜索 (BFS)

以上就是广度优先搜索 (BFS)的详细内容,更多请关注php中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
相关标签:
来源:dev.to网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号