数据结构-邻接数组存储的图

发表于 分类于
  • 邻接数组存储的图的表示
  • 邻接数组存储的图的操作接口定义
  • 邻接数组存储的图的操作实现

邻接数组存储的图的表示

由于图的任意两个顶点之间都可能存在边（弧），因此在图的存储与表示中，关键是如何表示边（弧）集。 用邻接矩阵也就是一个二维数组存储图的边集，也即关系数组，用一个一维数组存储图的顶点，也即顶点数组。

邻接数组的存储结构类型定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 用于标记是否已访问 */
#define UNVISITED	0
#define VISITED		1

#define INFINITY INT_MAX	// 计算机中允许的最大整数值

typedef enum {DG, DN, UDG, UDN} GraphKind;	// 图的四种类型：有向图、有向带权图、无向图、无向带权图

/* 邻接数组类型 */
typedef struct {
	VexType * vexs; // 顶点数组
	int** arcs;	// 关系数组，无权图用0或1表示是否相邻，带权图则为权值或INFINITY
	int n;		// 顶点数
	int e; 		// 边（弧）数
	GraphKind kind;	// 图的类型
	int * tags;	// 标志数组，用于标记顶点访问与否
}MGraph;

/* 边（弧）信息 */
typedef struct {
	VexType v, w; // 边（弧）端点
	int info; // 对于带权图为权值
}ArcInfo;

本文中预定义的说明

预定义常量和类型

1
2
3
4
5
6
7
8
//函数结果状态代码
#define TRUE      1
#define FALSE     0
#define OK        1
#define ERROR     0
#define OVERFLOW -1

typedef int Status; // 用作函数值类型，表示函数结果状态

数据结构（存储结构）的表示

数据结构的表示用类型定义(typedef)描述。数据元素类型约定为ElemType，读者在使用该数据类型时自行定义，如int、char等简单类型。

扩展引用调用

为了便于算法描述，我们使用了 C++ 语言中的引用调用参数传递方式。

邻接数组存储的图的操作接口定义

图G的顶点v在顶点数组中的下标k称为k在G中的位序，也称v为G的 第k顶点， 简称 k顶点。基于邻接数组的图的接口定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 初始化含n个顶点且无边的kind类的图G
Status InitGraph_M(MGraph &G, GraphKind kind, VexType *vexs, int n);
// 创建n个顶点和e条边的kind类的图G，vexs为顶点信息，arcs为边信息
Status CreateGraph_M(MGraph &G, GraphKind kind, VexType *vexs, int n, ArcInfo *arcs, int e);
// 销毁图G
Status DestroyGraph_M(MGraph &G);
// 查找顶点v在图G中的位序
int LocateVex_M(MGraph G, VexType v);
// 取图G的k顶点的值到w
Status GetVex_M(MGraph G, int k, VexType &w);
// 对图G的k顶点赋值w
Status PutVex_M(MGraph &G, int k, VexType w);
// 求图G中k顶点的第一个邻接顶点位序
int FirstAdjVex_M(MGraph G, int k);
// m顶点为k顶点的邻接顶点，求图G中k顶点相对于m顶点的下一个邻接顶点的位序
int NextAdjVex_M(MGraph G, int k, int m);
// 在图G中增加k顶点到m顶点的边或弧，若为带权图，info为权值，否则为1
Status AddArc_M(MGraph &G, int k, int m, int info);
// 在图G中删除k顶点到m顶点的边或弧
Status RemoveArc_M(MGraph &G, int k, int m);
// 深度优先遍历图G
Status DfsTraverse_M(MGraph G, Status(* visit)(int));
// 广度优先遍历图G
Status BFSTraverse_M(MGraph G, Status(*visit)(int));

邻接数组存储的图的操作实现

初始化图

