检查恒定时间内是否存在边

问：

原始问题：在 DAG 中查找哈密顿路径的算法

选择答案：

您可以首先以 O（n+m） 格式对 DAG 进行拓扑排序（每个 DAG 都可以进行拓扑排序）。

完成此操作后，您就知道边从较低的索引顶点变为较高的索引顶点。这意味着当且仅当连续顶点之间存在边时，才存在哈密顿路径，例如

(1,2), (2,3), ..., (n-1,n).

（这是因为在哈密顿路径中，你不能“回去”，但你必须访问所有，所以唯一的方法是“不跳过”）

您可以在 O（n） 中检查此条件。

因此，总体复杂度为 O（m+n）。

- 佩塔尔·伊万诺夫

如何检查这种情况？我没有足够的声誉，因此，我正在“复制”这个帖子。此外，我找不到其他帖子来解释如何在恒定的时间内访问边缘。

假设有从拓扑排序中导出的对 （1,2），（2,3）， ...， （n-1，n），因此将有 n-1 对源顶点和尾顶点（即边）需要检查。因此，我们需要遍历这些货币对中的 n-1 个，并检查这两个货币对之间是否存在边。

因此，如果条件可以像 Pertar 所说的那样“在 O（n）”中检查，这将得出结论，我们可以访问 O（1） 中的边（即恒定时间）。没有提到使用或可用的邻接矩阵，该矩阵允许我们在恒定时间内检查源顶点和尾顶点之间是否存在边。我错过了什么？在最坏的情况下，是否有某种数据结构用于实现这种恒定时间搜索？