擅长:python、mysql、java
<p>对我来说,C似乎是最有效的,因为您所做的查找平均为O(1)。(<strong>注意,</strong>这是平均情况,<strong>不是最坏情况。)对于邻接列表,您可以使用最坏情况线性搜索。你知道吗</p>
<p>对于稀疏图,您可能希望使用邻接列表(a),因为它们占用的空间较少。然而,对于稠密图,选项C应该是最有效的。你知道吗</p>
<p>A和B将有非常相似的运行时-渐近相同。除非您希望将邻居之外的数据添加到这些节点,否则我将选择A</p>
<p>我不熟悉python;但是,对于Java,可以通过使用HashSet(set)来改进选项C,这将减少您的空间需求。运行时与使用HashMap相同,但集合不存储值-仅存储键,这是检查两个节点之间是否存在边所需的。你知道吗</p>
<p>所以,澄清一下:</p>
<p>对于运行时,选择C。您将有平均情况O(1)边缘添加。为了改进C语言以减少内存消耗,可以使用集合而不是映射,这样就不必为值分配空间。你知道吗</p>
<p>对于内存,如果有稀疏图,请选择一个。您将节省大量内存,并且在运行时方面不会损失太多。作为参考,稀疏是指节点没有太多邻居的情况;例如,在一个有20个节点的图中,每个节点大约有2个邻居。你知道吗</p>