初始化图的过程如下： 1. 按顶点数分配顶点、边集和标志3个数组空间； 2. 将顶点依次存入顶点数组； 3. 初始化标志数组和关系数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Status InitGraph_M(MGraph &G, GraphKind kind, VexType *vexs, int n)
{
	int i, j, info;

	if (n < 0 || (n > 0 && NULL == vexs))
		return ERROR;

	/*根据图的类型赋权值*/
	if (DG == kind || UDG == kind) 		// 无权图
		info  = 0;
	else if (DN == kind || UDN == kind) // 有权图
		info = INFINITY;
	else
		return ERROR;

	G.n = n;  // 顶点数
	G.e = 0;  // 边数

	/*若为空图，则已初始化完成*/
	if (n == 0)
		return OK;

	G.vexs = (VexType*)malloc(n * sizeof(VexType));
	if (NULL == G.vexs)
		return OVERFLOW;

	/*建立顶点数组*/
	for (i = 0; i < G.n; i++)
		G.vexs[i] = vexs[i];

	/*分配关系数组的指针数组*/
	G.arcs = (int**)malloc(n * sizeof(int*));
	if (NULL == G.arcs)
		return OVERFLOW;

	/*分配关系数组的指针数组指向的数组*/
	for (i = 0; i < n; i++) {
		G.arcs[i] = (int*)malloc(n * sizeof(int));
		if (NULL == G.arcs[i])
			return OVERFLOW;
	}

	/*分配标志数组*/
	G.tags = (int*)malloc(n * sizeof(int));
	if (NULL == G.tags)
		return OVERFLOW;

	/*初始化标志数组和关系数组*/
	for (i = 0; i < n; i++) {
		G.tags[i] = UNVISITED;
		for (j = 0; j < n; j++)
			G.arcs[i][j] = info;
	}
	return OK;
}

创建图

在图已初始化的情况下根据图的类型和边关系数组创建图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status CreateGraph_M(MGraph &G, GraphKind kind, VexType *vexs, int n, ArcInfo *arcs, int e)
{
	if (n < 0 || e < 0 || (n > 0 && NULL == vexs) || (e > 0 && NULL == arcs))
	       return ERROR;

	G.kind = kind; // 图的类型
	switch (G.kind) {
		case UDG : return CreateUDG_M(G, vexs, n, arcs, e);	// 创建无向无权图
		case DG : return CreateDG_M(G, vexs, n, arcs, e);	// 创建有向无权图
		case UDN : return CreateUDN_M(G, vexs, n, arcs, e);	// 创建无向带权图
		case DN : return CreateDN_M(G, vexs, n, arcs, e);   	// 创建有向带权图
		default:  return ERROR;
	}

	return OK;
}

创建无向无权图

对每条边分别求得顶点v和w在顶点数组中的下标i和j，然后置G.arcs[i][j]和G.arcs[j][i]的值为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Status CreateUDG_M(MGraph &G, VexType *vexs, int n, ArcInfo *arcs, int e)
{
	int i, j, k;
	VexType v, w;

	/*初始化*/
	if (OK != InitGraph_M(G, G.kind, vexs, n))
		return ERROR;

	G.e = e; // 边数

	for (k = 0; k < G.e; k++) {
		/*读入边(v,w)*/
		v = arcs[k].v;
		w = arcs[k].w;

		/*确定v和w在顶点数组中的位序i和j*/
		i = LocateVex_M(G, v);
		j = LocateVex_M(G, w);

		if (i < 0 || j <0)
			return ERROR;
		G.arcs[i][j] = G.arcs[j][i] = 1;	// 对关系数组赋值
	}
	return OK;
}

创建有向无权图

对每条边分别求得顶点v和w在顶点数组中的下标i和j，然后置G.arcs[i][j]的值为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Status CreateDG_M(MGraph &G, VexType *vexs, int n, ArcInfo *arcs, int e)
{
	int i, j, k;
	VexType v, w;

	/*初始化*/
	if (OK != InitGraph_M(G, G.kind, vexs, n))
		return ERROR;

	G.e = e; // 边数

	for (k = 0; k < G.e; k++) {
		/*读入边(v,w)*/
		v = arcs[k].v;
		w = arcs[k].w;

		/*确定v和w在顶点数组中的位序i和j*/
		i = LocateVex_M(G, v);
		j = LocateVex_M(G, w);

		if (i < 0 || j < 0)
			return ERROR;
		G.arcs[i][j] = 1;	// 对关系数组赋值
	}
	return OK;
}

无向带权图

