san*_*lto 2 graph directed-graph data-structures
我来自阿根廷,但我认为每个参加数据结构课程的人都知道图表是什么.如果你这样做,你可能知道什么样的实现是"常见的"或"标准的".它可以通过List或数组实现.甚至维基百科都这么说.还有Mark Allen Weiss,Bruno Preiss和Luis Joyanes Aguilar.
事情是.没有人认为这不是一个好方法吗？最推荐的方法是通过List.但是考虑到顶点之间只有一条边,我不认为List是这样做的好界面.我的意思是,如果Vertex V1与Vertex V2连接,那么只有一个且只有一个边缘.
难道你不认为它会是一个Set而不是一个列表吗？
Class Vertex{
private Set edges;
private Object data;
/** Methods**/
}
只是想知道一些意见,你怎么看？
谢谢!!
编辑: 此外,如果我们认为图形不能有重复的元素,HashSet将是一个很好的选择,以最小化插入中的顶点的查找.
你是正确的指出顶点的邻接最精确地由一个集合建模(或者在多图形的情况下,多集合).那么为什么数据结构书籍会改写关于数组和链接列表的呢？我可以想到三个原因:
编程语言应该将集合作为原始数据类型的想法是最近的.较老的作家不会考虑使用它,现代作家倾向于遵循该领域的传统.
数据结构课程的目的之一是使您能够在低(具体)级别以及高(抽象)级别考虑数据的表示.set是一种抽象数据类型(与链接列表和数组不同)没有明显的低级实现:一些集合最好表示为链表,一些表示为哈希表,一些表示为数组,依此类推.因此,数据结构课程很自然地跳过集合的高级表示到它们的低级实现,为了分析使用它们的算法的行为,你必须知道它们.
重要的是不要教会如何表示数据类型,因为算法可以使用特定的表示最有效地表达.示例1.要计算图形中每对顶点之间的长度n的路径,请通过其邻接矩阵表示图形,并将矩阵提升到幂n.如果你坚持将顶点的邻近表示为一组边,那么你将错过这个算法(可以使用标准技术进行并行化).示例2. Knuth 针对精确封面问题的" Dancing Links "算法表示使用双向链接列表的列集,以便可以重用来自已删除项目的链接以进行有效的回溯.