离散数学正向表是什么

离散数学正向表是什么

离散数学中，正向表是对邻接矩阵的行进行压缩的结果，
它的特点是将每个顶点的邻接顶点集中在一起存放。
有向图的正向表使用一个一维|V|元数组A和一个一维|E|元数组B表示，
无向图的正向表使用一个一维|V|元数组A和一个一维2|E|元数组B表示。
具体做法：
首先将所有邻接于顶点1的顶点标号依次写入B中，并将最后一个邻接顶点在B的地址记录在A[1]中；
然后将所有邻接于顶点2的顶点标号依次写入B中，并将最后一个邻接顶点在B中的地址记录在A[2]中；
这样一直进行下去，直到与最后一个顶点相邻的顶点标号都存入B为止。
正向表的空间代价与邻接表相当，但是由于正向表没有使用指针而减少了一部分结构性开销。