[数据结构与算法] 【数据结构】图的存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）及实现（C语言）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构】图的存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）及实现（C语言） -> 正文阅读

[数据结构与算法]【数据结构】图的存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）及实现（C语言）

1. 邻接矩阵表示法

1.1 图的邻接矩阵

图的邻接矩阵表示法（Adjacency Matrix）也称作数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。
有向图的邻接矩阵可以指示弧的方向；无向图的邻接矩阵没有方向，所以是对称矩阵；
稀疏图不适于用邻接矩阵来存储，会造成空间浪费。

1.2 创建有向网的邻接矩阵

# include<stdio.h>
# define MAX_VERTEX_NUM 20			//最多顶点个数
# define INFINITY 32768				//表示极大值，即∞

/*图的邻接矩阵表示法*/
typedef int AdjType;
typedef char VertexData;
typedef struct ArcNode {
	AdjType adj;							//无权图用1或0表示是否相邻，带权图则为权值类型
}ArcNode;
typedef struct {
	VertexData vertex[MAX_VERTEX_NUM];		//顶点向量
	ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
	int vexnum, arcnum;						//图的顶点数和弧数
}AdjMatrix;

/*采用邻接矩阵表示法创建有向网*/
/*求顶点位置*/
int LocateVertex(AdjMatrix* G, VertexData v) {
	int k;
	for (k = 0; k < G->vexnum; k++) {
		if (G->vertex[k] == v)
			break;
	}
	return k;
}

/*创建有向网*/
int CreateDN(AdjMatrix* G) {
	int i, j, k, weight;
	VertexData v1, v2;
	printf("输入图的顶点数和弧数：");			//输入图的顶点数和弧数
	scanf("%d%d", &G->vexnum, &G->arcnum);
	for (i = 0; i < G->vexnum; i++) {		//初始化邻接矩阵
		for (j = 0; j < G->vexnum; j++)
			G->arcs[i][j].adj = INFINITY;
	}
	printf("输入图的顶点：");
	for (i = 0; i < G->vexnum; i++)			//输入图的顶点
		scanf(" %c", &G->vertex[i]);
	for (k = 0; k < G->arcnum; k++) {
		printf("输入第%d条弧的两个顶点及权值：", k + 1);
		scanf(" %c %c %d", &v1, &v2, &weight);	//输入一条弧的两个顶点及权值
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		G->arcs[i][j].adj = weight;			//建立弧
	}
}

/*邻接矩阵的输出*/
void AdjMatrixDisplay(AdjMatrix* G) {
	printf("图的邻接矩阵输出：\n");
	int i, j;
	for (i = 0; i < G->vexnum; i++) {
		printf("\t%c", G->vertex[i]);
	}
	printf("\n");
	for (i = 0; i < G->vexnum; i++) {		//输出邻接矩阵
		printf("%c\t", G->vertex[i]);
		for (j = 0; j < G->vexnum; j++) {
			if (G->arcs[i][j].adj == INFINITY)
				printf("∞\t");
			else
				printf("%d\t", G->arcs[i][j].adj);
		}
		printf("\n");
	}
}

int main() {
	AdjMatrix G;
	CreateDN(&G);
	AdjMatrixDisplay(&G);
	return 0;
}

运行结果

2. 邻接表表示法

2.1 图的邻接表存储结构

邻接表（Adjacency List）表示法是图的一种链式存储结构，它只存储图中存在的边信息。在邻接表中，对图中的每一个顶点建立一个带头结点的边链表，每个边链表的头结点又构成一个表头结点表。这样，一个n个顶点的图的邻接表表示由表头结点与边表两部分构成。
邻接表结点结构 ① 表头结点表：由所有表头结点以顺序结构（向量）的形式存储，以便可以随机访问任一顶点的边链表。表头结点由两部分组成，其中数据域vexdata用于存储顶点的名或其它相关信息；链域firstarc用于指向链表中第一个顶点。
② 边表：由表示图中顶点间邻接关系的n个边链表组成。边链表的弧结点结构由三部分组成，邻接点域adjvex用于存放与顶点vi相邻接的顶点在图中的位置；链域nextarc用于指向与顶点vi相关联的下一条边或弧的结点；数据域info用于存放与边或弧相关的信息（如赋权图中每条边或弧的权值）。
图的邻接表

