广度优先搜索 (BFS)

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

广度优先搜索算法

下面的代码描述了图中顶点的代码 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 开始广度优先搜索。首先访问 然后访问所有邻居 1、2 和 3，如下图 (b) 所示。顶点 1 有三个邻居：0、2 和 4。由于 0 和 2 你已经被访问过了，所以你现在只会访问 4，如下图 (c) 所示。顶点 2 有 3 个邻居：0、1 和 三、他们都被访问过。顶点 3 有 3 个邻居：0、2 和 四、他们都被访问过。顶点 4 有两个邻居：1 和 三、他们都被访问过。此时，搜索已经结束。

因为每个边缘和顶点只被访问一次，所以

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。

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 



按以下顺序搜索 12 个顶点：<p>
 芝加哥 西雅图 丹佛 堪萨斯城 波士顿 纽约<br>
 旧金山 洛杉矶 亚特兰大 达拉斯 迈阿密 休斯顿<br>
芝加哥的父母是芝加哥<br>
西雅图是旧金山的父母<br>
丹佛是洛杉矶的父母<br>
芝加哥是丹佛的父母<br>
芝加哥是堪萨斯城的母校<br>
芝加哥是波士顿的父母<br>
芝加哥是纽约的父母<br>
堪萨斯城是亚特兰大的父母<br>
亚特兰大是迈阿密的父母<br>
达拉斯的父母是堪萨斯城<br>
休斯顿的父母是亚特兰大<br></p>
  
  
  bfs 的应用
<h2>

</h2>dfs 许多问题也可以用来解决 bfs 解决。具体来说，bfs可以用来解决以下问题：<p>

</p>
<ul>检测图是否连接。具体来说，bfs可以用来解决以下问题：<p>

</p>
<ul>检查图纸是否连接。若图中任意两个顶点之间有路径，则图纸是连接的。<li>
</li>检查两个顶点之间是否有路径。<li>
</li>在两个顶点之间找到最短的路径。bfs树根到任何节点的路径都可以证明是根到节点的最短路径。<li>
</li>找到所有连接的组件。连接分量是最大的连接子图，每对顶点都通过路径连接。<li>
</li>检测图中是否存在环路。<li>
</li>在图中找到一个循环。<li>
</li>测试图是否为二分图。 (如果图的顶点可以分为两个不相交的集合，使得同一集中的顶点之间没有边缘，则图为二分图。）<li>
</li>

</ul>
<p><img src="https://img.php.cn/upload/article/000/887/227/172327522735818.png" alt="优先搜索广度 (BFS)"></p>

            
        </integer></string></string>

以上是广度优先搜索 (BFS)详情请关注图灵教育的其他相关文章！