欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图论之图的存储 邻接矩阵、邻接表和链式前向星

程序员文章站 2022-03-25 14:04:53
...

一、图的存储方式

目前常用的图的存储方式有两种,邻接矩阵和邻接表存储。
边数M小于顶点N平方的图为稀疏图,反之为稠密图。稀疏图可用邻接表存储,稠密图可用邻接矩阵存储。邻接表可用数组或链表实现,邻接矩阵可用二维数组实现。

二、邻接矩阵

1、邻接矩阵简介

邻接矩阵很好理解,实质是用二维数组来存储一个图的各边的信息,例如用矩阵e[ i ][ j ]来存储,其中下标i是指一条边的起点的编号,而下标j就是该边终点的编号,e[ i ][ j ]的值存的是该边的权值。
用邻接矩阵既可以存储无向图,也可以存储有向图。例如对于权值为x的ab边存无向图时,e[ a ][ b ] = x; e[ b ][ a ] = x; 。而存有向图时只需e[ a ][ b ] = x;即可。

例如,将下方的有向图以邻接矩阵的方式存储
图论之图的存储 邻接矩阵、邻接表和链式前向星
图论之图的存储 邻接矩阵、邻接表和链式前向星
顶点自身到自身的权值默认为0,若该边不存在,就存为无穷大。

2、邻接矩阵存储的代码模板

#include<iostream>

using namespace std;
const int N = 110,INF = 0x3f;	//N为最多顶点数,INF为无穷大

int e[N][N],n,m;	//e是邻接矩阵,n是顶点数,m是边数

int main()
{
	int a,b,w;
	cin >> n >> m;
	for(int i = 0;i <= n;i++)	//矩阵初始化
		for(int j = 0;j <= n;j++)
			if(i == j)
				e[i][j] = 0;	//自身存为0
			else
				e[i][j] = INf;	//其他边为无穷
	for(int i = 0;i < m;i++)
	{
		cin >> a >> b >> w;
		e[a][b] = w;		//加入边
		//e[b][a] = w;		//无向图的存储
	}

	return 0;
}

三、邻接表

1、邻接表简介
稀疏图用邻接矩阵存储十分浪费空间,大部分数据全是没有意义的无穷大,所以在文章开始提到了:稀疏图我们用邻接表存储比较好

正经的邻接表(链表实现):

图论之图的存储 邻接矩阵、邻接表和链式前向星

不正经的邻接表(数组实现):

我们用较为容易的数组来实现邻接表,先对1~m条边编号,然后用u,v,w三个一维数组存储边的信息,其中u[ i ],v[ i ],w[ i ]分别表示第i条边的起点是u[ i ],终点是v[ i ],权值是w、[ i ]。然后我们还需要数组来存储顶点和边的关系,我们用一个first[ i ]来存储i顶点的第一条边的编号,next[ i ]存储第i条边的下一条边的编号,最后一条边的下一条边存为-1 。

例如还是存储一图

图论之图的存储 邻接矩阵、邻接表和链式前向星
图论之图的存储 邻接矩阵、邻接表和链式前向星
2、邻接表存储的代码模板

#include<iostream>
#include<cstring>

using namespace std;
const int N = 110;
int u[N],v[N],w[N],n,m;
int first[N],next[N*N];

int main()
{
	cin >> n >> m;
	memset(next,-1,sizeof next);		//将next数组初始化为-1
	for(int i = 0;i < m;i++)
	{
		cin >> u[i] >> v[i] >> w[i];	//存储第i条边的信息
		next[i] = first[u[i]];		//先将第i边的下一条边设为顶点u[i]的第一条边
		first[u[i]] = i;		//然后将顶点u[i]的第一条边更新为i
	}

	return 0;
}

3、邻接表的遍历
邻接表的遍历不像邻接矩阵一样直接遍历矩阵即可,如图
图论之图的存储 邻接矩阵、邻接表和链式前向星
邻接表遍历代码

for(int i = 1;i <= n;i++)
{
	int k = first[i];
	while(k != -1)
	{
		cout << u[k] << " " << v[k] << " " << w[k] << endl;
		k = next[k];
	}
}

四、链式前向星

1、链式前向星简介
链式前向星的思想其实还是邻接表,也就是对上面数组实现的邻接表的一个优化,在比赛中一般用链式前向星多一些,非常实用。

2、代码模板

#include<iostream>
#include<cstring>

using namespace std;
const int N = 110;
int e[N],ne[N],h[N],w[N],idx;	//若不存权值可省略w数组
int n,m;

void add(int a,int b,int w)	//加边模板
{
	e[idx] = b;	//idx为边的编号,idx边的终点是e[idx]
	w[idx] = w;	//idx边的权值是w[idx]
	ne[idx] = h[a];	//idx边同起点的下一条边的编号是ne[idx]
	h[a] = idx++;	//a顶点的第一条边的编号是h[a]
}

int main()
{
	int a,b,c;
	cin >> n >> m;
	memset(h,-1,sizeof h);		//h要初始化为-1
	for(int i = 0;i < m;i++)
	{
		cin >> a >> b >> c;
		add(a,b,c);
	}

	return 0;
}

3、链式前向星的遍历

for(int i = 1;i <= n;i++)
{
	for(int k = h[i];k > 0;k = ne[k])
		cout << i << << e[k] << w[k];
}