图状结构是一种比树形结构更复杂的非线性结构。在树状结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图状结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。
8.1.1 图的定义和术语
1．图的定义
图(Graph)是由非空的顶点集合和一个描述顶点之间关系――边（或者弧）的集合组成，其形式化定义为：
G＝（V，E）
V＝{vi| vi∈dataobject}
E＝{( vi,vj)| vi, vj ∈V ∧P(vi, vj)}
其中，G 表示一个图，V 是图G 中顶点的集合，E 是图G 中边的集合，集合E 中P(vi,vj)表示顶点vi 和顶点vj 之间有一条直接连线，即偶对(vi,vj)表示一条边。图8.1 给出了一个图的示例，在该图中：
集合V＝{v1,v2,v3,v4,v5}；
集合E＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。 |
