• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

经典算法:广度优先搜索算法(BFS)

武飞扬头像
正经程序员
帮助45

前言

广度优先搜索算法(BFS),又叫宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。广度优先搜索的实现一般采用open-closed表。

节点进行广度优先搜索的顺序图 image.png

BFS是一种暴力搜索算法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能地址,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。

从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实现里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表,而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)

实现方法

  1. 首先将根节点放入队列中。
  2. 从队列中取出第一个节点,并检验它是否为目标。
    • 如果找到目标,则结束搜索并回传结果。
    • 否则将它所有尚未检验过的直接子节点加入队列中。
  3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
  4. 重复步骤2。

BFS的迭代实现

BFS 的非递归实现类似于DFS 的非递归实现,但在两个方面有所不同:

  • 它使用队列而不是堆栈。
  • 它在推送顶点之前检查是否已发现顶点,而不是延迟此检查直到顶点出列。
import java.util.*;
 
class Edge
{
    int source, dest;
 
    public Edge(int source, int dest)
    {
        this.source = source;
        this.dest = dest;
    }
}
 
class Graph
{
    // 表示邻接列表的列表
    List<List<Integer>> adjList = null;
 
    Graph(List<Edge> edges, int n)
    {
        adjList = new ArrayList<>();
 
        for (int i = 0; i < n; i  ) {
            adjList.add(new ArrayList<>());
        }
 
        // 向无向图添加边
        for (Edge edge: edges)
        {
            int src = edge.source;
            int dest = edge.dest;
 
            adjList.get(src).add(dest);
            adjList.get(dest).add(src);
        }
    }
}
 
class Main
{
    // 从顶点 `v` 开始对图执行 BFS
    public static void BFS(Graph graph, int v, boolean[] discovered)
    {
        // 创建一个执行 BFS 的队列
        Queue<Integer> q = new ArrayDeque<>();
 
        // 源顶点标记为已发现
        discovered[v] = true;
 
        // enqueue source vertex
        q.add(v);
 
        // 遍历直到队列为空
        while (!q.isEmpty())
        {
            // 脱离前面的节点并打印
            v = q.poll();
            System.out.print(v   " ");
 
            // 每条边 (v, u) 
            for (int u: graph.adjList.get(v))
            {
                if (!discovered[u])
                {
                    // 标记为已发现并排队等候
                    discovered[u] = true;
                    q.add(u);
                }
            }
        }
    }
 
    public static void main(String[] args)
    {
        List<Edge> edges = Arrays.asList(
                new Edge(1, 2), new Edge(1, 3), new Edge(1, 4), new Edge(2, 5),
                new Edge(2, 6), new Edge(5, 9), new Edge(5, 10), new Edge(4, 7),
                new Edge(4, 8), new Edge(7, 11), new Edge(7, 12)
                // 顶点 0、13 和 14 是单个节点
        );
 
        // 图中的节点总数(标记为 0 到 14)
        int n = 15;
 
        // 从给定的边构建图
        Graph graph = new Graph(edges, n);
 
        // 来跟踪一个顶点是否被发现
        boolean[] discovered = new boolean[n];
 
        // 从所有未发现的节点进行BFS遍历
        // 覆盖图形的所有连接部分
        for (int i = 0; i < n; i  )
        {
            if (discovered[i] == false)
            {
                // 从顶点 `i` 开始 BFS 遍历
                BFS(graph, i, discovered);
            }
        }
    }
}

输出:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

BFS的递归实现

import java.util.*;
 
class Edge
{
    int source, dest;
 
    public Edge(int source, int dest)
    {
        this.source = source;
        this.dest = dest;
    }
}
 
// 图形对象类
class Graph
{
    List<List<Integer>> adjList = null;
 
    Graph(List<Edge> edges, int n)
    {
        adjList = new ArrayList<>();
 
        for (int i = 0; i < n; i  ) {
            adjList.add(new ArrayList<>());
        }
 
        // 向无向图添加边
        for (Edge edge: edges)
        {
            int src = edge.source;
            int dest = edge.dest;
 
            adjList.get(src).add(dest);
            adjList.get(dest).add(src);
        }
    }
}
 
class Main
{
    // 在图上递归执行 BFS
    public static void recursiveBFS(Graph graph, Queue<Integer> q,boolean[] discovered)
    {
        if (q.isEmpty()) {
            return;
        }
 
        // 脱离前面的节点并打印
        int v = q.poll();
        System.out.print(v   " ");
 
        // 每条边 (v, u) 
        for (int u: graph.adjList.get(v))
        {
            if (!discovered[u])
            {
                // 标记为已发现并排队等候
                discovered[u] = true;
                q.add(u);
            }
        }
 
        recursiveBFS(graph, q, discovered);
    }
 
    public static void main(String[] args)
    {
        List<Edge> edges = Arrays.asList(
                new Edge(1, 2), new Edge(1, 3), new Edge(1, 4), new Edge(2, 5),
                new Edge(2, 6), new Edge(5, 9), new Edge(5, 10), new Edge(4, 7),
                new Edge(4, 8), new Edge(7, 11), new Edge(7, 12)
                // 顶点 0、13 和 14 是单个节点
        );
 
        // 图中的节点总数(标记为 0 到 14)
        int n = 15;
 
        // 从给定的边构建图
        Graph graph = new Graph(edges, n);
 
        // 跟踪一个顶点是否被发现
        boolean[] discovered = new boolean[n];
 
        // 创建一个BFS队列
        Queue<Integer> q = new ArrayDeque<>();
 
        // 从所有未发现的节点执行 BFS 遍历到
        // 覆盖图的所有连通分量
        for (int i = 0; i < n; i  )
        {
            if (discovered[i] == false)
            {
                // 将源顶点标记为已发现
                discovered[i] = true;
 
                q.add(i);
 
                // 从顶点 `i` 开始 BFS 遍历
                recursiveBFS(graph, q, discovered);
            }
        }
    }
}

输出:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

性能

空间复杂度

因为所有节点都必须被存储,因此BFS的空间复杂度为O(|V| |E|),其中 |V|是节点的数目,而|E|是图中边的数目。另一种说法称BFS的空间复杂度为O(B^M),其中B是最大分支系数,而M是树的最长路径长度。由于对空间的大量需求,因此BFS并不适合解非常大的问题,对于类似的问题,应用IDDFS以达节省空间的效果。

时间复杂度

最差情形下,BFS必须查找所有到可能节点的所有路径,因此其时间复杂度为O(|V| |E|),其中|V|是节点的数目,而|E|是图中边的数目。

BFS 的应用

  • 复制垃圾收集,切尼算法。
  • 找到两个节点u和之间的最短路径v,路径长度由边的总数测量(优于深度优先搜索)。
  • 测试图表的二分性。
  • 未加权图的最小生成树。
  • 网络爬虫。
  • 在图的任何连接组件中查找节点。
  • Ford-Fulkerson 方法用于计算流网络中的最大流量。
  • 二叉树的序列化/反序列化与排序顺序的序列化可以有效地重建树。

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanfbebh
系列文章
更多 icon
同类精品
更多 icon
继续加载