树是一种特殊的图。树是有向无环图。

无向图是一种特殊的有向图。相当于a->b && b->a需要建立两个方向的联系。

下面考虑如何存储有向图

  • 邻接矩阵

    g[a][b]存储a->b（一般用0，1表示。0表示!a->b，1表示a->b。或者也可以用bool来表示）。如果有权重的话g[a][b]就存储权重（还是0表示!a->b，只要不是0就是a->b）。

    空间复杂度 $O(n^2)$ 所以使用较少。比较适合存储稠密图，否则空间浪费大。

  • 邻接表

    是一种特殊的单链表。每一个点都有一个单链表（这个单链表存这个点能够走到的点）。

邻接表存储

V表示点，e表示边。

存储结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct ANode {		// 边节点 
	int adjvex;				// 该边的邻接点编号
	struct ANode* nextarc;	// 指向下一条边的指针
	int weight;				// 该边的权重 
} ArcNode;					// 边节点的类型 

typedef struct {			// 头节点 
	infoType info			// 顶点的其他信息 
	ArcNode* firstarc;		// 指向第一个边的指针 
} VNode; 					// 邻接表头节点类型 

typedef struct {
	VNode adjlist[MaxV];	// 邻接表头结点数组
	int n, e;				// 图中的顶点数n, 边数e 
} AdjGraph;					// 完整的图邻接表类型

运算(利用邻接矩阵创建图)

