数据结构C++——图的邻接矩阵和邻接表

文章目录

数据结构C++——图的邻接矩阵和邻接表
- 一、图的介绍及概念
- 二、图的邻接矩阵
- - ①邻接矩阵的存储结构
  - ②邻接矩阵表示法创建无向网
  - ③LocateVex()函数的代码实现
  - ④打印邻接矩阵
  - ⑤测试的完整代码
  - ⑥邻接矩阵的优缺点分析
- 二、图的邻接表
- - ①邻接表的存储结构
  - ②邻接表表示法创建无向图
  - ③LocateVex()函数的代码实现
  - ④打印邻接表
  - ⑤测试的完整代码
  - ⑥邻接表的优缺点分析
- 三、总结

一、图的介绍及概念

(1) 无向完全图：对于无向图，若具有 n(n- 1)/2 条边，则称为无向完全图。
(2)有向完全图：对于有向图，若具有n(n- l)条弧，则称为有向完全图。
(3)邻接点：对于无向图 G, 如果图的边 (v, v’)属于E, 则称顶点 v 和 v’互为邻接点，即 v 和 v’相邻接。边 (v, v’)依附千顶点 v 和 v’, 或者说边 (v, v’)与顶点 v 和 v’相关联。
(4) 回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。
(5)简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
(6)连通、连通图和连通分量：在无向图 G 中，如果从顶点 v 到顶点 v’有路径，则称 v 和 v’是连通的。如果对于图中任意两个顶点都是连通的，则称 G 是连通图。所谓连通分量，指的是无向图中的极大连通子图
(7)强连通图和强连通分量：在有向图 G 中，如果对于每一对 V1， V2属于图, 从 V1到 V2 和从 V2到V1都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

二、图的邻接矩阵

①邻接矩阵的存储结构

图的邻接矩阵的存储结构

/*-------图的邻接矩阵存储表示-----*/
#define MVNum 100//最大顶点数
#define OK 1
#define ERROR 0
typedef int Status;
typedef string VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
bool visited[MVNum];//定义标志数组

typedef struct {
   VerTexType vexs[MVNum];//顶点表
   ArcType arcs[MVNum][MVNum];//邻接矩阵
   int vexnum, arcnum;//图的当前点数和边数
}AMGraph;

②邻接矩阵表示法创建无向网

采用邻接矩阵表示法创建无向网

采用邻接矩阵表示法创建无向网的算法思路：
1：输入总顶点数和总边数
2：通过for循环输入顶点信息
3：将邻接矩阵的边信息初始化为0
4：通过循环输入边依附的两个顶点，找到两个顶点在顶点表中的位置，返回其下标
5：在邻接表中将相应两顶点之间的边信息赋值为1

/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
	//采用邻接矩阵表示法，创建无向网
	int i = 0, j = 0, k = 0;
	cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
	for ( i = 0; i < G.vexnum; i++)//依次输入点的信息
		cin >> G.vexs[i];
	for ( i = 0; i < G.vexnum; i++)//初始化邻接矩阵
		for ( j = 0; j < G.vexnum; j++)
			G.arcs[i][j] = 0;
	for ( k = 0; k < G.arcnum; k++) {
		VerTexType v1, v2;//定义两个顶点v1,v2
		cin >> v1 >> v2 ;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
		G.arcs[i][j] = G.arcs[j][i] = 1;
	}
}

③LocateVex()函数的代码实现

LocateVex()函数的代码实现

LocateVex()函数代码实现思路：
1：利用for循环遍历顶点表
2：找到顶点表中顶点信息和形参相同的顶点，返回其下标i
3：若未找到此形参顶点，则返回-1

/*---------确定某顶点在G中的位置下标-----------*/
int LocateVex(AMGraph G, VerTexType u) {
	int i;
	for (int i = 0; i < G.vexnum; i++)
		if (u == G.vexs[i]) return i;
	return -1;
}

④打印邻接矩阵

打印邻接矩阵

打印邻接矩阵的算法思路：
     利用两层循环输出邻接矩阵

/*--------打印图的邻接矩阵-----------*/
void PrintfAMGraph(AMGraph G) {
	//将图的邻接矩阵输出在控制台上
	for (int i = 0; i < G.vexnum; i++) {
		cout << "v" << i + 1 << ":";
		for (int j = 0; j < G.vexnum; j++)
			cout << G.arcs[i][j] << " ";
		cout << endl;
	}
}

⑤测试的完整代码

完整代码

#include<iostream>
using namespace std;
/*-------图的邻接矩阵存储表示-----*/
#define MVNum 100//最大顶点数
#define OK 1
#define ERROR 0
typedef int Status;
typedef string VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型

bool visited[MVNum];//定义标志数组

