图的四种刻画方式

缘起

图是一种典型的非线性数据结构. 我们使用邻接矩阵或者邻接表两种模型对其进行刻画.

分析

第一种是最质朴，空间复杂度较高，但是时间复杂度较低的邻接矩阵法

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
#include "stdafx.h"
#include <iostream>

#define LOCAL
#define MAX_VERTEX_NUM 20 // 最多20个顶点
#define INF 0x3f3f3f3f // 网之间不通的含义
typedef enum{DG, UDG, DN, UDN} GRAPH_KIND; // 图类型，分别是 有向图（direction graph）、无向图、有向网、无向网

using namespace std;

struct Graph // 使用邻接矩阵刻画的图的数据结构，一眼望去， 显然的缺陷就是空间复杂度较高
{
	GRAPH_KIND kind; // 图的种类
	int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
	int vertexnum; // 顶点实际个数
	int edgenum; // 实际的边的数目
	Graph(GRAPH_KIND kind, int vertexnum, int edgenum)
	{
		this->kind = kind;
		this->vertexnum = vertexnum;
		this->edgenum = edgenum;
		int start, end, weight;
		switch(kind)
		{
		case DG: // 有向图
			memset(&this->matrix[0][0], 0, MAX_VERTEX_NUM*MAX_VERTEX_NUM*sizeof(int)); // 预设边都是不连通的
			puts("请输入边的起点和终点, 不同边换行, 起点在前, 终点在后");
			for (int i =0;i<edgenum; i++) 
			{
				scanf("%d %d", &start, &end);
				this->matrix[start][end] = 1;
			}
			break;
		case UDG: // 无向图
			memset(&this->matrix[0][0], 0, MAX_VERTEX_NUM*MAX_VERTEX_NUM*sizeof(int)); // 预设边都是不连通的
			puts("请输入边的起点和终点, 不同边换行");
			for (int i = 0; i<edgenum;i++)
			{
				scanf("%d %d", &start, &end);
				this->matrix[start][end] = this->matrix[end][start] = 1;
			}
			break;
		case DN: // 有向网(所谓网指的就是边带权重)
			memset(&this->matrix[0][0], 0x3f, MAX_VERTEX_NUM*MAX_VERTEX_NUM*sizeof(int)); // 初始化默认都不连通
			puts("输入各边及其权重, 起点在前, 终点在后");
			for (int i = 0; i<edgenum;i++)
			{
				scanf("%d %d %d", &start, &end, &weight);
				this->matrix[start][end] = weight;
			}
			break;
		case UDN: // 无向网
			memset(&this->matrix[0][0], 0x3f, MAX_VERTEX_NUM*MAX_VERTEX_NUM*sizeof(int)); // 初始化默认都不连通
			puts("输入各边及其权重");
			for (int i =0;i<edgenum;i++)
			{
				scanf("%d %d %d", &start, &end, &weight);
				this->matrix[start][end] = this->matrix[end][start] = weight;
			}
			break;
		}
	}
};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int vertexnum, edgenum;
	puts("输入顶点个数:\n");
	scanf("%d", &vertexnum);
	puts("输入边的条数:\n");
	scanf("%d", &edgenum);
	Graph(UDN, vertexnum, edgenum);
	return 0;
}

缺点是对于稀疏矩阵，空间浪费的太多.

第二种是邻接链表法.

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
#include "stdafx.h"
#include <iostream>

#define LOCAL
#define MAX_VERTEX_NUM 20 // 最多20个顶点
#define INF 0x3f3f3f3f // 网之间不通的含义
typedef enum{DG, UDG, DN, UDN} GRAPH_KIND; // 图类型，分别是 有向图（direction graph）、无向图、有向网、无向网

using namespace std;

struct Edge // 边
{
	int v; // 顶点（因为该边挂在某个顶点上，所以只需要给出额外另一个顶点即可）
	int w; // 边的权重
	Edge *next; // 下一条边
	Edge(int v,int w):v(v),w(w),next(NULL){}
};

struct Vertex // 顶点
{
	int v; // 顶点的标号
	Edge *first; // 挂在此顶点上的第一条边
};

struct Graph // 使用邻接表刻画图  所谓邻接表, 指的是 顶点数组, 而每个顶点的结构是一根边的链表, 即挂在顺序表上的链表
{
	Vertex adj[MAX_VERTEX_NUM]; // 邻接链表
	int vertexnum, edgenum; //  顶点数目、边数目
	Graph(int vertexnum, int edgenum):vertexnum(vertexnum),edgenum(edgenum)
	{
		for (int i = 0;i< vertexnum; i++)adj[i].v = i; // 初始化邻接链表
		puts("输入边的起点终点以及权值,空格分开,起点在前, 终点在后"); // 这里仅仅以有向网为例
		int start,end,weight;
		for (int i =0; i<edgenum;i++)
		{
			scanf("%d %d %d", &start, &end, &weight);
			Edge *e = new Edge(end, weight);
			e->next = adj[start].first; // 头插法
			adj[start].first = e; // 如果是有向网的话, 就要再跑到adj[end]这个链表上去加一条边
		}
	}
}; // 从上述图的初始化算法可以看出邻接链表的初始化时间复杂度是 O(n+e), 而邻接矩阵的初始化算法的时间复杂度是 O（n^2）


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int vertexnum, edgenum;
	puts("输入顶点个数和边的数目");
	scanf("%d %d", &vertexnum, &edgenum);
	Graph *g = new Graph(vertexnum, edgenum);

	return 0;
}

