c++ - O(log n) 中的广度优先搜索

Question

是否可以在具有循环和负边的无向图中使用 BFS(使用遍历的最小顶点)在 O(log n) 时间内从源找到目的地？

例如:给定一个具有 N 个顶点和 N 条边的简单连通图 G(简单图是一种无向图，没有环，并且任意两个不同顶点之间的边不超过一条)。很明显，图 G 正好包含一个圈，你可以假设这个圈的长度是奇数(这个圈中有奇数个顶点)。顶点从 1 到 N 编号。每条边都分配有相应的整数权重。您的任务是激发两种类型的查询:update query f u v 表示:改变顶点u到顶点v的最短路径(后面看本题最短路径的定义)上所有边的权值符号。查找由 ? 表示的查询u v:在从顶点 u 到顶点 v 的最短路径上，找到(可能为空的)一组连续的边，使得权重之和最大。换句话说，让我们将从 u 到 v 的最短路径定义为 a_1、a_2、...、a_k(其中 a_1 = u 和 a_k = v)。你必须找到 a_i 和 a_j 使得 i <= j 并且路径 a_i, a_(i + 1), ..., a_j 的边的权重之和尽可能大。你只需要找到那笔钱。两个顶点 u 和 v 之间的最短路径是连接它们且顶点数最少的路径。在这个问题中，显然G的任意一对顶点之间只有一条最短路径。

Answer 1

设 G 是一个顶点集 V 和边集 E 的图。那么广度优先搜索(BFS)在最坏情况下的时间复杂度是O(|V|+|E|)。时间复杂度是O(|V|+|E|)，因为在最坏的情况下每个顶点和边都被访问了。复杂度 O(|E|) 可能在 O(|V|) 和 O(|V²|) 之间变化。在稀疏图的情况下，复杂度约为 O(|V|)，在密集图的情况下，复杂度约为 O(|V²|)。