BFS的运行时间是O(b^d)

b是分支因子，d是从起始节点到图的深度（层数）。

我谷歌了一会儿，但还是没看到有人提到他们是如何确定这个“b”的

所以我知道分支因子意味着“每个节点拥有的子节点数量”

例如，二叉树的分支因子是2。

那么对于BFS图来说，是b=图中每个节点的分支因子的平均值，

还是b = MAX(所有节点的分支因子中的最大值)？

此外，无论我们选择哪种方式来确定b，似乎都难以准确地估算我们的运行时间。例如，如果我们的图有30000个节点，只有5个节点有10000个分支，其余29955个节点只有10个分支。我们将深度设置为100。

在这种情况下，O(b^d)似乎没有意义。

能有人解释一下吗？谢谢！

回答：

更常引用的运行时间是BFS是O(m + n)，其中m是边的数量，n是节点的数量。这是因为每个顶点被处理一次，每条边最多被处理两次。

我认为O(b^d)是在使用BFS进行暴力破解游戏（例如国际象棋）时使用的，每个位置具有相对恒定的分支因子，你的引擎需要搜索一定深度的位置。例如，国际象棋的b大约是35，深蓝的搜索深度为6-8（最高可达20）。

在这种情况下，因为图相对无环，b^d大致等于m + n（对于树来说它们是相等的）。O(b^d)更有用，因为b是固定的，d是你可以控制的。