当前位置:   article > 正文

数据结构学习笔记——图的存储结构(邻接矩阵、邻接表、邻接多重表和十字链表)_邻接矩阵和邻接表

邻接矩阵和邻接表

前言

图的常用存储结构有邻接矩阵和邻接表,另外还有十字链表、邻接多重表等等。

一、邻接矩阵

图的邻接矩阵存储结构用于表示顶点之间的相邻关系,其中通过一个一维数组存储顶点,一个二维数组存储顶点之间的相邻关系,一个顶点数为n的图的邻接矩阵是n×n(n行n列),即一个方阵,用邻接矩阵方法来表示一个图需要n2个存储空间,它只与图中的顶点数有关,其空间复杂度为O(n2)。

(一)图的邻接矩阵表示

设图G=(V,E),若顶点是E(G)中的边,则用1标记,记为A[i][j]=1;若顶点不是E(G)中的边,则用0标记,记为A[i][j]=0

  • ✨通过邻接矩阵存储图时,其邻接矩阵是唯一的。

例如,下面是一个无向图:
在这里插入图片描述
该无向图的邻接矩阵为:
在这里插入图片描述

  • ✨对于一个无向图,其邻接矩阵的主对角线一定为零,另外无向完全图中,其邻接矩阵的主对角线为0,其余元素都为1,其任意两个顶点之间都有边连接。

例如,下面是一个无向完全图:
在这里插入图片描述
其邻接矩阵表示如下:
在这里插入图片描述
下面是一个有向图:
在这里插入图片描述
其邻接矩阵表示如下:
在这里插入图片描述

(二)图的邻接矩阵性质

  • ✨由于邻接矩阵是方阵,所以图的顶点数等于邻接矩阵的行或列的数目。

例如以下是一个图的邻接矩阵,由于该邻接矩阵是4×4,即该图的顶点数为4。

在这里插入图片描述

  • ✨对于一个含有n个顶点,e条边的无向图,其邻接矩阵中元素为零的个数为n2-2e。

例如,如下这个邻接矩阵,若它是无向图,求其共有多少条边。

在这里插入图片描述

可知该邻接矩阵是3×3,即该图的顶点数为3,n=3,又由于是无向图,其邻接矩阵中元素为零的个数为5,由n2-2e,即5=9-2e,解得e=2,故无向图中共有2条边。

  • ✨无向图的邻接矩阵一定是对称矩阵,关于对角线对称,且主对角线一定为零(只针对简单图),而有向图的邻接矩阵不一定是对称矩阵;另外,0若一个图的邻接矩阵是对称的,则它可以是无向图或有向图。
    在这里插入图片描述

由于无向图的邻接矩阵存在对称关系,其上三角和下三角的相同的,所以当在存储邻接矩阵时,除了对角线都为0以外,其实只需要存储上三角或下三角的数据,故只需要n(n-1)/2个存储空间。

只存储上三角或下三角的数据,即1+2+3+……+(n-1)=n(n-1)/2。

  • ✨对于无向图,顶点vi的度为其邻接矩阵中第i行(或第i列)的非零元素的个数;而有向图中,对于顶点i,邻接矩阵中第i行非零元素的个数和第i列非零元素的个数对应该顶点的出度OD(vi)和入度ID(vi),又由于有向图中度等于出度和入度之和,即顶点vi的度为其邻接矩阵中第i行和第i列的非零元素的个数之和
v i的度
出度
邻接矩阵的第i行非零元素个数
入度
邻接矩阵的第i列非零元素个数

若对于带权的图,即网,在有关度的运算时,只需将非零元素的个数替换成非∞元素的个数即可,例如对于无向图中,顶点vi的度为其邻接矩阵中第i行(或第i列)的非∞元素的个数。

例、设图的邻接矩阵A如下所示,求各顶点的度依次是_______。
在这里插入图片描述

