数据库怎么实现临接矩阵

这篇文章主要介绍“数据库怎么实现临接矩阵”，在日常操作中，相信很多人在数据库怎么实现临接矩阵问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”数据库怎么实现临接矩阵”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

       图由顶点跟边或者弧构成  顶点不分大小主次  用一维数组表示顶点， 边或弧 用二维数组存储，二维数组就是邻接矩阵

       G(V,E) 如果有N个顶点 则临接矩阵为N*N 方阵

       维持一个二维数组，arr[i][j]表示i到j的边，如果两顶点之间存在边，则为1，否则为0；  无向图为对称矩阵

       维持一个一维数组，存储顶点信息，比如顶点的名字；

1. 邻接矩阵（无向图）的特点：

图的邻接矩阵存储方式是用两个数组来表示图：

1.）一个一维数组存储存储图中顶点信息。

2.）一个二维数组（称为邻接矩阵）存储图中边或弧的信息。

上图中我们设置两个数组：

顶点数组：vertex[4] = {V0，V1，V2，V3}

边数组：arc[4][4] 为对称矩阵（0表示顶点间不存在边，1表示顶点间存在边）

2. 邻接矩阵（有向图）的特点：

无向图的边构成了一个对称矩阵，貌似浪费了一半的空间，那如果是有向图来存放，会不会把资源利用好呢？

顶点数组vertex[4] = {V0，V1，V2，V3}

弧数组arc[4][4]也是一个矩阵，但因为是有向图，所以这个矩阵并不对称。

如： V1到V0有弧，所以arc[1][0] = 1，而V0到V1没有弧，所以arc[0][1] = 0 

3. 邻接矩阵（网）的特点：

每条边上带有权的图就叫网。通常权值表示两点之间的距离。

这里∞表示一个计算机允许的，大于所有边上权值的值。

定义临接矩阵 图结构

typedef char Vtype;//顶点类型
typedef int   Etype;//边或者弧上的权值 类型
#define MAXV 100 //最大顶点数
#define UNexist  65535 //不存在权值
typedef struct 
{
	Vtype VArr[MAXV];//顶点数组
	Etype EArr[MAXV][MAXV];//临接矩阵
	int numV；//当前顶点数
	int numE；//当前边数
}MGraph;

构造一个图  下面代码为无向图
void CreateMGraph(MGraph* G)
{
	int i,j,k,w;
	cout<<" 输入顶点数";
	cin>> G->numV;
	cout<<" 输入边数";
	cin>> G->numE;
	for(i=0;i<G->numV;i++)
	{
		cin>> G->VArr[i];//输入顶点的信息；
	}
	for(i=0;i<G->numV;i++)//将临接矩阵初始化为空
	{
		for(j=0;j<G->numV;j++)
		{
			G->EArr[i][j] = UNexist;
		}
	}
	 for(k=0;k<G->numE;k++)
	 {
		cout<<"输入边的开始";
		cin>>i;
		cout<<"输入边的结尾";
		cin>>j;
		cout<<"输入边的权重";
		cin>>w;
		G->VArr[i][j]=W;
		G->VArr[i][j]=G->VArr[j][i]//无向图 对称
		//如果不是对称的话 上面一行注释点就好
	 }
}

V个顶点 E个无向边创建时时间复杂度为O( V^2)  邻接矩阵是不错的图存储结构 不过如果 顶点V之间相互存在的边很少 那么就存在很多空间浪费

到此，关于“数据库怎么实现临接矩阵”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！