对每条边分别求得顶点v和w在顶点数组中的下标i和j，然后置G.arcs[i][j]和G.arcs[j][i]的值为权值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Status CreateUDN_M(MGraph &G, VexType *vexs, int n, ArcInfo *arcs, int e)
{
	int i, j, k;
	VexType v, w;

	/*初始化*/
	if (OK != InitGraph_M(G, G.kind, vexs, n))
		return ERROR;

	G.e = e; // 边数

	for (k = 0; k < G.e; k++) {
		/*读入边(v,w)*/
		v = arcs[k].v;
		w = arcs[k].w;

		/*确定v和w在顶点数组中的位序i和j*/
		i = LocateVex_M(G, v);
		j = LocateVex_M(G, w);

		if (i < 0 || j <0)
			return ERROR;
		G.arcs[i][j] = G.arcs[j][i] = arcs[k].info;	// 对关系数组赋值
	}
	return OK;
}

创建有向带权图

对每条边分别求得顶点v和w在顶点数组中的下标i和j，然后置G.arcs[i][j]的值为权值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Status CreateDN_M(MGraph &G, VexType *vexs, int n, ArcInfo *arcs, int e)
{
	int i, j, k;
	VexType v, w;

	/*初始化*/
	if (OK != InitGraph_M(G, G.kind, vexs, n))
		return ERROR;

	G.e = e; // 边数

	for (k = 0; k < G.e; k++) {
		/*读入边(v,w)*/
		v = arcs[k].v;
		w = arcs[k].w;

		/*确定v和w在顶点数组中的位序i和j*/
		i = LocateVex_M(G, v);
		j = LocateVex_M(G, w);

		if (i < 0 || j <0)
			return ERROR;
		G.arcs[i][j] = arcs[k].info;	// 对关系数组赋值
	}
	return OK;
}

销毁图

需要销毁顶点数组，指向关系数组的指针数组，关系数组，标志数组。

1
2
3
4
5
6
7
8
9
void DestroyGraph_M(MGraph &G)
{
	int i;
	for (i = 0; i < G.n; i++)
		free(G.arcs[i]);
	free(G.arcs);
	free(G.vexs);
	free(G.tags);
}

查找顶点位序

1
2
3
4
5
6
7
8
9
10
int LocateVex_M(MGraph G, VexType v)
{
	int i;

	for (i = 0; i < G.n; i++)
		if (G.vexs[i] == v)
			return i;

	return OVERFLOW;
}

取顶点值

1
2
3
4
5
6
7
8
Status GetVex_M(MGraph G, int k, VexType &w)
{
	if (G.n <= 0 || k > G.n || k < 0)
		return ERROR;
	w = G.vexs[k];

	return OK;
}

置顶点值

1
2
3
4
5
6
7
8
Status PutVex_M(MGraph &G, int k, VexType w)
{
	if (G.n <= 0 || k > G.n || k < 0)
		return ERROR;
	G.vexs[k] = w;

	return OK;
}

求k顶点第一个邻接顶点

对于无权图，查找关系数组中的第k行第一个非零元素列号； 对于带权图，查找关系数组中的第k行第一个非\(\infty\)元素列号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int FirstAdjVex_M(MGraph G, int k)
{
	int i;
	if (k < 0 || k >= G.n)
		return ERROR;

	for (i = 0; i < G.n; i++) {
		if ((G.kind == UDG || G.kind == DG) && G.arcs[k][i] != 0)
			return i;
		else if ((G.kind == UDN || G.kind == DN) && G.arcs[k][i] != INFINITY)
			return i;
	}
	return OVERFLOW;
}

求k顶点某邻接顶点的下一个邻接顶点

将上一个操作的从第0列开始查找改为从第m+1列开始查找即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int NextAdjVex_M(MGraph G, int k, int m)
{
	int i;

	if (G.n <= 0)
		return ERROR;

	for (i = m + 1; i < G.n; i++) {
		if ((G.kind == UDG || G.kind == DG) && G.arcs[k][i] != 0)
			return i;
		else if ((G.kind == UDN || G.kind == DN) && G.arcs[k][i] != INFINITY)
			return i;
	}
	return OVERFLOW;
}

