适用于图形的ADT

Question

适用于图形的数据结构是什么？

我想答案因图的类型而异？

无论如何，有什么建议？

Answer 1

看到你想要的抽象数据类型，我不会提及任何有关实现。

的曲线G = <V, E>是一组顶点的V，和一组边缘E其中E每个元素是一个元组e = <v1, v2>，和v1和v2在V的。

下可能看起来像Java，但我真的想任何足够表现力的语言：

interface Graph { 
    Set getVertices(); 
    Set getEdges(); 
    void addVertex(Object v); 
    void addEdge(Object v1, Object v2); 
    void removeVrtex(Object v); 
    void removeEdge(Object v1, Object v2); 
} 

我觉得这是最起码的。我没有指定getEdges返回的内容;如果语言具有本地元组类型，那么它将是一组元素。在实践中，你会希望添加额外的方法，如：

int getDegree(Object v); 
void contractEdge(Object v1, Object v2); 
boolean isIsthmus(Object v1, Object v2); /* does removal of this edge increase the number of components? */ 
int numComponents(); 
boolean isConnected(); /* return numComponents() <= 1 */ 
boolean isCycle(Set path); /* path is a set of edges. */ 

等

扩大这有向图留作练习:-)。

Answer 2

当图形很稀疏时，Map<Vertex, List<Vertex>>（1）会做。如果密度很大，也可以使用2D阵列（2）。

参见：

（1）http://en.wikipedia.org/wiki/Adjacency_list

（2）http://en.wikipedia.org/wiki/Adjacency_matrix

Answer 3

用于存储图的最常见结构中的两个是adjacency lists和adjacency matrices。使用哪种方法通常取决于您计划如何处理图表（因为对于给定的算法，可以提供比其他算法更优化的操作/访问时间）以及图表的稀疏性或密度（列表是对于稀疏图更紧凑，矩阵相对于图的密度更小）。