数据结构之图

基本概念

图(Graph)：图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V，E) 线性结构：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。 树结构：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。

图相关的概念和术语

一个图(G)定义为一个偶对(V,E) ，记为G=(V,E) 。其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&V的一个子集，记为E(G) ，其元素是图的弧(Arc)。 将顶点集合为空的图称为空图。其形式化定义为：

G=(V ，E)
V={v|vdata object}
E={| v,w