算法:广度优先遍历

广度优先搜索(BFS)算法以宽幅运动遍历图形并使用队列记住在任何迭代中发生死角时获取下一个顶点以开始搜索。

广度优先遍历

如在上面给出的示例中,BFS算法首先从A到B到E到F,然后到C和G,最后到D.它采用以下规则。

  • 规则1 - 访问相邻的未访问顶点。 将其标记为已访问。显示它。将其插入队列中。

  • 规则2 - 如果未找到相邻顶点,则从队列中删除第一个顶点。

  • 规则3 - 重复规则1和规则2,直到队列为空。

穿越 描述
1 广度优先搜索第一步 初始化队列。
2 广度优先搜索第二步 我们从访问 **S** (起始节点)开始,并将其标记为已访问。
3 广度优先搜索第三步 然后我们从 **S** 看到一个未访问的相邻节点。在这个例子中,我们有三个节点,但按字母顺序我们选择 **A** ,将其标记为已访问并将其排入队列。
4 广度优先搜索第四步 接下来,从未访问的邻接节点 **小号** 是 **乙** 。我们将其标记为已访问并将其排入队列。
5 广度优先搜索第五步 接下来,从未访问邻接节点 **小号** 是 **Ç** 。我们将其标记为已访问并将其排入队列。
6 广度优先搜索第六步 现在, **S** 没有未访问的相邻节点。所以,我们出队,并找到 **一个** 。
7 广度优先搜索第七步 从 **A** 我们有 **D** 作为未访问的相邻节点。我们将其标记为已访问并将其排入队列。

在这个阶段,我们没有未标记(未访问)的节点。但是根据算法我们继续出列以获得所有未访问的节点。当队列清空时,程序结束。

树表示由边连接的节点。我们将具体讨论二叉树或二叉搜索树。二叉树是用于数据存储目的的特殊数据结构。二叉树具有特殊条件,即每个节点最多可以有两个子节点。二叉树具有有序数组和链表的优点,因为搜索与排序数组一样快,插入或删除操作与链表 ...