增加边或弧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Status AddArc_M(MGraph &G, int k, int m, int info)
{
	if (k < 0 || k > G.n || m < 0 || m > G.n)
		return ERROR;

	switch (G.kind) {
		case UDG : // 无向无权图
			if (G.arcs[k][m] != 0 || G.arcs[m][k] != 0) // 边已存在
				return ERROR;
			else
				G.arcs[k][m] = G.arcs[m][k] = info;
			break;
		case DG : // 有向无权图
			if (G.arcs[k][m] != 0)
				return ERROR;
			else
				G.arcs[k][m] = info;
			break;
		case UDN : // 无向带权图
			if (G.arcs[k][m] != INFINITY || G.arcs[m][k] != INFINITY)
				return ERROR;
			else
				G.arcs[k][m] = G.arcs[m][k] = info;
			break;
		case DN : // 有向带权图
			if (G.arcs[k][m] != INFINITY)
				return ERROR;
			else
				G.arcs[k][m] = info;
			break;
		deault :
			return ERROR;
	}
	return OK;
}

删除边或弧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Status RemoveArc_M(MGraph &G, int k, int m)
{
	if (k < 0 || k > G.n || m < 0 || m > G.n)
		return ERROR;

	switch (G.kind) {
		case UDG : // 无向无权图
			if (G.arcs[k][m] == 0 || G.arcs[m][k] == 0) // 边已存在
				return ERROR;
			else
				G.arcs[k][m] = G.arcs[m][k] = 0;
			break;
		case DG : // 有向无权图
			if (G.arcs[k][m] == 0)
				return ERROR;
			else
				G.arcs[k][m] = 0;
			break;
		case UDN : // 无向带权图
			if (G.arcs[k][m] == INFINITY || G.arcs[m][k] == INFINITY)
				return ERROR;
			else
				G.arcs[k][m] = G.arcs[m][k] = INFINITY;
			break;
		case DN : // 有向带权图
			if (G.arcs[k][m] == INFINITY)
				return ERROR;
			else
				G.arcs[k][m] = INFINITY;
			break;
		deault :
			return ERROR;
	}
	return OK;
}

深度优先遍历

对于连通图： 1. 从指定顶点\(v\)出发，先访问该顶点； 2. 对\(v\)顶点的所有邻接顶点\(w_i\)依次检查； 3. 若\(w_i\)未被访问，则以\(w_i\)为新起点递归进行深度优先遍历。

对于非连通图，这样的过程仅能访问到开始顶点所在的连通分量，故需要依次检查图中的所有顶点，若未访问，则以其为新起点进行深度优先遍历，直到所有顶点都被访问为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status DFS_M(MGraph G, int k, Status (*visit)(int))
{
	int i;

	if (ERROR == visit(k))
		return ERROR;

	G.tags[k] = VISITED;

	for (i = FirstAdjVex_M(G, k); i >= 0; i = NextAdjVex_M(G, k, i)) {
		if (UNVISITED == G.tags[i]) {
			if (ERROR == DFS_M(G, i, visit))
					return ERROR;
		}
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status DFSTraverse_M(MGraph G, Status (*visit)(int))
{
	int i;

	/*初始化标志数组*/
	for (i = 0; i < G.n; i++)
		G.tags[i] = UNVISITED;

	for (i = 0; i < G.n; i++) {
		if (UNVISITED == G.tags[i])
			if (ERROR == DFS_M(G, i, visit))
				return ERROR;
	}

	return OK;
}

广度优先遍历图

  1. 将所有顶点的访问标志初始化为UNVISITED；
  2. 依次检查所有顶点，若未被访问过，则：
    • 访问该顶点，入队；
    • 队列非空，队头元素出队，判断其所有邻接顶点是否被访问过；
    • 若未被访问过，访问该顶点，入队；
    • 重复以上操作直至队列为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Status BFSTraverse_M(MGraph G, Status (*visit)(int))
{
	int i, j, k;
	SqQueue Q;

	InitQueue_Sq(Q, G.n);

	for (i = 0; i < G.n; i++)
		G.tags[i] = UNVISITED;

	for (i = 0; i < G.n; i++) {
		if (UNVISITED == G.tags[i]) {
			if (ERROR == visit(i))
				return ERROR;
			G.tags[i] = VISITED;
			EnQueue_Sq(Q, i);
			while (OK == DeQueue_Sq(Q, k)) {
				for (j = FirstAdjVex_M(G, k); j >= 0; j = NextAdjVex_M(G, k, j)) {
					if (UNVISITED == G.tags[j]) {
						if (ERROR == visit(j))
							return ERROR;
						G.tags[j] = VISITED;
						EnQueue_Sq(Q, j);
					}
				}
			}
		}
	}
}

参考资料

  • 《数据结构》（高教版，吴伟民，李小妹）