图的存储结构

7.2　图的存储结构

图的存储结构除了存储图中各个顶点外,同时,还要存储顶点与顶点之间的所有关系（边的信息）,而图中顶点之间是多对多的关系,很难用数据元素在存储区中的物理位置来表示元素之间的关系。常用的图的存储结构有邻接矩阵、邻接表和邻接多重表等。

7.2.1　邻接矩阵

对于一个图,可以采用2个数组来表示:①存储所有顶点信息的一维数组；②存储图中顶点之间关系的二维数组,这个二维数组称为邻接矩阵。

设图G有n个顶点,则邻接矩阵是一个n×n的方阵,定义如下。

图7－13所示的是无向图的邻接矩阵表示法,矩阵沿对角线对称,即A（i,j）＝A（j,i）。矩阵A（i,j）＝1表示图中存在一条边（v_i,v_j）,而A（i,j）＝0表示图中不存在边（v_i,v_j）。无向图邻接矩阵的第i行或第i列非零元素的个数就是第i个顶点的度。求顶点v_i的所有邻接点就是将矩阵中第i行元素扫描一遍,若A（i,j）＝1,表示v_j是v_i的邻接点。

图7－13　无向图的邻接矩阵

图7－14所示的是有向图的邻接矩阵表示法,矩阵不一定沿对角线对称,A（i,j）＝1表示顶点v_i邻接到顶点v_j；A（j,i）＝1则表示顶点v_i邻接自顶点v_j。有向图邻接矩阵的第i行非零元素的个数是第i个顶点的出度,而第i列非零元素的个数则是第i个顶点的入度,即第i个顶点的度是第i行和第i列非零元素个数之和。求顶点v_i的所有出边邻接点就是将矩阵中第i行元素扫描一遍,若A（i,j）＝1,表示v_j是v_i的出边邻接点。

图7－14　有向图的邻接矩阵

若图G是带权图,有n个顶点,则邻接矩阵是一个n×n的方阵,定义如下。

其中:w_ij表示边（v_i,v_j）或〈v_i,v_j〉上的权值；∞表示一个计算机允许的、大于所有边上权值的数,也就是一个不可能的极限值。

图7－15所示为无向网的邻接矩阵。

图7－15　无向网的邻接矩阵

通过邻接矩阵可以很容易地判定顶点间有无边,并计算顶点的度（出度、入度）。但是邻接矩阵所占用的空间只与顶点个数有关,与边数无关,在边数较少时,将出现大量零元素,空间浪费较大。一般在顶点数较少且边数稠密时采用邻接矩阵存储。

用邻接矩阵存储图,需要一个二维数组存储边信息,一个一维数组存储顶点信息,还要存储图的顶点数和边数。下面代码即用于创建和输出无向网的邻接矩阵的存储结构。

7.2.2　邻接表

邻接表是为了克服邻接矩阵在存储稀疏图时的空间浪费大的缺点而提出的,在边稀疏的情况下,邻接表要比使用邻接矩阵节省空间。图的邻接表存储方法是顶点的向量结构和边的单链表结构相结合的存储结构。将n个顶点放在一个向量中（顺序存储的表头结点表）,每个顶点对应一个存储在数组中的表头结点,如图7－16所示。表头结点有两部分组成,其中,data是顶点数据,firstEdge是指向该顶点第一个邻接点的指针。一个顶点的所有邻接点依次存放于一个单链表中,单链表中每个结点有两部分组成,其中adjvex是该顶点的邻接点在向量表中的下标,next是指向下一邻接点的指针。

图7－16　邻接表结点结构图

图7－17所示为无向图的邻接表存储。n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。

图7－17　无向图的邻接表

有向图的邻接表又称为出边表。出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点。出边表容易求顶点的出度,但要求顶点的入度需要遍历所有单链表。

有向图的邻接表有出边表和入边表（又称逆邻接表）之分。入边表的表结点存放的则是指向表头结点的某个头顶点,入边表容易求顶点的入度。如图7－18所示,图（b）和（c）分别为有向图（a）的出边表和入边表。

图7－18　有向图的邻接表和逆邻接表

n个顶点e条边的有向图,它的邻接表表示中有n个顶点表结点和e个边表结点。

如果要表示带权图,可以在表结点中增加一个存放权的字段,其效果如图7－19所示。

图7－19　无向网的邻接表

在图的邻接表存储中,若判断两个顶点之间是否有边,需要搜索这两个顶点对应的邻接表,不如邻接矩阵方便。

图的邻接表是一种链式存储结构。在邻接表中,图的每个顶点建立一个单链表,单链表的头结点存放在一个一维数组中。邻接表由两种不同的结点组成,一种是头结点,包括数据域和指针域,数据域用于存放顶点信息；另一种是表结点,包括邻接点域和链域。下面程序是用C语言实现对图的邻接表的构建及邻接表的输出。

7.2.3　邻接多重表

用邻接表存储无向图时,每一条边的两个结点（v_i,v_j）分别在第i个和第j个链表之中,如果需要对已访问过的边做标记,或者要删除图中某一条边等,都需要找到表示同一条边的两个结点。如果无向图的每一条边用一个结点表示,每条边只出现一次,这些问题就容易解决了。邻接多重表就可以满足这个需求,邻接多重表主要用于存储无向图。邻接多重表用一个结点表示无向图的一条边,每条边只出现一次,并通过各指针将这些边互相连接起来,以便于查找。

邻接多重表包含顶点表结点和边表结点两类结点,其结构如图7－20所示。

图7－20　邻接多重表的结点结构

其中,顶点表由两个域组成,vertex域用于存储该顶点的值,firstedge域指示第一条依附于该顶点的边。边表结点由六个域组成,mark为标记域,用于标记该条边是否被访问过或该边的权值；ivex和jvex为该边依附的两个顶点在图中的编号；ilink用于指向下一条依附于顶点ivex的边；jlink用于指向下一条依附于顶点jvex的边。

图7－21所示为无向图的邻接多重表。在邻接多重表中,所有依附于同一顶点的边在同一链表中,由于每条边依附于两个顶点,则每个边结点同时链接在两个链表中。对于无向图,同一条边在邻接表中用两个结点表示,在邻接多重表中只有一个结点。在邻接多重表上,各种基本操作的实现和邻接表相似。

图7－21　无向图的邻接多重表