图的存储 ——边集数组 & 邻接表

图的存储 ——边集数组 & 邻接表

【边集数组】

边集数组通过数组存储每条边的起点和终点，如果是网，则增加一个权值域。

网的边集数组数据结构定义如下：

struct Edge{
	int u; 
	int v;
	int w;
}e[N * N];

采用边集数组计算节点的度或查找边时，要遍历整个边集数组，时间复杂度为O (e )。

除非特殊需要，很少使用边集数组，例如求解最小生成树kruskal算法时需要按权值对边进行排序，使用边集数组更方便。

【邻接表】

邻接表是图的一种链式存储方法，其数据结构包括两部分：节点和邻接点。

【1 邻接表的表示方法】

① 无向图的邻接表

一个无向图及其邻接表如下图所示。

一个节点的所有邻接点构成一个单链表。

[解释]

• 节点a 的邻接点是节点b 、d ，其邻接点的存储下标为1、3，按照头插法（逆序）将其放入节点a 后面的单链表中；
• 节点b 的邻接点是节点a 、c 、d ，其邻接点的存储下标为0、2、3，将其放入节点b 后面的单链表中；
• 节点c 的邻接点是节点b、d ，其邻接点的存储下标为1、3，将其放入节点c 后面的单链表中；
• 节点d 的邻接点是节点a、b、c ，其邻接点的存储下标为0、1、2，将其放入节点d 后面的单链表中。

[无向图邻接表的特点]

• 如果无向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有2e 个节点。
• 节点的度为该节点后面单链表中的节点数。

上面的例子中，节点数n =4，边数e =5，则在该图的邻接表中，节点表有4个节点，邻接点表有10个节点。节点a 的度为2，其后面单链表中的节点数为2；节点b 的度为3，其后面单链表中的节点数为3。

② 有向图的邻接表( 出弧 )

一个有向图及其邻接表如下图所示

[解释]

• 节点a 的邻接点（只看出边，即出弧）是节点b、c、e ，其邻接点的存储下标为1、2、4，按照头插法（逆序）将其放入节点a 后面的单链表中；
• 节点b 的邻接点【注意只看出】是节点c ，其邻接点的存储下标为2，将其放入节点b 后面的单链表中；
• 节点c 的邻接点是节点d、e ，其邻接点的存储下标为3、4，按头插法将其放入节点c 后面的单链表中；
• 节点d 的邻接点是节点e ，其邻接点的存储下标为4，将其放入节点d 后面的单链表中；
• 节点e 没有邻接点，其后面的单链表为空。【图中可以看到节点e 只有入，没有出】

注意： 对有向图中节点的邻接点，只看该节点的出边（出弧）。

[有向图的邻接表的特点]

• 如果有向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有e 个节点。
• 节点的出度为该节点后面单链表中的节点数。

在上图中，节点数n =5，边数e =7，则在该图的邻接表中，节点表有5个节点，邻接点表有7个节点。节点a 的出度为3，其后面单链表中的节点数为3；节点c 的出度为2，其后面单链表中的节点数为2。

在有向图邻接表中很容易找到节点的出度，但是找入度很难，需要遍历所有邻接点表中的节点，查找到该节点出现了多少次，入度就是多少。例如在下图中，
节点c 的下标为2，在邻接点表中有两个为2的节点，因此节点c 的入度为2；节点e 的下标为4，在邻接点表中有3个为4的节点，因此节点e 的入度为3。

③ 有向图的逆邻接表（入弧）

有时为了方便得到节点的入度，可以建立一个有向图的逆邻接表，如下图所示。

[解释]【这个只看入，不看出】

• 节点a 没有逆邻接点（只看入边，即入弧），其后面的单链表为空；【节点a 全是出】
• 节点b 的逆邻接点是节点a ，其邻接点的存储下标为0，将其放入节点b 后面的单链表中；
• 节点c 的逆邻接点是a、b ，其邻接点的存储下标为0、1，按照头插法将其放入节点c 后面的单链表中；
• 节点d 的逆邻接点是节点c ，其邻接点的存储下标为2，将其放入节点d 后面的单链表中；
• 节点e 的逆邻接点是节点a、c、d ，其邻接点的存储下标为0、2、3，按照头插法（逆序）将其放入节点e 后面的单链表中。

注意： 对有向图中节点的逆邻接点，只看该节点的入边（入弧）。

[有向图的逆邻接表的特点]

• 如果有向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有e 个节点。
• 节点的入度为该节点后面的单链表中的节点数。

在上图中，节点数n =5，边数e =7，在该图的邻接表中，节点表有5个节点，邻接点表有7个节点。

节点a 的入度为其后面的单链表中的节点数0，节点c 的入度为其后面的单链表中的节点数2。

【2 邻接表的数据结构定义】

邻接表的数据结构包括节点和邻接点，对其分别定义如下。

① 节点。

包括节点信息data和指向第1个邻接点的指针first，如下图所示。

typedef struct VexNode{ //定义节点类型
	VexType data; //VexType 为节点信息的数据类型，根据需要定义
	AdjNode *first;  //指向第1个邻接点
}VexNode;

② 邻接点

包括该邻接点的存储下标v 和指向下一个邻接点的指针next，如果是网的邻接点，则还需增加一个权值域w ，如下图所示。

typedef struct AdjNode{ //定义邻接点类型
	int v;  //邻接点下标
	struct AdjNode *next; //指向下一个邻接点
}AdjNode;

邻接表的结构体定义，如下图所示。

【3 邻接表的存储方法】

[算法步骤]

1. 输入节点数和边数；
2. 依次输入节点信息，将其存储到节点数组Vex[]的data域中，将Vex[]的first域置空；
3. 依次输入每条边依附的两个节点，如果是网，则还需要输入该边的权值。