首先,可知该邻接矩阵不对称,所以图为有向图,有向图的度为入度和出度之和,
所以各顶点的度为邻接矩阵中每行和每列之和,出度对应行,入度对应列,
即,V1=1+1+1=3,V2=1+1+1+1=4,V3=1+1=2,V4=1+1+1=3
即3,4,2,3。

  • ✨若邻接矩阵为对称矩阵,当图为有向图时,图的弧的数目等于邻接矩阵中非零元素的个数;当为无向图,则图的边数等于邻接矩阵中非零元素的一半。

(三)网的邻接矩阵表示

  • 带权的图称为网,设图G=(V,E),若顶点vi与顶点vj之间有边,则记为A[i][j]=Wij,即对应邻接矩阵对应项中存放边的权值;若顶点vi与顶点vj不相连,两个顶点间不存在边,则用标记,记为A[i][j]=∞,这里的∞是一个大于所有边的权值。

例如,下面是一个无向网,带有权值:
在这里插入图片描述
其邻接矩阵表示如下:
在这里插入图片描述
例如,下面是一个有向网,带有权值:
在这里插入图片描述
其邻接矩阵表示如下:
在这里插入图片描述

二、邻接矩阵存储图代码

以下代码可用于求有向图或无向图的邻接矩阵,只需修改其中一句代码(详细见图的邻接矩阵建立)。

(一)图的邻接矩阵定义

可自行定义MAXSIZE,即顶点数目的最大值,顶点的数据类型为char类型,边的数据类型为int类型,如下代码:

#define MAXSIZE 100
typedef struct {
	int n,e;					//图的顶点数目、图的边数目
	char V[MAXSIZE];			//一维数组,存储顶点
	int E[MAXSIZE][MAXSIZE];	//二维数组,边的邻接矩阵
} Graph;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

(二)初始化邻接矩阵

初始化邻接矩阵,将邻接矩阵中的所有元素都置为0,通过for循环嵌套完成,如下代码:

