algorithm - 在给定邻接表表示的情况下，查找通用接收器的时间复杂度是多少

Question

这个问题有很多变体，要求在 O(|V|) 时间内解决。

但是，如果我想计算图中是否存在通用接收器并且我的图在邻接列表中表示，那么最坏的情况是什么？这很重要，因为所有其他算法似乎都更适用于邻接列表，因此如果查找通用接收器不是我需要的过于频繁的操作，我肯定会继续使用列表而不是矩阵。

在我看来，时间复杂度就是图的大小，即 O(|V| + |E|)。寻找图的通用汇点的算法如下。假设有近邻列表，从图的索引 1 开始。检查索引 1 处的邻接表长度，如果它是 |V| - 1，然后遍历链表，检查是否存在自循环。如果列表没有自循环并且所有其他顶点都是列表的一部分，则存储列表索引。然后，我们必须遍历其他列表来检查这个顶点是否是他们列表的一部分。如果是，则存储的顶点不能是通用汇。从下一个索引继续搜索。即使列表是外邻列表，我们也必须搜索具有 length = 0 列表的顶点，然后搜索所有其他列表以检查该顶点是否存在于它们各自的列表中。

从上面的解释可以得出结论，无论考虑什么形式的邻接表，在最坏的情况下，找到通用汇点必须遍历所有顶点和边一次，因此复杂度是图的大小，即 O(|V|+|E|)

但是我最近加入大学担任助理教授的 friend 提到它必须是O(|V|*|V|)。在他 Spring 开始教授这门类(class)之前，我正在复习他的笔记，但在更正之前，我想百分百确定。

Answer 1

你说得很对。我们可以构建跟踪所有中间结果所需的结构，但基本的复杂性仍然很简单:我们遍历所有边缘一次，标记和计算引用。我们甚至可以在 O(E) 时间内构建一个完整的转换矩阵。

根据数据结构，我们可能会发现通过遍历所有边的第二次遍历得到改进，但 2 * O(E) 仍然是 O(E)。

然后我们遍历每个节点一次，寻找输入/输出计数和自循环。