边集数组

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

定义边集数组是由两个一维数组构成，一个是存储顶点的信息，另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin），终点下标（end）和权（weight）组成。带权图（网）的另一种存储结构是边集数组，它适用于一些以边为主的操作。用边集数组表示带权图时，列出每条边所依附的两个顶点及边上的权，即每个数组元素代表一条边的信息。

例子前向星是一个边集数组，把边的起点终点和权值存起来，然后以起点从小到大或者从大到小排序，记录每个顶点在数组中的起始位置和长度.。适用于点多边少的稀疏图，或两点之间有多条弧的时候。1

下面介绍一下链式前向星构造方法如下：
(1)每读入一条边i的信息；

(2)将边的终点和权值存放在数组中；

(3)把该条边的next=headlist[a]。

前向星就构造完了。

代码如下：

#include #include #include using namespace std;#define maxedge 20000#define maxn 5000 //结点数#define inf 1