对图表的教学方式提出疑问

Question

我来自阿根廷，但我想每个上过数据结构课的人都知道图是什么。如果您这样做，您可能知道哪种实现是“通用”或“标准”。可以通过List，或者数组来实现。甚至维基百科也这么说。还有马克·艾伦·韦斯、布鲁诺·普莱斯和路易斯·乔亚内斯·阿吉拉尔。

问题是。没有人想过这不是一种好方法吗？最推荐的方法是通过列表。但考虑到顶点之间只能有一条边，我不认为列表是执行此操作的良好界面。我的意思是，如果顶点 V1 与顶点 V2 连接，则只有一条边。

您不认为这将是一个集合而不是列表吗？

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

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

谢谢！！

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

Answer 1

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

1. 编程语言应该包含集合作为原始数据类型的想法是相当新的。年长的作者不会考虑使用它，而现代的作者则倾向于遵循该领域的传统。

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

3. 重要的是不要对如何表示数据类型教条，因为使用特定的表示可以最有效地表达算法。示例 1. 要计算图中每对顶点之间长度为 n 的路径，请用图的邻接矩阵表示该图，并将该矩阵求 n 次幂。如果您坚持将顶点的邻接表示为一组边，那么您将错过此算法（可以使用标准技术进行并行化）。示例 2. Knuth 针对精确覆盖问题的“Dancing Links”算法表示使用双向链表，以便可以重用已删除项目的链接以进行有效的回溯。

Answer 2

在相对较高的 C/C++ 程序员级别，图/网络的实现方式在很大程度上取决于对其执行的操作。作为一个 OR 人，我在这里的回答/例子可能有偏见。可以在图/网络上实现的一些最有效的算法是多项式时间算法。我能想到的大多数（如果不是全部）多项式时间算法（Dijkstra 的最短路径问题、运输问题、最大流问题等）都是最小成本流 (MCF) 问题的特殊情况。在计算上，解决 MCF 问题的最有效方法之一是通过网络单纯形算法（其本身是解决一般线性程序的单纯形算法的特化）。

在网络单纯形算法中，需要有效地表示生成树（在节点集上）。为了在图中表示生成树，可以使用多种数据结构。其中包括以下节点长度

predecessor[], thread[] and depth[] arrays.

在我遇到的网络单纯形算法的最有效实现中，这些并不表示为数组，而是通过我不确定的某种动态创建的内存块

calloc(number_of_nodes, sizeof(struct vertex));

（相对较低级别）编译器内部的内存分配是如何实现的 - 无论是列表/集合/映射。

因此，总而言之，实现图的最佳方法高度依赖于对其执行的操作。

网络单纯形算法以及高效实现该算法所需的数据结构可以在本书中找到。

Answer 3

从最抽象的角度来看，集合有一个谓词来测试某个元素是否在集合内。它还可以支持提供并集和交集的运算符。差异不一定是可计算的。

从最抽象的角度来看，List 支持迭代、子列表和追加。

大多数图算法都要求您迭代边缘，因此支持迭代的结构是首选。大多数算法不会尝试将相同的边添加两次，因此不需要删除重复项。

当然，库中的大多数集合都是有限的、可扩展的集合，它们也支持迭代，因此您可以使用它们，尽管您仍然需要检查重复项的成本。

一些基于图的系统确实使用集合作为底层机制，但它们处理的是无限图而不是有限图，在有限图中内涵集变得有用。