typedef struct {
	VerTexType vexs[MVNum];//顶点表
	ArcType arcs[MVNum][MVNum];//邻接矩阵
	int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
/*---------确定某顶点在G中的位置下标-----------*/
int LocateVex(AMGraph G, VerTexType u) {
	int i;
	for (int i = 0; i < G.vexnum; i++)
		if (u == G.vexs[i]) return i;
	return -1;
}
/*--------打印图的邻接矩阵-----------*/
void PrintfAMGraph(AMGraph G) {
	//将图的邻接矩阵输出在控制台上
	for (int i = 0; i < G.vexnum; i++) {
		cout << "v" << i + 1 << ":";
		for (int j = 0; j < G.vexnum; j++)
			cout << G.arcs[i][j] << " ";
		cout << endl;
	}
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
	//采用邻接矩阵表示法，创建无向网
	int i = 0, j = 0, k = 0;
	cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
	for ( i = 0; i < G.vexnum; i++)//依次输入点的信息
		cin >> G.vexs[i];
	for ( i = 0; i < G.vexnum; i++)//初始化邻接矩阵
		for ( j = 0; j < G.vexnum; j++)
			G.arcs[i][j] = 0;
	for ( k = 0; k < G.arcnum; k++) {
		VerTexType v1, v2;//定义两个顶点v1,v2
		cin >> v1 >> v2 ;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
		G.arcs[i][j] = G.arcs[j][i] = 1;
	}
}
/*-----------主函数-----------*/
int main() {
	AMGraph G;
	CreateUDN(G);
	PrintfAMGraph(G);
	return 0;
}

测试结果

输入：
8 9
v1 v2 v3 v4 v5 v6 v7 v8
v1 v2
v1 v3
v2 v4
v2 v5
v3 v6
v3 v7
v4 v8
v5 v8
v6 v7

输出结果

输出：

在这里插入图片描述
输入数据创建的无向图：

⑥邻接矩阵的优缺点分析

(1)优点
①便于判断两个顶点之间是否有边，即根据A[z][j] = 0或1来判断。
②便于计算各个顶点的度。对于无向图，邻接矩阵第i行元素之和就是顶点i的度；对于有向图，第i行元素之和就是顶点 i 的出度，第i列元素之和就是顶点i的入度。
(2) 缺点
①不便于增加和删除顶点。
②不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为O(n²）
③空间复杂度高。如果是有向图，n个顶点需要n²个单元存储边。如果是无向图，因其邻接矩阵是对称的，所以对规模较大的邻接矩阵可以采用压缩存储的方法，仅存储下三角（或上三角）的元素，这样需要n(n-1)/2个单元即可。但无论以何种方式存储，邻接矩阵表示法的空间复杂度均为0(n²)这对于稀疏图而言尤其浪费空间。

--------------------------------一道华丽的分割线-----------------------------------

二、图的邻接表

①邻接表的存储结构

邻接表的存储结构

/*--------图的邻接表存储表示----------*/
#define MVNum 100//最大顶点数
#define OK 1
typedef int OtherInfo;
typedef string VerTexType;
typedef int Status;
typedef struct ArcNode {//边结点
	int adjvex;//该边所指向的顶点位置
	struct ArcNode* nextarc;//指向下一条边的指针
	OtherInfo info;//和边相关的信息
}ArcNode;
typedef struct VNode {//顶点信息
	VerTexType data;
	ArcNode* firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];
typedef struct {·
	AdjList vertices;
	int vexnum, arcnum;//图的当前顶点数和边数
}ALGraph;

②邻接表表示法创建无向图

算法思路

邻接表表示法创建无向图的算法思路：
1：输入总顶点数和总边数
2：输入各顶点，构造表头结点表，记得初始化顶点表的指针域为NULL
3：输入一条边依附的两个顶点，找到两个顶点在顶点表中的位置坐标
4：分别定义两个新的边结点指针，利用头插法将邻接点插入到相应的顶点表中

Status CreateUDG(ALGraph& G) {
	//采用邻接表表示法，创建无向图G
	cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
	for (int i = 0; i < G.vexnum; i++) {
		//输入各点，构造表头结点表
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL
	}
	for (int k = 0; k < G.arcnum; k++) {
		//输入各边，构造邻接表
		VerTexType v1, v2;
		cin >> v1 >> v2;//输入一条边依附的两个顶点
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点在G.vertices中的序号
		ArcNode* p1 = new ArcNode;//生成新的一个边结点*p1
		p1->adjvex = j;//邻接点序号为j
		p1->nextarc = G.vertices[i].firstarc;//采用头插法
		G.vertices[i].firstarc = p1;//将新结点*p1插入顶点vi的边表头部
		ArcNode* p2 = new ArcNode;//生成新的一个边结点*p2
		p2->adjvex = i;//邻接点序号为i
		p2->nextarc = G.vertices[j].firstarc;//采用头插法
		G.vertices[j].firstarc = p2;//将新结点*p2插入顶点vj的边表头部
	}
	return OK;
}

③LocateVex()函数的代码实现

LocateVex()函数代码实现

LocateVex()函数代码实现的思路：
1：从0开始遍历顶点表
2：若某顶点的数据域值与形参相等，则返回此时的i值（形参顶点的下标值）

/*-------------LocateVex()函数代码实现----------------*/
int LocateVex(ALGraph G,VerTexType v1) {//返回传入结点在图中的位置下标
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vertices[i].data == v1)
			return i;
	}
	return -1;
}

