边集数组

边集数组（edgeset array）是利用一维数组存储图中所有边的一种图的表示方法。该数组中所含元素的个数要大于等于图中边的条数，每个元素用来存储一条边的起点、终点（对于无向图，可选定边的任一端点为起点或终点）和权（若有的话），各边在数组中的次序可任意安排，也可根据具体要求而定。

边集数组只是存储图中的所有边的信息，若需要存储顶点信息，则还需要另外一个具有n个元素的一维数组。设图G中的顶点数为n，边数为e，且不需要存储顶点信息，则图的边集数组表示的有关类型定义和生成一个无向带权图的边集数组的算法描述如下:

type degenode=record{} fromvex，endvex:1..n; {边的起点和终点域，亦可定义为其它子域型或自定义型}

weight:{权值的类型，对无权图可省去此域}end edgeset=array〔1..m 0 〕of edgenode; {定义边集数组类型，其中m 0 要大于等于图中的边数e}

procedure crate3（GE）; {GE为具有edgeset类型的变参，表示一个边集数组}

begin

for k:=1 to e do （1）

read（i，j，w）;{读入一条边的信息}

2）

GE〔k〕.fromvex:=i;

GE〔k〕.endvex:=j;

GE〔k〕.weight:=w {把读入的一条边写入边集数组的第k个单元}

end;

在边集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以其时间复杂性为O（e）。

边集数组适合那些对边依次进行处理的运算，不适合对顶点的运算和对任一条边的运算。

边集数组表示通常包括一个边集数组和一个顶点数组，所以其空间复杂性为O（n+e）。从空间复杂性上讲，边集数组也适合表示稀疏图。图的邻接矩阵、邻接表示和边集数组表示各有利弊，具体应用时，要根据图的稠密和稀疏程度以及运算的要求进行选择。