图的存储(邻接矩阵,邻接表,十字链表)

发布于:2023-01-20 ⋅ 阅读:(15) ⋅ 点赞:(0) ⋅ 评论:(0)

1.邻接矩阵

(1)基本思想

用一个一维数组存储图中顶点的信息(可以是int,char,自定义的结构体,用来储存图顶点的信息);用一个二维数组(称为邻接矩阵)存储图中各顶点之间的邻接关系

(2)邻接矩阵的构建

1.无向

在邻接矩阵中,若两个顶点之间连通,则赋值1,否则赋值0;根据无向图的性质,则无向图的邻接矩阵一定主对角线为0且一定是对称矩阵,如下图(图片来自懒猫老师《数据结构》相关课程)

顶点的度:该顶点行或列的值和

两顶点间连接:arc[i][j]是否为1值

顶点的邻接点:遍历行,寻找arc[i][j]==1的点

2.有向图

 不同于无向图,在有向图中对于一个顶点来说,例如a-->b,这时才将a行中b的下标赋值为1

 

顶点的出度:该顶点行的值和

顶点的入度:该顶点列的值和

两顶点间连接:arc[i][j]是否为1值

顶点的邻接点:遍历行,寻找arc[i][j]==1的点

3.网图

网图在有向图的基础上,将原本赋值为1的结点赋值为该边的权值,并且矩阵对角线赋值为0,其他值赋为无穷

(3)代码实现

这里以无向图为例,其他图可对应上面进行修改;分为两个包,邻接矩阵.h包和测试.c包,合并即为完整代码

1.图_邻接矩阵.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX 10//最大的顶点个数
typedef int DataType;

//以下是无向图的定义
void MGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum, int arcNum) { //初始化构造图(邻接矩阵法)
	printf("请逐个输入顶点的内容:");
	DataType x;
	DataType vi, vj; //构建邻接矩阵时,一条边的两个结点编号
	for (int i = 0; i < vertexNum; i++) { //顶点数组赋值
		scanf("%d", &x);
		vertex[i] = x;
	}
	for (int i = 0; i < vertexNum; i++) //初始化邻接矩阵
		for (int j = 0; j < vertexNum; j++)
			arc[i][j] = 0;
	int count = 1;
	for (int i = 0; i < arcNum; i++) { //依次输入每一条边
		printf("请输入第%d条边依附的两个顶点的编号:", count++);
		scanf("%d %d", &vi, &vj); //输入该边依附的顶点的编号
		arc[vi][vj] = 1; //置有边标志
		arc[vj][vi] = 1;
	}

}

void printMGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum) { //输出
	printf("vertex:");
	for (int i = 0; i < vertexNum; i++) {
		printf("%d ", vertex[i]);
	}
	printf("\n");
	printf("arc:\n");
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++) {
			if (j == vertexNum - 1)
				printf("%d\n", arc[i][j]);
			else
				printf("%d ", arc[i][j]);
		}
	}

}

int isLinked(int arc[][MAX_VERTEX], int i, int j) { //两顶点i,j是否有边相连,1是相连,0是不相连
	if (arc[i][j] == 1)
		return 1;
	else
		return 0;
}

int nodeDepth(int arc[][MAX_VERTEX], int index, int vertexNum) { //任意一顶点的度
	//无向图任意遍历行\列求和
	int count = 0;
	for (int i = 0; i < vertexNum; i++) {
		if (arc[index][i] == 1)
			count++;
	}
	return count;
}

2. 图的测试_邻接矩阵.c

#include "图_邻接矩阵.h"

main() {
	DataType vertex[MAX_VERTEX];//储存所有的顶点
	int arc[MAX_VERTEX][MAX_VERTEX];//邻接矩阵,结点间的连通关系
	int vertexNum, arcNum; //结点个数,边的个数
	printf("输入顶点个数:");
	scanf("%d", &vertexNum);
	printf("输入边个数:");
	scanf("%d", &arcNum);
	MGraph(vertex, arc, vertexNum, arcNum);
	printMGraph(vertex, arc, vertexNum);
	printf("测试判断两顶点是否相连,请输入两个顶点下标:");
	int i, j;
	scanf("%d %d", &i, &j);
	if (isLinked(arc, i, j) == 1)
		printf("相连!\n");
	else
		printf("不相连!\n");
	printf("测试求顶点的度,请输入一个顶点下标:");
	int index;
	scanf("%d", &index);
	printf("该顶点的度为:%d", nodeDepth(arc, index, vertexNum));

}

(4)输出测试

测试用例:

输出:

 2.邻接表

 (1)基本思想

建立一个一维数组,一维数组中的元素结构定义为两部分,一部分储存顶点的的信息,一部分储存链表的头指针。而每一个链表的头指针都指向一个链表,链表里储存的是该顶点所连接的点信息。

一维数组称为顶点表,每一个数组元素指向的链表称为边表

(2)邻接表的构建

1.数据结构

typedef struct ArcNode { /*边表结点*/
	int adjvex;//边表数据域,即下标
	struct ArcNode *next; //指针域
} ArcNode;

typedef struct VertexNode { /*顶点表结点*/
	DataType vertex;//顶点的数据
	ArcNode *firstEdge; //指向储存该顶点所连接所有结点的边表
} VertexNode;