第三种是邻接多重表

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
#include "stdafx.h"
#include <iostream>

#define LOCAL
#define MAX_VERTEX_NUM 20
using namespace std;


struct Edge
{
	int i,j, w; // 边的两个顶点和边的权重
	Edge *nexti, *nextj; // 下一条边, 其中 nexti 是顶点i 邻接的下一条边, nextj是j顶点邻接的下一条边
	Edge(int i, int j, int w):i(i),j(j),w(w),nexti(NULL),nextj(NULL){}
};

typedef struct Vertex
{
	int v; // 顶点编号
	Edge *first; // 第一条边
} Adj[MAX_VERTEX_NUM];

// 邻接链表法解决的是邻接矩阵空间复杂度高的痛点. 而邻接链表法也并非完美,  比如对于无向图（网），我们增肌一条边(i,j)的话, 则要在两个节点(i和j)上新增两个一模一样的边节点, 因为节点都是new出来的, 所以很浪费空间
// 所以邻接多重表是用于处理无向图的
struct Graph
{
	int vertexnum, edgenum; // 顶点的个数、边的条数
	Adj adj; // 邻接矩阵
	Graph(int vtxnum, int edgnum):vertexnum(vtxnum),edgenum(edgnum)
	{
		for (int i = 0; i< vertexnum; i++) // 初始化顶点
		{
			adj[i].v = i;
			adj[i].first = NULL;
		}
		puts("输入各个边的顶点和权重\n");
		int start, end, weight;
		for (int i = 0; i<edgenum; i++)
		{
			scanf("%d %d %d", &start, &end, &weight);
			Edge *e  = new Edge(start, end, weight); // 对于无向图（网）而言，只需要新建一个节点，对于邻接链表法而言, 就需要新建两个节点了, 所以就无向图(网)而言, 空间复杂度比邻接链表法低, 但是时间复杂度都是O(n+e)
			// 头插法
			e->nexti = adj[start].first;
			adj[start].first = e;
			e->nextj = adj[end].first;
			adj[end].first = e;
		}
	}
};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	cout << "输入无向图的顶点的个数和边的条数"<<endl;
	int vertexnum, edgenum;
	scanf("%d %d", &vertexnum, &edgenum);
	Graph *g = new Graph(vertexnum,edgenum);

	return 0;
}

关于邻接多重表一种较好的acm实现，见 poj3255、hdu1874、hdu2544

第四种是十字链表法

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
#include "stdafx.h"
#include <iostream>

#define LOCAL
#define MAX_VERTEX_NUM 20
using namespace std;


// 十字链表的缘起是考虑有向图的入度的计算（无向图的入度=出度, 所以不是问题, 而邻接多重表是仅仅处理无向图的）. 我们知道邻接链表法
// 求出度是十分简单的, 只需要遍历链表即可. 但是求入度就比较惨了, 需要遍历图的所有节点,为了解决这个问题，我们显然需要建立一个入度的邻接链表法，但是这样就建立了两份图了，
// 十分麻烦，所以有没有能将入度邻接链表和出度邻接链表结合起来的图模型呢? 所以十字链表法就此诞生. 所以十字链表法委实十分适合有向图

struct Edge // 边
{
	int start, end, weight; // 起点、终点、权重
	Edge *nextIn, *nextOut; // 下一条入边、下一条出边
	Edge(int start, int end, int weight):start(start),end(end),weight(weight),nextIn(NULL),nextOut(NULL){}
};

struct Vertex // 节点
{
	int v, indeg, outdeg; // 顶点标号，入度、出度（既然要做，就做的彻底点, 干脆维护一下出度和入度好了）
	Edge *firstin, *firstout;
};

struct Graph
{
	int vertexnum, edgenum; // 实际顶点的个数、实际边的条数
	Vertex adj[MAX_VERTEX_NUM]; // 邻接链表
	Graph(int vertexnum, int edgenum):vertexnum(vertexnum),edgenum(edgenum)
	{
		for (int i = 0; i<vertexnum;i++)
		{
			adj[i].v = i;
			adj[i].indeg = adj[i].outdeg = 0;
			adj[i].firstin = adj[i].firstout = 0;
		}
		puts("输入边的起点，终点，权重，不同边换行");
		int start, end, weight;
		for (int i = 0; i<edgenum;i++)
		{
			scanf("%d %d %d", &start, &end, &weight);
			Edge *e = new Edge(start, end, weight);
			// 头插法
			e->nextOut = adj[start].firstout;
			adj[start].firstout = e;
			adj[start].outdeg++;
			e->nextIn = adj[end].firstin;
			adj[end].firstin = e;
			adj[end].indeg++;
		}
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int vertexnum, edgenum;
	puts("输入顶点个数和边的条数\n");
	scanf("%d %d", &vertexnum, &edgenum);
	Graph *g = new Graph(vertexnum, edgenum);
	return 0;
}