广度优先搜索

图遍历是按某种系统顺序访问图的所有顶点的问题。遍历图主要有两种方法。

广度优先搜索(BFS)从图G的第0层顶点X开始。然后,我们访问与X相邻的所有顶点。访问后,我们将这些顶点标记为“已访问”,并将它们放置在第-层1。然后,我们从1级顶点开始,并对每个1级顶点应用相同的方法,依此类推。当访问图的每个顶点时,BFS遍历就会终止。

BFS算法

该概念是在访问邻居顶点的其他邻居顶点之前访问所有邻居顶点。

  • 将所有节点的状态初始化为“就绪”。

  • 将源顶点放在队列中,并将其状态更改为“等待”。

  • 重复以下两个步骤,直到队列为空-

    • 从队列中删除第一个顶点,并将其标记为“已访问”。

    • 将状态为“就绪”的已删除顶点的所有邻居添加到队列的尾部。将其状态标记为“正在等待”。

问题

让我们拍一个图(源顶点为“ a”),然后应用BFS算法找出遍历顺序。

解决方案-

  • 将所有顶点的状态初始化为“就绪”。

  • 一个在队列,并且改变其状态为“等待”。

  • 从队列中删除一个,将其标记为“已访问”。

  • 添加一个“邻居‘准备就绪’状态B,dē结束队列,并将其标记为‘等待’。

  • 从队列中删除b,将其标记为“已访问”,将其“就绪”邻居c放置在队列末尾,并将c标记为“等待”。

  • 从队列中删除d并将其标记为“已访问”。它没有邻居处于“就绪”状态。

  • 从队列中删除e并将其标记为“访问”。它没有邻居处于“就绪”状态。

  • 从队列中删除c并将其标记为“访问”。它没有邻居处于“就绪”状态。

  • 队列为空,请停止。

因此遍历顺序为-

a→b→d→e→c

遍历的替代顺序是-

             a→b→e→d→c

或a→d→b→e→c

或a→e→b→d→c

或a→b→e→d→c

或a→d→e→b→c

BFS的应用

  • 寻找最短路径

  • 非加权图的最小生成树

  • GPS导航系统

  • 在无向图中检测周期

  • 查找一个连接的组件中的所有节点

复杂度分析

令G(V,E)为| V |的图 顶点数和| E | 边数。如果广度优先搜索算法访问图形中的每个顶点并检查每个边缘,则其时间复杂度将为-

O(| V | + | E |)。O(| E |)

它可能在O(1)和O(| V2 |)之间变化

以上是 广度优先搜索 的全部内容, 来源链接: utcz.com/z/352534.html

回到顶部