注意

• 如果是无向图，则输入a b ，查询节点a、b 在节点数组Vex[]中的存储下标i 、j ，创建一个新的邻接点s ，令s ->v =j ; s ->next=NULL；然后将节点s 插入第i 个节点的第1个邻接点之前（头插法）。在无向图中，从节点a 到节点b 有边，从节点b 到节点a 也有边，因此还需要创建一个新的邻接点s 2 ，令s 2 ->v =i ; s 2 ->next=NULL；然后将s 2 节点插入第j 个节点的第1个邻接点之前（头插法）。
• 如果是有向图，则输入a b ，查询节点a、b 在节点数组Vex[]中的存储下标i 、j ，创建一个新的邻接点s ，令s ->v =j ; s ->next=NULL；将节点s 插入第i 个节点的第1个邻接点之前（头插法）。
• 如果是无向网或有向网，则和无向图或有向图的处理方式一样，只是邻接点多了一个权值域

[完美图解]

一个有向图如下图所示，其邻接表的存储过程如下所述。

1. 输入节点数5和边数7，G .vexnum=5，G .edgenum=7。

2. 输入节点信息a b c d e 并将其存入节点表，存储结果如下图所示。
   

3. 依次输入每条边依附的两个节点。

• 输入a b ，处理结果：在Vex[]数组的data域中查找到节点a 、b的下标分别为0、1，创建一个新的邻接点s ，令s ->v =1; s ->next=NULL。将节点s 插入第0个节点的第1个邻接点之前（头插法）
  

• 输入a c ，处理结果：在Vex[]数组的data域中查找到节点a 、c的下标分别为0、2，创建一个新的邻接点s ，令s ->v=2; s ->next=NULL。将节点s 插入第0个节点的第1个邻接点之前（头插法）。
  

• 输入a e ，处理结果：在Vex[]数组的data域中查找到节点a 、e的下标分别为0、4，创建一个新的邻接点s ，令s ->v =4; s ->next=NULL。将节点s 插入第0个节点的第1个邻接点之前（头插法）。
  

• 输入b c ，处理结果：在Vex[]数组的data域中查找到节点b 、c的下标分别为1、2，创建一个新的邻接点s ，令s ->v =2; s ->next=NULL。将节点s 插入第1个节点的第1个邻接点之前（头插法）。
  

• 输入c d ，处理结果：在Vex[]数组的data域中查找到节点c 、d的下标分别为2、3，创建一个新的邻接点s ，令s ->v =3; s ->next=NULL。将节点s 插入第2个节点的第1个邻接点之前（头插法）。
  

• 输入c e ，处理结果：在Vex[]数组的data域中查找到c 、e 的下标分别为2、4，创建一个新的邻接点s ，令s ->v =4; s ->next=NULL。将节点s 插入第2个节点的第1个邻接点之前（头插法）。
  

• 输入d e ，处理结果：在Vex[]数组的data域中查找到节点d 、e的下标分别为3、4，创建一个新的邻接点s ，令s ->v =4; s ->next=NULL。将节点s 插入第3个节点的第1个邻接点之前（头插法）。
  

由于后输入的内容被插在了单链表的前面，因此若输入顺序不同，则建立的单链表也不同。

[算法代码]

void CreateALGraph(ALGraph &G){ //创建有向图的邻接表
	VexType u, v;
	cout << "请输入节点数和边数：" << endl;
	cin >> G.vexnum >> G.edgenum;
	cout << "请输入节点信息：" << endl;
	for(int i = 0 ; i < G.vexnum ; i ++){ //输入节点信息，将其存入节点信息数组
		cin >> G.Vex[i].data;
	}
	for(int i = 0 ; i < G.vexnum ; i ++){
		G.Vex[i].first = NULL;
	}
	cout << "请依次输入每条边的两个节点u ， v" << endl;
	while(G.edgenum --){
		cin >> u >> v;
		int i = locatevex(G , u); //查找节点u 的存储下标
		int j = locatevex(G , v); //查找节点v 的存储下标
		if(i != -1 && j != -1){
			insertedge(G , i , j); //插入该边，若无向图还需要插入一条边
		}
	}
}

void insertedge(ALGraph &G , int i ,int j){ //插入一条边(头插法)
	AdjNode *s;
	s = new AdjNode;
	s->v = j;
	s->next = G.Vex[i].first;
	G.Vex[i].first = s;
}

【4 邻接表的优缺点】

① 优点

• 便于增删节点。
• 便于访问所有邻接点。访问所有节点的邻接点，其时间复杂度为O (n +e )。
• 空间复杂度低。节点表占用n 个空间，无向图的邻接点表占用n+2e 个空间，有向图的邻接点表占用n +e 个空间，总体空间复杂度为O(n +e )。而邻接矩阵的空间复杂度为O (n2 )。因此，对于稀疏图，可采用邻接表存储；对于稠密图，可采用邻接矩阵存储。

② 缺点

• 不便于判断在两个节点之间是否有边。要判断在两个节点之间是否有边，需要遍历该节点后面的邻接点链表。
• 不便于计算各节点的度。在无向图邻接表中，节点的度为该节点后面单链表中的节点数；在有向图邻接表中，节点的出度为该节点后面单链表中的节点数，但不易于求入度；在有向图的逆邻接表中，节点的入度为该节点后面单链表中的节点数，但不易于求出度。

虽然以邻接表访问单条边的效率不高，但是访问同一节点的所有关联边时，仅需访问该节点后面的单链表，时间复杂度为该节点的度O (d(vi ))；而以邻接矩阵访问同一节点的所有关联边时，时间复杂度为O(n )。总体上，邻接表比邻接矩阵效率更高。