提问图形的方式

Question

我来自阿根廷，但我认为每个曾经参加数据结构课程的人都知道图形是什么。如果这样做，您可能会知道哪种实现是“常见”或“标准”。它可以通过列表或数组实现。甚至维基百科也这样说。以及马克·艾伦·魏斯（Mark Allen Weiss），布鲁诺·佩里斯（Bruno Preiss）和路易斯·乔伊纳斯（Luis Joyanes Aguilar）。

事情是。没有人认为这不是一个好方法吗？最建议的方法是通过列表。但是考虑到顶点之间只有一个优势，我认为列表不是这样做的好界面。我的意思是，如果顶点V1与顶点V2连接，则只有一个和一个边缘。

您不认为这是一套而不是列表吗？

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

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

谢谢！！

编辑： 另外，如果我们认为该图无法重复元素，则标签将是最大程度地减少插入中顶点的查找的好选择。

Answer 1

您正确地指出，顶点的邻接是最精确地由集合建模（或在多编码的情况下，多式集）。那么，为什么数据结构书籍撰写有关数组和链接列表的文章呢？我可以想到三个原因：

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

2. 数据结构课程的目的之一是使您能够考虑低（具体）级别以及高（摘要）级别的数据表示。一组是一个抽象的数据类型，该数据类型（与链接列表和数组不同）没有明显的低级实现：某些集合最能表示为链接列表，有些是哈希表，有些作为阵列，等等。因此，数据结构课程很自然，可以跳过其低级实现集合的高级表示，您无论如何都必须知道，以分析使用它们的算法的行为。

3. 重要的是不要对如何表示数据类型有教条，因为可以使用特定表示形式最有效地表达算法。示例1.计算长度路径 n 在图中的每对顶点之间，通过其邻接矩阵表示图，并将矩阵提高到功率 n. 。如果您坚持将顶点的邻接表示为一组边缘，那么您会错过此算法（可以使用标准技术并行化）。示例2. Knuth的“跳舞链接“确切封面问题的算法代表使用双链接列表的列集，因此可以将已删除项目的链接重新使用以有效回溯。

Answer 2

在一个相对 更高 C/C ++程序员级别，如何实现图形/网络在很大程度上取决于在其上执行哪些操作。我自己是一个人，我可能会在这里的回应/示例中有偏见。可以在图形/网络上实现的一些最有效的算法是多项式时间算法。大多数（如果不是全部），我可以想到的多项式时间算法（Dijkstra的最短路径问题，运输问题，最大流量问题等）是最低成本流量（MCF）问题的特殊情况。从计算上讲，解决MCF问题的最有效方法之一是通过网络简单算法（本身就是单纯形算法的专业化来求解通用线性程序）。

在网络简单的算法中，需要有效地表示一生（节点集）。为了表示图中的生成树，可以使用各种数据结构。这些包括以下节点长度

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

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

calloc(number_of_nodes, sizeof(struct vertex));

我不确定（在一个相对 降低 级别）在编译器内部使用什么/如何实现此内存分配 - 是否是列表/set/map。

因此，总而言之 最好的 实现图的方法高度取决于要在其上执行的操作。

网络单纯算法和有效实现它所需的数据结构可以在 这本书.

Answer 3

从最抽象的角度来看，一个集合具有测试元素是否在集合中的谓词。它还可以支持提供工会和交叉路口的运营商。差异不是必需的计算。

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

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

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

一些基于图形的系统确实使用集合作为基础机制，但是它们正在处理无限图，而不是有限的图形，而强度集变得有用。