C++图论之邻接矩阵-创新互联

1. 邻接矩阵是啥

创新互联于2013年成立,先为长宁等服务建站,长宁等地企业,进行企业商务咨询服务。为长宁企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

它是用来存图的一种方式,不过唯一的问题就是占用非常大,大部分用于稠密图。

2. 邻接矩阵用法

它其实就是一个二维数组,现在我们设N为点数,邻接矩阵就可以这么定义:

int a[N][N];//从0点开始。
int a[N+5][N+5];//从1点开始,这里我给他扩大到了(N+5)*(N+5)这样更保险,实际扩大到(N+1)*(N+1)就可以了。

我们设a[i][j]的值为i点到j点的边权,但是有些点之间没有边我们可以用很大的数来区分,这时有人就要问了:“啊为什么作者你不用负数呢?!”,因为有时还有负边权,顾名思义这个边权是负数。但是要是题目写了没有负边权,你还是可以用负数的。

以上的是带边权的图,那不带边权的图我们可以这么定义:

bool a[N][N];//从0开始的。
bool a[N+5][N+5];//从1点开始,这里我给他扩大到了(N+5)*(N+5)这样更保险,实际扩大到(N+1)*(N+1)就可以了。

两点之间有边就设为true,否则设为false。 

3. 邻接矩阵代码

虽然我知道各位应该不需要代码就会了,但是为让各位学的更透彻,还是上代码吧(n=点数,m=边数)。

(1)带边权的

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		a[i][j]=1e+9;//做题的时候,按要求设置大小就可以了(1e+9=1000000000)。
	}
}//初始化。
for(int i=1;i<=m;i++){
	int u,v,w;//u点到v点之间有一条边权为w的边(v点到u点之间有一条边权为w的边)。
	cin>>u>>v>>w;
	a[u][v]=w;
	a[v][u]=w;
}

(2)不带边权

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		a[i][j]=0;
	}
}//初始化。
for(int i=1;i<=m;i++){
	int u,v;//u点到v点之间有一条边(v点到u点之间有一条边)。
	cin>>u>>v>>w;
	a[u][v]=1;
	a[v][u]=1;
}

邻接矩阵讲完了,作者正摆烂着度过一个漫长无聊的寒假,非常不容易,留下你的点赞再走吧!

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


名称栏目:C++图论之邻接矩阵-创新互联
本文网址:http://myzitong.com/article/cdjjhi.html