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 是节点数。这是因为每个顶点处理一次，每条边最多处理两次。
我认为在使用 BFS 时会使用 O(b^d)，例如，暴力破解国际象棋游戏，其中每个位置都有一个相对恒定的分支因子，并且您的引擎需要深入搜索一定数量的位置。例如，国际象棋的 b 约为 35，深蓝的搜索深度为 6-8（最高可达 20）。
在这种情况下，由于图是相对无环的，所以 b^d 与 m + n 大致相同（它们对于树是相等的）。O(b^d) 更有用，因为 b 是固定的，而 d 是您可以控制的。
在图中O(b^d)，b = MAX。因为这是最坏的情况。检查来自普林斯顿http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Breadth-first_search.html的链接- 转到时间复杂度部分
引用人工智能——Stuart Russel 和 Peter Norvig 的现代方法：
时间和空间复杂度总是根据问题难度的某种度量来考虑。在理论计算机科学中，典型的度量是状态空间图的大小，|V | + |E|，其中 V 是图的顶点（节点）集合，E 是边（链接）集合。当图形是输入到搜索程序的显式数据结构时，这是合适的。（罗马尼亚的地图就是一个例子。）在人工智能中，图形通常由初始状态、动作和转换模型隐式表示，并且通常是无限的。由于这些原因，复杂性用三个量表示： b，任何节点的分支因子或最大后继数；d，最浅目标节点的深度（即从根开始沿路径的步数）；和米，状态空间中任何路径的最大长度。时间通常以搜索期间生成的节点数来衡量，而空间则以存储在内存中的最大节点数来衡量。在大多数情况下，我们描述了在树上搜索的时间和空间复杂度；对于图，答案取决于状态空间中路径的“冗余”程度。
这应该让您清楚地了解 O(|V|+|E|) 和 b^d 之间的区别