/*初始化邻接矩阵*/
void InitGraph(Graph *G) {
	int i,j;
	for(i=0; i<G->n; i++)
		for(j=0; j<G->n; j++)
			G->E[i][j]=0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

(三)图的邻接矩阵建立

针对无向图和有向图,由于无向图中边连接边的两个顶点与有向图中不同,所以只需对if条件语句进行修改。
对于无向图时:

for(k=0; k<G->e; k++) {
	scanf("%c",&X); 
	printf("建立第%d条边(以逗号隔开):",k+1);
	scanf("%c,%c",&ch1,&ch2);
	for(i=0; i<G->n; i++)
		for(j=0; j<G->n; j++)
			if(ch1==G->V[i]&&ch2==G->V[j]) {
				G->E[i][j]=1;
				G->E[j][i]=1;		/*对于有向图,可以去掉这行代码,而无向图需加上*/
			}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

对于有向图时,加上G->E[j][i]=1:

for(k=0; k<G->e; k++) {
	scanf("%c",&X); 
	printf("建立第%d条边(以逗号隔开):",k+1);
	scanf("%c,%c",&ch1,&ch2);
	for(i=0; i<G->n; i++)
		for(j=0; j<G->n; j++)
			if(ch1==G->V[i]&&ch2==G->V[j])
				G->E[i][j]=1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

完整代码如下:

/*图的邻接矩阵建立*/
void CreateGraph(Graph *G) {
	int i,j,k;
	char ch1,ch2,X;
	printf("请输入图的顶点数目:");
	scanf("%d",&G->n);
	printf("请输入图的边的数目:");
	scanf("%d",&G->e);
	printf("请输入各顶点的信息:\n");
	for(i=0; i<G->n; i++) {
		scanf("%c",&X); 
		printf("输入第%d个顶点:",i+1);
		scanf("%c",&(G->V[i]));
	}
	for(k=0; k<G->e; k++) {
		scanf("%c",&X); 
		printf("建立第%d条边(以逗号隔开):",k+1);
		scanf("%c,%c",&ch1,&ch2);
		for(i=0; i<G->n; i++)
			for(j=0; j<G->n; j++)
				if(ch1==G->V[i]&&ch2==G->V[j]) {
					G->E[i][j]=1;
					G->E[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

(四)输出邻接矩阵

/*输出邻接矩阵*/
void PrintGraph(Graph G) {
	int i,j;
	for(i=0; i<G.n; i++) {
		for(j=0; j<G.n; j++)
			printf("%d  ",G.E[i][j]);
		printf("\n");
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

例如,下面是个无向完全图,求其邻接矩阵。
在这里插入图片描述
可知该图有4个顶点,6条边,顶点信息分别为A、B、C、D,边分别为A,B、A,C、A,D、B,C、B,D、C,D。
代码如下:

#include <stdio.h>
#define MAXSIZE 100
typedef struct {
	int n,e;					//图的顶点、图的边
	char V[MAXSIZE];			//一维数组,存储顶点
	int E[MAXSIZE][MAXSIZE];	//二维数组,存储顶点之间关系
} Graph;

/*初始化邻接矩阵*/
void InitGraph(Graph *G) {
	int i,j;
	for(i=0; i<G->n; i++)
		for(j=0; j<G->n; j++)
			G->E[i][j]=0;
}

/*图的邻接矩阵建立*/
void CreateGraph(Graph *G) {
	int i,j,k;
	char ch1,ch2,X;
	printf("请输入图的顶点数目:");
	scanf("%d",&G->n);
	printf("请输入图的边的数目:");
	scanf("%d",&G->e);
	printf("请输入各顶点的信息:\n");
	for(i=0; i<G->n; i++) {
		scanf("%c",&X); 
		printf("输入第%d个顶点:",i+1);
		scanf("%c",&(G->V[i]));
	}
	for(k=0; k<G->e; k++) {
		scanf("%c",&X); 
		printf("建立第%d条边(以逗号隔开):",k+1);
		scanf("%c,%c",&ch1,&ch2);
		for(i=0; i<G->n; i++)
			for(j=0; j<G->n; j++)
				if(ch1==G->V[i]&&ch2==G->V[j]) {
					G->E[i][j]=1;
					G->E[j][i]=1;
				}
	}
}

/*输出邻接矩阵*/
void PrintGraph(Graph G) {
	int i,j;
	for(i=0; i<G.n; i++) {
		for(j=0; j<G.n; j++)
			printf("%d  ",G.E[i][j]);
		printf("\n");
	}
}

/*主函数*/
int main() {
	Graph G;
	InitGraph(&G);					//初始化邻接矩阵 
	CreateGraph(&G);				//建立邻接矩阵 
	printf("图的邻接矩阵为:\n");
	PrintGraph(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

运行结果如下:
在这里插入图片描述
例如,下面是个有向图,求其邻接矩阵。
在这里插入图片描述
可知该图有4个顶点,5条边,顶点信息分别为A、B、C、D,边分别为B,A、B,C、B,D、C,A、D,C。
代码如下:

#include <stdio.h>
#define MAXSIZE 100
typedef struct {
	int n,e;					//图的顶点、图的边
	char V[MAXSIZE];			//一维数组,存储顶点
	int E[MAXSIZE][MAXSIZE];	//二维数组,存储顶点之间关系
} Graph;

/*初始化邻接矩阵*/
void InitGraph(Graph *G) {
	int i,j;
	for(i=0; i<G->n; i++)
		for(j=0; j<G->n; j++)
			G->E[i][j]=0;
}

/*图的邻接矩阵建立*/
void CreateGraph(Graph *G) {
	int i,j,k;
	char ch1,ch2,X;
	printf("请输入图的顶点数目:");
	scanf("%d",&G->n);
	printf("请输入图的边的数目:");
	scanf("%d",&G->e);
	printf("请输入各顶点的信息:\n");
	for(i=0; i<G->n; i++) {
		scanf("%c",&X); 
		printf("输入第%d个顶点:",i+1);
		scanf("%c",&(G->V[i]));
	}
	for(k=0; k<G->e; k++) {
		scanf("%c",&X); 
		printf("建立第%d条边(以逗号隔开):",k+1);
		scanf("%c,%c",&ch1,&ch2);
		for(i=0; i<G->n; i++)
			for(j=0; j<G->n; j++)
				if(ch1==G->V[i]&&ch2==G->V[j]) {
					G->E[i][j]=1;
					//G->E[j][i]=1;
				}
	}
}

/*输出邻接矩阵*/
void PrintGraph(Graph G) {
	int i,j;
	for(i=0; i<G.n; i++) {
		for(j=0; j<G.n; j++)
			printf("%d  ",G.E[i][j]);
		printf("\n");
	}
}

/*主函数*/
int main() {
	Graph G;
	InitGraph(&G);					//初始化邻接矩阵 
	CreateGraph(&G);				//建立邻接矩阵 
	printf("图的邻接矩阵为:\n");
	PrintGraph(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

运行结果如下:
在这里插入图片描述

三、邻接表

(一)邻接表定义

邻接表方法采用顺序存储结构和链式存储结构来存储图,对于图中每个顶点vi,将所有邻接于vi的顶点连成一个单链表,即这个单链表就称为顶点vi的邻接表,另外还需将所有顶点的邻接表放进数组中,通过邻接表存储图所用的空间大小取决于图的顶点数和边的个数,顶点数n决定了顶点表的空间大小,边的个数决定了边表结点的空间大小。

  • 由于图G=(V,E),即需要在邻接表中定义两种结点结构,即顶点表和边表,另外若边上带有权值,则还需中边表上添加一个信息代表权值。顶点表中除了数据域用于存储顶点信息,还有指向第一条与其邻接顶点的指针域;边表中由邻接点域和指向下一条邻接边的指针域组成。

在这里插入图片描述

#define MAXSZIE 100
/*边表结点定义(不带权值的图的边表)*/
typedef struct Node {
	int adjvex;			//邻接点域
	struct Node *next;	//指向下一条邻接边的指针域
} EdgeNode;
/*顶点表结点定义*/
typedef struct VexNode {
	int data;				//数据域
	EdgeNode *firstedge;	//指向第一条邻接该顶点的指针域
} VHeadNode;
typedef struct {
	VHeadNode list[MAXSZIE];	//邻接表头结点数组
	int n,e;					//顶点数和边数
} List;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

例如,下面这个无向完全图:
在这里插入图片描述
为其编号如下:
在这里插入图片描述
邻接表表示的是顶点的出度邻接情况,即为每个顶点vi建立一个以vi为弧头的单链表,例如上图的邻接表表示如下:
在这里插入图片描述
例如,下面这个有向图:
在这里插入图片描述
为其编号如下:
在这里插入图片描述
其邻接表表示如下:
在这里插入图片描述

(二)逆邻接表

与邻接表相反,逆邻接表表示的是顶点的入度邻接情况,即为每个顶点vi建立一个以vi为弧头的单链表,如下:
在这里插入图片描述
该有向图的邻接表和逆邻接表表示如下:
在这里插入图片描述

(三)邻接表性质

  • ✨通过邻接表存储图时,其邻接表并不唯一,这与邻接矩阵相反,是由于单链表中各边结点的连接顺序是任意的。

在邻接表表示中,对于无向图,由于同一条边连着两个顶点,所以相当于每条边在邻接表存储中被存储了两遍,而对于有向图则没有,所以:

  • ✨在一个有n个顶点、e条边的无向图或有向图中,采用邻接表存储,无向图需要n个单链表表头指针和2e个边结点;而有向图需要n个单链表表头指针和e个边结点。

可以通过邻接表看出图中顶点的度,但无向图和有向图的度不一样,如下:

  • ✨对于无向图,顶点vi为第i个单链表的结点数;而对于有向图,顶点vi出度为第i个单链表的结点数,其入度为邻接表中所有单链表的邻接点域值为i的边结点个数。

对于要频繁计算有向图中顶点入度和出度的情况,可以另外建立一个逆邻接表,与有向图的邻接表相比,邻接表表示的是顶点的出度邻接情况,而相反,其逆邻接表表示的是顶点的入度邻接情况。

四、邻接矩阵与邻接表的对比

1、邻接矩阵

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/611024
推荐阅读
相关标签