# define MAX_VERTEX_NUM 20					//最多顶点个数

/*图的邻接表表示法*/
typedef char VertexData;
//弧结点结构
typedef struct ArcNode {
	int adjvex;								//该弧指向顶点的位置
	struct ArcNode* nextarc;				//指向下一条弧的指针
	int info;								//与弧相关的信息
}ArcNode;
//表头结点结构
typedef struct VertexNode {
	VertexData data;						//顶点数据
	ArcNode* firstarc;						//指向该顶点的第一条弧的指针
}VertexNode;
//邻接表结构
typedef struct {
	VertexNode vertex[MAX_VERTEX_NUM];
	int vexnum, arcnum;						//图的顶点数和弧数
}AdjList;

2.2 创建有向图的邻接表

邻接表创建过程

/*采用邻接表表示法创建有向图*/
/*求顶点位置*/
int LocateVertex(AdjList* G, VertexData v) {
	int k;
	for (k = 0; k < G->vexnum; k++) {
		if (G->vertex[k].data == v)
			break;
	}
	return k + 1;
}

/*创建有向图*/
int CreateAdjList(AdjList* G) {
	int i, j, k;
	VertexData v1, v2;
	ArcNode* p;
	printf("输入图的顶点数和弧数：");			//输入图的顶点数和弧数
	scanf("%d%d", &G->vexnum, &G->arcnum);
	printf("输入图的顶点：");
	for (i = 0; i < G->vexnum; i++) {		//输入图的顶点，初始化顶点结点
		scanf(" %c", &(G->vertex[i].data));
		G->vertex[i].firstarc = NULL;
	}
	for (k = 0; k < G->arcnum; k++) {
		printf("输入第%d条弧的两个顶点：", k + 1);
		scanf(" %c %c", &v1, &v2);			//输入一条弧的两个顶点
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		p = (ArcNode*)malloc(sizeof(ArcNode));	//申请新弧结点
		p->adjvex = j;
		p->nextarc = G->vertex[i].firstarc;
		G->vertex[i].firstarc = p;
	}
}

3. 十字链表表示法

3.1 图的十字链表存储结构

十字链表（Orthogonal List）是有向图的另一种链式存储结构。有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，称为顶点结点。

data：用于存储与顶点有关的信息，如顶点的名字等。
firstin：用于指向以该顶点作为弧头的第一个弧顶点。
firstout：用于指向以该顶点作为弧尾的第一个弧顶点。

弧结点 tailvex：表示弧尾顶点在图中的位置。
headvex：表示弧头顶点在图中的位置。
hlink：指向与此弧的弧头相同的下一条弧。
tlink：指向与此弧的弧尾相同的下一条弧。
info：指向该弧的相关信息，如权值等。
图的十字链表

# define MAX_VERTEX_NUM 20					//最多顶点个数

/*十字链表表示法*/
typedef char VertexData;
//弧结点结构
typedef struct ArcNode {
	int tailvex, headvex;
	struct ArcNode* hlink, * tlink;
}ArcNode;
//顶点结构
typedef struct VertexNode {
	VertexData data;						//顶点信息
	ArcNode* firstin, * firstout;
}VertexNode;
//十字链表结构
typedef struct {
	VertexNode vertex[MAX_VERTEX_NUM];
	int vexnum, arcnum;						//图的顶点数和弧数
}OrthList;

3.2 创建有向图的十字链表

/*创建有向图的十字链表*/
/*求顶点位置*/
int LocateVertex(OrthList* G, VertexData v) {
	int k;
	for (k = 0; k < G->vexnum; k++) {
		if (G->vertex[k].data == v)
			break;
	}
	return k + 1;
}

