为什么使用邻接列表而不是邻接集合来表示图形？ [英] Why are graphs represented using an adjacency list instead of an adjacency set?

问题描述

如果每个节点都映射到它所具有边缘的一组节点，而不是一个列表，我们将获得获得边缘常量时间查找的能力，而不必遍历整个列表。我能想到的唯一缺点是稍微多的内存开销和时间来枚举节点的边缘，但不是渐近地显着。

If each node maps to a set of the nodes it has edges to, instead of a list, we would gain the ability to gain constant time lookup of edges, instead of having to traverse the whole list. The only disadvantage I can think of is slightly more memory overhead and time to enumerate the edges of a node, but not asymptotically significantly so.

推荐答案

我认为list只是一个通用标签，不能从字面上理解。我已经使用了 Set ，它工作得很好。

I think "list" is just a generic label, not to be taken literally. I've used a Set and it works perfectly well.

如果我没有记错，我的课本也使用了 Set 。

If I recall correctly, my textbook also used a Set.

这篇关于为什么使用邻接列表而不是邻接集合来表示图形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！