面向对象的图数据结构实现

Question

面向对象的图数据结构实现

7

我最近一直在阅读关于图形数据结构的文章，因为我打算编写自己的UML工具。据我所见，我想要的可以建模为一个简单的图，由顶点和边组成。顶点将有几个值，并且最好表示为对象。就我所看到的，边不需要是有向或加权的，但我不希望选择一种实现方式，使得以后无法包括这些属性。

作为一个受过纯面向对象编程教育的人，我首先想到的是通过类来表示顶点和边，例如：

Class: Vertice
    - Array arrayOfEdges;
    - String name;

Class: Edge
    - Vertice from;
    - Vertice to;

这使我能够稍后引入权重、方向等概念。现在，当我查阅有关实现图表的资料时，似乎这是一种非常不常见的解决方案。之前在Stack Overflow上的问题建议使用邻接列表和邻接矩阵，但对于完全新手的我来说，很难理解为什么它比我的方法更好。

我应用程序最重要的方面是能够轻松计算点击并移动哪个顶点，以及添加和删除顶点和顶点之间的边缘。这是否在一个实现中比另一个实现更容易实现？

我选择的语言是Objective-C，但我不认为这应该有任何影响。

- Bendik

3个回答

1

相邻矩阵在添加和删除顶点（但不是边）时比您的对象模型更困难，因为这涉及从矩阵中添加和删除行和列。有一些技巧可以用来解决这个问题，例如保留空行和列，但仍然会有一些复杂性。

当将顶点移动到屏幕上时，边也会被移动。这也使得您的对象模型具有轻微的优势，因为它将具有连接边的列表，并且不必搜索矩阵。

两种模型都具有边的固有方向性，因此，如果您想要无向边，则必须进行额外的工作。

总体而言，我认为没有太大的区别。如果我要实现这个功能，我可能会做类似于您正在做的事情。

- Jeffrey L Whitledge

0

如果您正在使用Objective-C，我假设您可以访问Core Data，这可能是一个很好的起点 - 我了解到您正在创建自己的图形，Core Data的优势在于，如果您正确设置模式，则可以免费执行您所说的许多检查。

- Nektarios

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Regexident · Accepted Answer

以下是两种基本图形类型及其典型实现：

稠密图:

稀疏图:

在我编写的图框架中(遗憾的是不开源)，我已经实现了(有向/无向/混合)超图、(有向/无向/混合)多图、(有向/无向/混合)有序图、(有向/无向/混合)K分图，以及各种树，例如通用树、(A,B)树、KAry-树、Full-KAry-树。(未来将要实现的树：VP-Trees、KD-Trees、BKTrees、B-Trees、R-Trees、Octrees等)。并且所有这些都没有单独的顶点或边缘类，完全是泛型实现。几乎没有冗余实现。
噢，如果这还不够，它们都存在着可变、不可变、可观察(NSNotification)、线程不安全和线程安全版本。
如何实现的呢？通过大量使用装饰器模式。
基本上所有图形都是可变的、线程不安全的，也不可观察。因此，我使用装饰器来为它们添加各种风味(结果只有35个类，而不是500多个类)。

虽然我不能提供实际的代码，但我的图形基本上是通过关联表实现的，主要使用NSMutableDictionaries和NSMutableSets(以及我的有序树使用NSMutableArrays)。

我的无向稀疏图只有这些实例变量，例如：

NSMutableDictionary *vertices;
NSMutableDictionary *edges;

ivar vertices映射顶点到相邻的顶点与关联边（{"vertex": {"vertex": "edge"}}）的字典，而ivar edges将每条边映射到其相邻的顶点对（{"edge": {"vertex", "vertex"}}），其中Pair是一个包含边的头部和尾部顶点的数据对象。 混合稀疏图具有稍微不同的邻接/关联列表映射，定向稀疏图也是如此，但您应该能够理解。

这种实现的局限性在于，每个顶点和每条边都需要有与之关联的对象。为了使事情更有趣，每个顶点对象都需要是唯一的，每个边缘对象也是如此。这是因为字典不允许重复键。另外，对象需要实现NSCopying。然而，NSValueTransformers或值封装是绕过这些限制的方法（从字典键复制的内存开销也是如此）。

虽然该实现有它的缺点，但有一个巨大的好处：极高的通用性！我几乎想不出有哪种类型的图形是无法通过我已经拥有的东西实现的。您基本上只需要从自己的乐高积木盒子里组装所需的图形，而不是使用定制构建的零件构建每种类型的图形。

每种主要的图形类型都有自己的协议，这里列举了一些：

HypergraphProtocol
    MultigraphProtocol [tagging protocol] (allows parallel edges)
    GraphProtocol (allows directed & undirected edges)
        UndirectedGraphProtocol [tagging protocol] (allows only undirected edges)
        DirectedGraphProtocol [tagging protocol] (allows only directed edges)
            ForestProtocol (allows sets of disjunct trees)
                TreeProtocol (allows trees)
                    ABTreeProtocol (allows trees of a-b children per vertex)
                        FullKAryTreeProtocol [tagging protocol] (allows trees of either 0 or k children per vertex)

协议的嵌套涵盖了继承(包括协议和实现)。

如果您还想了解更多信息，请随时留下评论。

附言: 为了给予应有的荣誉: 架构受到了JUNG Java图形框架(55k+ loc)的很大影响。

二话不说: 在选择这种类型的实现之前，我曾经写过一个只支持无向图的小兄弟，我希望将其扩展为也支持有向图。我的实现与你在问题中提供的实现非常相似。这就是当时导致我的第一个(相当幼稚的)项目突然结束的原因：Objective-C中子类化一组相互依赖的类并确保类型安全性将简单的有向性添加到我的图形中，使整个代码都崩溃了。(我甚至没有使用当时发布的解决方案，因为它只会推迟痛苦) 现在，我已经实现了20多种图形风格的通用实现，没有任何hack。它很值得。

如果你只想画一个图并能够在屏幕上移动其节点，那么你可以只实现一个通用的图形类，如果需要，可以稍后扩展到特定的有向性。