数据结构——图（1）

数据结构—图

图(Graph)是一种比线性表和树更为复杂的数据结构。

线性结构：它是专门用于研究数据元素之间一对一关系的一种数据组织形式。在这样的结构中，除了第一个和最后一个元素之外的所有元素都只有一个直接前驱和一个直接后继。

树结构的概念：是对研究数据元素之间一对多关系的一种组织形式。在这样的结构中，在一个元素（节点）下一层可以有零个或多个子节点与之相连，在上一层只有一个父节点与其相关联。这种组织方式使得数据元素之间的层次关系清晰可辨。

图结构：是用来探讨数据元素之间的多个节点间的关联的。
在这种结构中，
任何两个节点之间都可能存在关联。
也就是各个节点之间的关联可能是任意的，
图中的任何两个节点都可能相互关联。

（一）图的定义和术语

图形G由两个集合V和E组成一个有序对 (V, E) 。其中,V代表的是图中的所有顶点Vertexes,E代表的是边的数量。在数据结构领域中,我们通常从逻辑关系的角度出发来分析问题,因此可以说任何两个顶点之间可能存在关联,任何一条边都连接着两个特定的顶点。当顶点集为空时，则称该图为空图。其形式化定义为：

G=(V ，E)

V={v|vÎdata object}

E={<v,w>| v,wÎV∧p(v,w)}

P(v,w)表示从顶点v到顶点w有一条直接通路。

弧（Arc）用于描述两个顶点v和w之间的关系，并使用有