|
|
|
|
|
图是重要的一类非线性结构，应用极为广泛，其形式化定义可写为：
|
|
|
|
|
|
其中，V=｛x|x∈datatype｝,R=｛VR｝, VR=｛<x,y>|P（x,y）∧（x,y∈V）｝。
|
|
|
|
在图中，数据元素常称为顶点，V是顶点的有穷集合；R是边（弧）的有穷集合。可见，从逻辑上看，图是由顶点和边组成，边反映出顶点之间的联系。
|
|
|
|
|
|
图主要有以下4种存储结构：邻接矩阵、邻接表、邻接多重表及十字链表。其中最常用的存储结构为邻接矩阵和邻接表，尤其是邻接表。
|
|
|
|
邻接矩阵是表示顶点之间相邻关系的矩阵。有n个顶点的图G=（V,E）的邻接矩阵为n阶方阵，其定义为：
|
|
|
|
|
|
将邻接矩阵中的0、1换成权值，就是图的邻接矩阵。无向图的邻接矩阵是对称矩阵；顶点vi的度是邻接矩阵中第i行（或第i列）的元素1之和。有向图的邻接矩阵不一定是对称矩阵；顶点vi的出度是邻接矩阵中第i行元素之和，入度是邻接矩阵中第i列的元素之和。
|
|
|
|
可见，通过邻接矩阵可以很容易地判定顶点间有无边（弧），容易计算顶点的度（出度、入度）；缺点是所占空间只和顶点个数有关，和边数无关，在边数较少时，空间浪费较大。一般在顶点数较少且边数稠密时应用邻接矩阵。
|
|
|
|
邻接表是为克服邻接矩阵在图为稀疏图时的空间浪费大这个缺点而提出的。
|
|
|
|
邻接表是顶点的向量结构和边（弧）的单链表结构的集合，每个顶点节点包括两个域，将n个顶点放在一个向量中（称为顺序存储的节点表）；一个顶点的所有邻接点链接成单链表，该顶点在向量中有一个指针域指向其第一个邻接点。邻接表的结构如下：
|
|
|
 顶点节点
|
|
|
 边（弧）节点
|
|
|
|
其中，vexdata是顶点数据，firstarc是指向该顶点第一个邻接点的指针，adjvex是邻接点在向量中的下标，info是邻接点的信息，next是指向下一邻接点的指针。
|
|
|
|
对无向图，容易求各顶点的度；边表中节点个数是边数的两倍。对有向图，容易求顶点的出度；若求顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。所谓逆邻接表就是对图中的每个顶点i建立一个单链表，把被i邻接的顶点放在一个链表中，即边表中存放的是入度边而不是出度边。一般在处理以顶点为主且为边稀疏时用邻接表。
|
|
|
|
邻接多重表是为了解决邻接表不利于处理以边为主的情况，因为在邻接表中，每条边需要两个边节点，在以边为主处理图时，需判断此边是否处理过，增加了复杂性。图的邻接多重表中每个边只有一个节点，其节点结构如下：
|
|
|
 顶点节点
|
|
|
 边节点
|
|
|
|
十字链表为邻接表不利于求出顶点的入度这个缺点而提出的，其节点结构如下：
|
|
|
 顶点节点
|
|
|
 弧节点
|
|
|
