> 文章列表 > 图的广度优先搜索或 BFS

图的广度优先搜索或 BFS

图的广度优先搜索或 BFS

广度优先搜索 (BFS) 算法用于在树或图形数据结构中搜索满足一组条件的节点。它从树的根或图开始,在移动到下一个深度级别的节点之前搜索/访问当前深度级别的所有节点。广度优先搜索可用于解决图论中的许多问题。

类似于树的广度优先遍历。 

这里唯一的问题是,与树不同,图可能包含循环,因此我们可能会再次来到同一个节点。为了避免多次处理一个节点,我们将顶点分为两类:

  • 访问和
  • 没有去过。

布尔访问数组用于标记访问的顶点。为简单起见,假设所有顶点都可以从起始顶点到达。BFS 使用队列数据结构进行遍历。