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

一、图的存储方式

目前常用的图的存储方式有两种，邻接矩阵和邻接表存储。
边数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];
}