这里的边表链表的构建使用的是头插法 ,详见最下面的完整代码

2.无向图

顶点的度:遍历顶点表找到顶点,遍历顶点的链表,求结点个数

两顶点间连接:遍历顶点表找到顶点,遍历顶点的链表,求是否存在另一个结点

3.有向图

顶点的出度:遍历顶点表找到顶点,遍历顶点的链表,求结点个数

顶点的入度:遍历顶点表中其他每个顶点,并遍历其他每个顶点的链表,求该顶点出现的次数

邻接点:遍历顶点表找到顶点,遍历顶点的链表,即为邻接点

4.网图

在有向图基础上添加了权值的存储

(3)代码实现

 这里以有向图为例,其他图可对应上面进行修改;分为两个包,邻接表.h包和测试.c包,合并即为完整代码

1.图_邻接表.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX 10//最大的顶点个数
typedef int DataType;

typedef struct ArcNode { /*边表结点*/
	int adjvex;//边表数据域,即下标
	struct ArcNode *next; //指针域
} ArcNode;

typedef struct VertexNode { /*顶点表结点*/
	DataType vertex;//顶点的数据
	ArcNode *firstEdge; //指向储存该顶点所连接所有结点的边表
} VertexNode;
void initVertex(DataType *, int);

//以下是有向图的定义
void ALGraph(DataType *vertex, VertexNode *adjList, int vertexNum, int arcNum) { //初始化构造图(邻接表法)
	DataType vi, vj;
	int count = 0;
	initVertex(vertex, vertexNum);
	for (int i = 0; i < vertexNum; i++) { //初始化顶点表
		adjList[i].vertex = vertex[i];
		adjList[i].firstEdge = NULL;
	}
	for (int i = 0; i < arcNum; i++) {
		//输入边的信息储存在边表中
		printf("请输入第%d条边依附的两个顶点的编号(方向->):", count++);
		scanf("%d %d", &vi, &vj); //输入该边依附的顶点的编号
		ArcNode *s;
		s = (ArcNode *)malloc(sizeof(ArcNode));
		if (s != NULL) {
			s->adjvex = vj;
			s->next = adjList[vi].firstEdge; //头插法建立链表
			adjList[vi].firstEdge = s;
		} else
			printf("init error!\n");
	}
}

void initVertex(DataType *vertex, int vertexNum) {//输入函数
	printf("请逐个输入顶点的内容:");
	DataType x;
	for (int i = 0; i < vertexNum; i++) { //顶点数组赋值
		scanf("%d", &x);
		vertex[i] = x;
	}
}

void printALGraph(VertexNode *adjList, int vertexNum) {
	printf("vertex  firstEdge\n");
	ArcNode *p ;
	for (int i = 0; i < vertexNum; i++) {
		printf("%3d -->", adjList[i].vertex);
		p = adjList[i].firstEdge;
		while (p != NULL) {
			printf("%d -->", p->adjvex);
			p = p->next;
		}
		printf("NULL\n");
		printf("\n");
	}
}

int isLinked(VertexNode *adjList, int i, int j) { //两顶点i,j是否有边相连,1是相连,0是不相连
	ArcNode *p = adjList[i].firstEdge ;
	while (p != NULL) {
		if (p->adjvex == j)
			return 1;
		else
			p = p->next;
	}
	p = adjList[j].firstEdge;
	while (p != NULL) {
		if (p->adjvex == i)
			return 1;
		else
			p = p->next;
	}
	return 0;
}

int nodeDepth(VertexNode *adjList, int index, int vertexNum) { //任意一顶点的度
	int count = 0;
	ArcNode *p = adjList[index].firstEdge;
	while (p != NULL) {
		count++;
		p = p->next;
	}
	return count;
}

void freeArcNode(VertexNode *adjList, int vertexNum) {
	ArcNode *p;
	ArcNode *temp;
	for (int i = 0; i < vertexNum; i++) {
		p = adjList[i].firstEdge ;
		while (p != NULL) {
			temp = p;
			p = p->next;
			free(temp);
		}
	}
}

2. 图的测试_邻接表.c

#include "图_邻接表.h"

int main() {
	DataType vertex[MAX_VERTEX];//储存所有的顶点
	int vertexNum, arcNum; //结点个数,边的个数
	printf("输入顶点个数:");
	scanf("%d", &vertexNum);
	printf("输入边个数:");
	scanf("%d", &arcNum);
	VertexNode adjList[vertexNum];//顶点表
	ALGraph(vertex, adjList, vertexNum, arcNum);
	printALGraph(adjList, vertexNum);
	printf("测试判断两顶点是否相连,请输入两个顶点下标:");
	int i, j;
	scanf("%d %d", &i, &j);
	if (isLinked(adjList, i, j) == 1)
		printf("相连!\n");
	else
		printf("不相连!\n");
	printf("测试求顶点的度,请输入一个顶点下标:");
	int index;
	scanf("%d", &index);
	printf("该顶点的度为:%d", nodeDepth(adjList, index, vertexNum));
	freeArcNode(adjList, vertexNum);
}

(4)测试输出

测试用例:

输出:

3.十字链表

在结构体定义里添加了一个指针域,指向了<--方向的点

 

初学小白,有错误欢迎指正喔!!