data-structures - 质疑图形的教学方式

Question

我来自阿根廷，但我认为每个上过数据结构类(class)的人都知道图是什么。如果这样做，您可能知道什么样的实现是“通用”或“标准”的。可以通过一个List，或者一个数组来实现。甚至维基百科也这么说。以及 Mark Allen Weiss、Bruno Preiss 和 Luis Joyanes Aguilar。

事情是这样的。从来没有人认为这不是一种好方法吗？最推荐的方法是通过列表。但是考虑到顶点之间只能有一条边，我认为 List 不是执行此操作的好接口(interface)。我的意思是，如果 Vertex V1 与 Vertex V2 相连，则只有一条边。

你不认为它会是一个集合而不是一个列表吗？

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

只是想知道一些看法，你怎么看？

谢谢!!

编辑:另外，如果我们认为 Graph 不能有重复的元素，HashSet 将是一个很好的选择，可以最大限度地减少插入时对顶点的查找。

Answer 1

您正确地指出顶点的邻接由集合(或者在多重图的情况下，多重集)最准确地建模。那么，为什么数据结构书籍会写数组和链表呢？我可以想到三个原因:

1. 编程语言应该将集合作为原始数据类型的想法是最近才出现的。年长的作家不会考虑使用它，现代作家倾向于遵循该领域的传统。

2. 数据结构类(class)的目的之一是让您能够在低(具体)级别和高(抽象)级别考虑数据的表示。集合是一种抽象数据类型(与链表和数组不同)没有明显的低级实现:一些集合最好表示为链表，一些表示为哈希表，一些表示为数组，等等。因此，数据结构类(class)很自然地会跳过集合的高级表示来了解它们的低级实现，无论如何您都必须了解这些，以便分析使用它们的算法的行为。

   <

3. 重要的是不要对如何表示数据类型固执己见，因为使用特定的表示形式可以最有效地表达算法。示例 1. 要计算图中每对顶点之间长度为 n 的路径，请用邻接矩阵表示该图，并将该矩阵乘以 n 次方。如果您坚持将顶点的邻接表示为一组边，那么您将错过这个算法(可以使用标准技术并行化)。示例 2. Knuth 针对精确覆盖问题的“Dancing Links”算法使用双向链表表示列集，因此可以重复使用已删除项的链接以实现高效回溯。