④打印邻接表

打印邻接表

将邻接表输出在控制台的算法思路
1：通过for循环输出顶点信息
2：生成一个边指针，边指针指向第一个边结点
3：通过while循环输出各个顶点的边结点信息

/*--------将邻接表输出在控制台上---------*/
void PrintfALGraph(ALGraph G) {
	for (int i = 0; i < G.vexnum; i++) {
		cout << G.vertices[i].data << "：";
		ArcNode* p = new ArcNode;//生成一个边指针
		p = G.vertices[i].firstarc;//边指针指向第一个边结点
		while (p!=NULL) {//当边指针不为空时，即指针未遍历完
			cout << p->adjvex << " ";
			p = p->nextarc;//边指针继续遍历邻接表
		}
		cout << endl;
	}
}

⑤测试的完整代码

完整代码

#include<iostream>
#include<string>
using namespace std;
/*--------图的邻接表存储表示----------*/
#define MVNum 100//最大顶点数
#define OK 1
typedef int OtherInfo;
typedef string VerTexType;
typedef int Status;
typedef struct ArcNode {//边结点
	int adjvex;//该边所指向的顶点位置
	struct ArcNode* nextarc;//指向下一条边的指针
	OtherInfo info;//和边相关的信息
}ArcNode;
typedef struct VNode {//顶点信息
	VerTexType data;
	ArcNode* firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];
typedef struct {
	AdjList vertices;
	int vexnum, arcnum;//图的当前顶点数和边数
}ALGraph;
int LocateVex(ALGraph G,VerTexType v1) {//返回传入结点在图中的位置下标
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vertices[i].data == v1)
			return i;
	}
	return -1;
}
Status CreateUDG(ALGraph& G) {
	//采用邻接表表示法，创建无向图G
	cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
	for (int i = 0; i < G.vexnum; i++) {
		//输入各点，构造表头结点表
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL
	}
	for (int k = 0; k < G.arcnum; k++) {
		//输入各边，构造邻接表
		VerTexType v1, v2;
		cin >> v1 >> v2;//输入一条边依附的两个顶点
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点在G.vertices中的序号
		ArcNode* p1 = new ArcNode;//生成新的一个边结点*p1
		p1->adjvex = j;//邻接点序号为j
		p1->nextarc = G.vertices[i].firstarc;//采用头插法
		G.vertices[i].firstarc = p1;//将新结点*p1插入顶点vi的边表头部
		ArcNode* p2 = new ArcNode;//生成新的一个边结点*p2
		p2->adjvex = i;//邻接点序号为i
		p2->nextarc = G.vertices[j].firstarc;//采用头插法
		G.vertices[j].firstarc = p2;//将新结点*p2插入顶点vj的边表头部
	}
	return OK;
}
/*--------将邻接表输出在控制台上---------*/
void PrintfALGraph(ALGraph G) {
	for (int i = 0; i < G.vexnum; i++) {
		cout << G.vertices[i].data << "：";
		ArcNode* p = new ArcNode;//生成一个边指针
		p = G.vertices[i].firstarc;//边指针指向第一个边结点
		while (p!=NULL) {//当边指针不为空时，即指针未遍历完
			cout << p->adjvex << " ";
			p = p->nextarc;//边指针继续遍历邻接表
		}
		cout << endl;
	}
}
/*----------主函数-----------*/
int main() {
	ALGraph G;
	CreateUDG(G);
	PrintfALGraph(G);
	return 0;
}

测试结果

输入：
5 6
v1 v2 v3 v4 v5
v1 v2
v1 v4
v3 v4
v2 v3
v3 v5
v2 v5

输出：

在这里插入图片描述
输入数据建立的无向图：

⑥邻接表的优缺点分析

(1) 优点
①便于增加和删除顶点。
②便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O(n+e)。
③空间效率高。对于一个具有n个顶点e条边的图G, 若G是无向图，则在其邻接表表示中有 n 个顶点表结点和 2e 个边表结点；若G是有向图，则在它的邻接表表示或逆邻接表表示中均有 n 个顶点表结点和e个边表结点。因此，邻接表或逆邻接表表示的空间复杂度为 O(n + e), 适合表示稀疏图。对于稠密图，考虑到邻接表中要附加链域，因此常采取邻接矩阵表示法。
(2) 缺点
①不便于判断顶点之间是否有边，要判定 V_i和v_j之间是否有边，就需扫描第i个边表，最坏情况下要耗费 O(n)时间。
②不便于计算有向图各个顶点的度。对于无向图，在邻接表表示中顶点V_i的度是第i个边表中的结点个数。在有向图的邻接表中，第 i 个边表上的结点个数是顶点 V_i的出度，但求 V_i的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易，而求顶点的出度较难。

三、总结

以上为笔者对于图的邻接矩阵和邻接表的一些见解，希望初学者都能有所收获，有技术不到位的地方，还望各位大佬指正。
同时，笔者的个人主页还有数据结构中其他部分的一些见解与分析，后续数据结构的相关知识还将陆续更新，欢迎大家访问且共同学习！