2

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

事情是。从来没有人认为这不是一个好方法吗？最推荐的方式是通过列表。但考虑到顶点之间只能有一条边，我不认为 List 是做到这一点的好接口。我的意思是，如果 Vertex V1 与 Vertex V2 相连，那么只有一条边。

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

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

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

谢谢！！

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

4

3 回答 3

5

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

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

  2. 数据结构课程的目的之一是使您能够在低（具体）级别以及高（抽象）级别考虑数据的表示。集合是一种抽象数据类型，它（与链表和数组不同）没有明显的低级实现：一些集合最好表示为链表，一些作为哈希表，一些作为数组，等等。因此，对于数据结构课程来说，跳过集合的高级表示到它们的低级实现是很自然的，为了分析使用它们的算法的行为，无论如何你都必须知道这一点。

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

于 2010-12-22T13:25:12.920 回答
2

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

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

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

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

calloc(number_of_nodes, sizeof(struct vertex));

我不确定（在相对较低的级别）编译器内部是什么/如何实现此内存分配 - 是否是列表/集合/映射。

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

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

于 2010-12-22T13:37:00.440 回答
1

在最抽象的情况下，Set 有一个谓词来测试元素是否在集合内。它还可以支持提供联合和交叉的运算符。差异不一定是可计算的。

List 最抽象地支持迭代、子列表和追加。

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

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

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

于 2010-12-22T13:25:39.380 回答