利用邻接矩阵A创建图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void CreateAdj(AdjGraph*& G,int A[MaxV][MaxV], int n, int e) {
    ArcNode *p;
	G = (AdjGraph*)malloc(sizeof(AdjGraph));
	for (int i = 0; i < n; ++i)
		G->adjlist[i].firstarc = NULL;
	for (int i = 0; i < n; ++i) {
		for (int j = n-1; j >= 0; --j) {
			if (A[i][j] != 0 && A[i][j] != INF) {	// 存在一条边 
				// 申请内存 
				p = (ArcNode*)malloc(sizeof(ArcNode));
				// 存储信息 
				p->adjvex = j;
				p->weight = A[i][j];
				// 头插法插入节点 
				p->nextarc = G->adjlist[i].firstarc;
				G->adjlist[i].firstarc = p;
			}
		}
	}
	G->n = n;
	G->e = e; 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 图的遍历输出
void DispAdj(AdjGraph* G) {
	ArcNode* p;
	for (int i = 0; i < G->n; ++i) {
		p = G->adjlist[i].firstarc;
		cout << i << " :";
		// 遍历链表 
		while (p != NULL) {
			cout << p->adjvex << '[' << p->weight << ']->';
			p = p->nextarc; 
		} 
		cout << endl;
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 销毁图
void DestroyAdj(AdjGraph*& G) {
	ArcNode* pre, *p;
	for (int i = 0; i < G->n; ++i) {
		pre = G->adjlist[i].firstarc;
		if (pre != NULL) {
			p = pre->nextarc;
			while (p != NULL) {
				free(pre);
				pre = p;
				p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);
}

完整代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#define MaxV 100010 
#define INF INT_MAX

using namespace std;

typedef string infoType; 	// 存储信息的类型

typedef struct ANode {		// 边节点 
	int adjvex;				// 该边的邻接点编号
	struct ANode* nextarc;	// 指向下一条边的指针
	int weight;				// 该边的权重 
} ArcNode;					// 边节点的类型 

typedef struct {			// 头节点 
	infoType info;			// 顶点的其他信息 
	ArcNode* firstarc;		// 指向第一个边的指针 
} VNode; 					// 邻接表头节点类型 

typedef struct {
	VNode adjlist[MaxV];	// 邻接表头结点数组
	int n, e;				// 图中的顶点数n, 边数e 
} AdjGraph;					// 完整的图邻接表类型 

// 图的创建
void CreateAdj(AdjGraph*& G,int A[MaxV][MaxV], int n, int e) {
	ArcNode *p;
	G = (AdjGraph*)malloc(sizeof(AdjGraph));
	for (int i = 0; i < n; ++i)
		G->adjlist[i].firstarc = NULL;
	for (int i = 0; i < n; ++i) {
		for (int j = n-1; j >= 0; --j) {
			if (A[i][j] != 0 && A[i][j] != INF) {	// 存在一条边 
				// 申请内存 
				p = (ArcNode*)malloc(sizeof(ArcNode));
				// 存储信息 
				p->adjvex = j;
				p->weight = A[i][j];
				// 头插法插入节点 
				p->nextarc = G->adjlist[i].firstarc;
				G->adjlist[i].firstarc = p;
			}
		}
	}
	G->n = n;
	G->e = e; 
} 

// 图的遍历输出
void DispAdj(AdjGraph* G) {
	ArcNode* p;
	for (int i = 0; i < G->n; ++i) {
		p = G->adjlist[i].firstarc;
		cout << i << " :";
		// 遍历链表 
		while (p != NULL) {
			cout << p->adjvex << "[" << p->weight << "]->";
			p = p->nextarc; 
		} 
		cout << endl;
	}
} 

// 销毁图
void DestroyAdj(AdjGraph*& G) {
	ArcNode* pre, *p;
	for (int i = 0; i < G->n; ++i) {
		pre = G->adjlist[i].firstarc;
		if (pre != NULL) {
			p = pre->nextarc;
			while (p != NULL) {
				free(pre);
				pre = p;
				p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);
} 

int main () {
	int A[][MaxV] = {
		{0,2,1},		// <0,1>[2]  <0,2>[1]
		{2,0,3},		// <1,0>[2]  <1,2>[3]
		{1,3,0}			// <2,0>[1]  <2,1>[3]
	};
	AdjGraph* G;
	CreateAdj(G, A, 3, 3);
	DispAdj(G);
	DestroyAdj(G);
}

利用边关系构建图(添加边)

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#define MaxV 100010 
#define INF INT_MAX

using namespace std;

typedef string infoType; 	// 存储信息的类型

typedef struct ANode {		// 边节点 
	int adjvex;				// 该边的邻接点编号
	struct ANode* nextarc;	// 指向下一条边的指针
	int weight;				// 该边的权重 
} ArcNode;					// 边节点的类型 

typedef struct {			// 头节点 
	infoType info;			// 顶点的其他信息 
	ArcNode* firstarc;		// 指向第一个边的指针 
} VNode; 					// 邻接表头节点类型 

typedef struct {
	VNode adjlist[MaxV];	// 邻接表头结点数组
	int n, e;				// 图中的顶点数n, 边数e 
} AdjGraph;					// 完整的图邻接表类型 

// 添加有向边 
void AddVnode (AdjGraph*& G, int a, int b, int weight) { // 添加 (a, b) 
	// 声明并初始化点 
	ArcNode* p;
	p = (ArcNode*)malloc(sizeof(ArcNode));
	// 存储新边的信息 
	p->adjvex = b;			// 另一个点的编号 
	p->weight = weight;		// 到该点的权重 （边的权重） 
	// 添加到图中 
	p->nextarc = G->adjlist[a].firstarc;
	G->adjlist[a].firstarc = p;
	// 更新图中的最大节点的编号 
	if (a > G->n) {
		G->n = a;
	}
}

// 添加无向边 
void AddVnode2 (AdjGraph*& G, int a, int b, int weight) { // 添加 <a, b> 
	AddVnode(G, a, b, weight);
	AddVnode(G, b, a, weight);
}

// 图的遍历输出
void DispAdj(AdjGraph* G) {
	ArcNode* p;
	for (int i = 0; i <= G->n; ++i) {
		if (G->adjlist[i].firstarc == NULL)
			continue; 
		p = G->adjlist[i].firstarc;
		cout << i << " :";
		// 遍历链表 
		while (p != NULL) {
			cout << p->adjvex << "[" << p->weight << "]->";
			p = p->nextarc; 
		} 
		cout << endl;
	}
} 

int main () {
	// 声明并初始化 
	AdjGraph* G;
	G = (AdjGraph*)malloc(sizeof(AdjGraph));
	G->n = 0;
	// 添加双向边 
	AddVnode2(G, 1, 2, 3);
	AddVnode2(G, 2, 3, 2);
	AddVnode2(G, 2, 4, 2);
	AddVnode2(G, 2, 17, 3);
	// 遍历图 
	DispAdj(G);
}

适用于竞赛的邻接表

首先需要先会数组实现链表。数组实现链表

使用数组模拟实现链表，再用模拟的链表实现的邻接表就是链式向前星。

下面具体讲链式向前星