/*创建有向图的十字链表*/
void CreateOrthList(OrthList* G) {
	int i, j, k;
	VertexData vt, vh;
	ArcNode* p;
	printf("输入图的顶点数和弧数：");
	scanf("%d%d", &G->vexnum, &G->arcnum);	//输入图的顶点数和弧数
	printf("输入图的顶点：");
	for (i = 0; i < G->vexnum; i++) {		//输入图的顶点，初始化顶点结点
		scanf(" %c", &(G->vertex[i].data));
		G->vertex[i].firstin = NULL;
		G->vertex[i].firstout = NULL;
	}
	for (k = 0; k < G->arcnum; k++) {
		printf("输入第%d条弧的弧尾和弧头：", k + 1);
		scanf(" %c %c", &vt, &vh);
		i = LocateVertex(G, vt);
		j = LocateVertex(G, vh);
		p = (ArcNode*)malloc(sizeof(ArcNode));	//申请新弧结点
		p->tailvex = i;
		p->headvex = j;
		p->tlink = G->vertex[i].firstout;
		G->vertex[i].firstout = p;
		p->hlink = G->vertex[j].firstin;
		G->vertex[j].firstin = p;
	}
}

4. 邻接多重表

4.1 邻接多重表的存储结构

邻接多重表（Adjacency Multi-list）是无向图的存储结构，它能够提供更为方便的边处理信息。
顶点结点结构 data：用于存储与顶点有关的信息，如顶点的名字。
firstedge：用于指向第一条依附于该顶点的边。
边结点结构 mark：标志域，用以标记该条边是否被搜索过。
ivex / jvex：为该边依附的两个顶点在图中的位置。
ilink：用于指向下一条依附于顶点ivex的边。
jlink：用于指向下一条依附于顶点jvex的边。
邻接多重表

# define MAX_VERTEX_NUM 20					//最多顶点个数

/*邻接多重表表示法*/
typedef char VertexData;
//边结点结构
typedef struct EdgeNode {
	int mark, ivex, jvex;
	struct EdgeNode* ilink, * jlink;
}EdgeNode;
//顶点结点结构
typedef struct {
	VertexData data;
	EdgeNode* firstedge;
}VertexNode;
//邻接多重表结构
typedef struct {
	VertexNode vertex[MAX_VERTEX_NUM];
	int vexnum, arcnum;						//图的顶点数和弧数
}AdjMultiList;

4.2 创建无向图的邻接多重表

/*创建无向图的邻接多重表*/
/*求顶点位置*/
int LocateVertex(AdjMultiList* G, VertexData v) {
	int k;
	for (k = 0; k < G->vexnum; k++) {
		if (G->vertex[k].data == v)
			break;
	}
	return k + 1;
}

/*创建无向图的邻接多重表*/
void CreateAdjMultiList(AdjMultiList* G) {
	int i, j, k;
	VertexData v1, v2;
	EdgeNode* p;
	printf("输入图的顶点数和弧数：");
	scanf("%d%d", &G->vexnum, &G->arcnum);	//输入图的顶点数和弧数
	printf("输入图的顶点：");
	for (i = 0; i < G->vexnum; i++) {		//输入图的顶点，初始化顶点结点
		scanf(" %c", &(G->vertex[i].data));
		G->vertex[i].firstedge = NULL;
	}
	for (k = 0; k < G->arcnum; k++) {
		printf("输入第%d条弧的两个顶点：", k + 1);
		scanf(" %c %c", &v1, &v2);			//输入一条弧的两个顶点
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->ivex = i;
		p->jvex = j;
		p->mark = 0;

		p->ilink = G->vertex[i].firstedge;
		p->jlink = G->vertex[j].firstedge;
		G->vertex[i].firstedge = p;
		G->vertex[j].firstedge = p;
	}
}