Data Structures Algorithms 简明教程
Breadth First Search (BFS) Algorithm
Breadth First Search (BFS) Algorithm
广度优先搜索 (BFS) 算法以广度优先的方式遍历图，以搜索符合一组条件的节点的图数据结构。当在任何迭代中出现死角时，它使用队列记住下一个开始搜索的顶点。
Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion to search a graph data structure for a node that meets a set of criteria. It uses a queue to remember the next vertex to start a search, when a dead end occurs in any iteration.
广度优先搜索 (BFS) 算法从树根开始，在移动到下一层级的节点之前探索当前层级中的所有节点。
Breadth First Search (BFS) algorithm starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.
正如以上给出的示例，BFS 算法首先从 A 到 B 到 E 到 F，然后到 C 和 G，最后到 D。它采用以下规则。
As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs the following rules.
-
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
-
Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
-
Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.
在此阶段，我们只剩下未标记（未访问）的节点。但根据算法，我们会不断出列以获取所有未访问的节点。当队列清空后，程序结束。
At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the program is over.
Example
以下是广度优先搜索 (BFS) 算法在各种编程语言中的实现 −
Following are the implementations of Breadth First Search (BFS) Algorithm in various programming languages −
单击以查看 Breadth First Search (BFS) Algorithm 的 C 实现
Click to check C implementation of Breadth First Search (BFS) Algorithm