图的存储结构之邻接矩阵

目录

分析：

举例： 

那，对于有向图的邻接矩阵呢？会有什么不同吗？

对于网而言，其邻接矩阵有什么特点呢？

创建邻接矩阵：

1.邻接矩阵的构建

2.一维数组的构建

3.二维数组构建

4.整体构建代码：

其余案例：

优缺点：

总结：

图是多对多的数据类型，其存储结构分为两种：一种是线性，一种是链式

这里介绍利用线性数组来存储图。

分析：

首先，对于图而言，多对多肯定不是一个一维数组可以体现的物理结构，那么使用二维数组呢？在二维数组中标记谁和谁连接了。咦，感觉可以，那只有一个二维数组可以吗？

我们图的每个顶点好像还没有确定，那么就需要一个一维数组来存储顶点信息

🆗总结一下，邻接矩阵需要一个一维数组来存储顶点信息，一个二维数组来存储顶点之间的关系——也就是边。

举例： 

分析完了，下面就来创建两个数组吧 

这里利用无向图来介绍一下，两个数组中都存储什么？

——首先对于顶点来说肯定是存储顶点的V1、V2等

然后二维数组——存储边的数组存放的是两个顶点之间到底有没有边，有边就存储1，没有就存储0.

1.那么整体看下来，二维数组的每一行每一列都代表着什么含义呢？

例如：第一行和第一列都代表着所有连接着V0的边，加起来等于V0的度（以该顶点为端点的边数）

2.而且我们发现，这个二维数组好像是关于对角线对称的

对于无向图的邻接矩阵而言，其该二维数组就是对称的。

那，对于有向图的邻接矩阵呢？会有什么不同吗？

定义——有向图就是顶点和顶点之间的关系是有方向的

对于有向图的邻接矩阵而言

把第i行定义为，以vi为尾的弧（出度边）

把第j行定义为，以vj为头的弧（入度边）

特点：

有向图的邻接矩阵可能是不对称的

顶点的出度=第i行元素之和

顶点的入度=第j行元素之和

顶点的度=第i行元素和第j行元素之和

对于网而言，其邻接矩阵有什么特点呢？

网的邻接矩阵的二维数组变了

没有边的时候——把存储的单元设置为无穷大（代码中不可以表示无穷大，可以用一个较大的数字表示）

当有边的时候——把权值存储在空间里

创建邻接矩阵：

已经知道实例中如何创建了，现在就来使用代码来构建两个数组吧。

1.邻接矩阵的构建

#define n 1000
#define char C
#define int I

typedef struct{
    C vexs[n];
    A arcs[n][n];
}AMGraph;

2.一维数组的构建

顶点表刚才构建的是char类型的数组：vexs[n]

//vexs[n]
int p;//实际的顶点数
cin>>p;
for(int i=0;i<p;i++)
{
    cin>>vexs[i];
}

3.二维数组构建

对于二维数组，定义为：

特殊情况——当存储网的时候，如果没有边则用无穷大表示（但是代码中不可以表示无穷大，可以用一个较大的数字表示）

对于二维数组而言，先把所有的初始化为0，然后当顶点间有边时赋值为1。

对于不同的图，二维数组的构建其实不一样，例如：对于无向图，由于它是对称的所以只赋值一边即可，但是对于其他的图不一样，其他的需要把所有给判断一遍。

这里先用无向图来举例，代码如下：

两个for循环来赋值

int i=0;
int j=0;
for(;i<p;i++)
{
    for(;j<p;j++)
    {
      G.arcs[i][j]=MAXlnt;      
    }
}
for (int t = 0; t < G.arcnum; t++)
{
	cout << "输入边对应两顶点的下标\n";
	cin >> i >> j;
	G.arcs[i][j] = 1;
	G.arcs[j][i] = 1;
}

 有边的填1，无边的输入0

4.整体构建代码：

思路：

1. 先构建一个结构数组，来创建邻接矩阵的存储单元——顶点表、边表、边和点的数量
2. 创建函数来对邻接矩阵操作
   1. 先输入顶点和边的数量
   2. 然后输入顶点信息到顶点表中
   3. 初始化邻接矩阵其中的二维数组
   4. 完成邻接矩阵的构建，实现图的存储

代码：

#include<iostream>
#include<stdlib.h>
#define NMAX 100
using namespace std;

typedef struct AMGraph
{
	char vexs[NMAX];
	int arcs[NMAX][NMAX];
	int vexnum, arcnum;
}AMGraph;

int CreateUDN(AMGraph& G)
{
	int i = 0;
	int j = 0;
	cin >> G.vexnum >> G.arcnum;
	cout << endl;
	for (; i < G.vexnum; i++)
	{
		cin >> G.vexs[i];
	}
	cout << endl;
	for (i = 0; i < G.vexnum; i++)
	{
		for (; j < G.vexnum; j++)
		{
			G.arcs[i][j] = 0;
		}
	}
	for (int t = 0; t < G.arcnum; t++)
	{
		cout << "输入边对应两顶点的下标\n";
		cin >> i >> j;
		G.arcs[i][j] = 1;
		G.arcs[j][i] = 1;
	}
    //打印邻接矩阵
	cout<<"邻接矩阵为:\n";
    for(i=0;i<G->numV;i++)
	{
        for(j=0;j<G->numV;i++)
            cout<<G->arr[i][j]<<"  ";
        cout<<"\n";
	}

	return 1;
}

其余案例：

刚才是无向图的构建代码，那么对于有向图的邻接矩阵怎么创建呢？

其实很多地方都差不多，只有创建邻接矩阵的代码有所差别

//创建邻接矩阵
	for(k = 0;k < G->numE;k++)
	{
		cout<<"输入弧Vi->Vj对应两顶点的下标\n";
		cin>>i>>j;
		G->arr[i][j] = 1;
	}

输入的是从尾到头的顶点，讲究按照方向输入顶点。

优缺点：

邻接矩阵有好有坏，好处是它可以很好的去表示出顶点的度，清晰明了，而缺点是当图较为稀疏时，浪费的空间较多。

具体的优点：

缺点：

1. 不便于增加和删除顶点

2. 很可能会浪费空间——当存稀疏图时有大量无效元素

但是对稠密图，用邻接矩阵还是比较好的。

3. 浪费时间——统计稀疏图中一共有多少条边

总结：

对于图来说，它的物理结构，是多对多的，而利用邻接矩阵也就是一个一维数组和一个二维数组来表示图，而链表有几种存储方式可以表示图：十字链表阿、邻接表、邻接多重表。下篇文章见

ヾ(•ω•`)o