具有邻接列表的恒定时间操作
我正在使用必须使用与边缘+顶点成比例的空间的邻接列表在Java中实现一个图。我的初始程序包含一个长度为V的数组（顶点数），每个索引都包含一个边的ArrayList，显示连接到每个顶点的所有边。具有邻接列表的恒定时间操作
现在，我被告知操作existsEdge（x，y）必须在O（1）时间运行。 我想过的方式是访问数组中的索引x（以O（1）时间）并检查该索引处的列表是否具有Edge（x，y）。
但是，我不确定这个时间的复杂性。我知道ArrayList在任何特定索引处的长度永远不会超过图中顶点的数量，但我不确定这是否被认为是恒定时间。无论数据量如何，每个列表的长度将为< = V，因此遍历具有明确的上限。
这与O（1）相同，还是这是一个不同的时间复杂度？如果它不同，我不太确定如何使用ArrayList来创建这个结构。
您描述的内容不被视为O（1），它是O（V），最坏情况下的原因是顶点可能连接到所有其他顶点，并且ArrayList的长度为V-1。如果你想O（1），你应该使用HashSet而不是ArrayList。另外，您不需要Edge类，只需存储连接的顶点。让我们假设顶点1连接到2,4和5，然后在数组中的位置1，您将拥有一个HashSet（2,4,5）。现在，如果你必须检查是否存在边（1,4），你可以去数组的索引1（如你所描述的），然后你可以调用array[1].contains(4)，这是一个O（1）操作。
谢谢 - 我存储边缘的原因是因为它们也有重量，所以我觉得存储边缘本身可以防止我丢失边缘权重上的数据。有关于此的任何想法？ – rubyquartz
然后使用HashMap而不是HashSet。使用顶点作为键，权重作为值。像array [1] = [（2→w12），（4→w14），（5→w15）]。您仍然可以使用数组[1] .containsKey检查O（1）中的存在性，并使用数组[1] .get获得O（1）中的边权重。 – Pedro
您可以分享您迄今为止所做的工作吗？ – Yash
我通常会这样做，但这是作业的一部分。基本上，我有一个索引从0到V-1的数组。例如，如果顶点1连接到0,3和4，... arr [1]包含具有以下{Edge（0,1），Edge（1,3），Edge（1,4 ）}。如果我调用existsEdge（1,3），它应该在常量时间内返回true。 @Yash – rubyquartz