图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。本文将着重讲解建图存边的几种方法,主要学习如何定义、如何建边、如何访问，并且分析时间、空间复杂度以及应用场景。

邻接矩阵

定义一个二维数组 $存储点到点的边权$
初始化建边时,只需要暴力枚举所有的边即可
假设给定所有点之间对应的边权矩阵，只需要暴力枚举所有的边即可建边。

1
2
3

for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
		G[i][j] = w;

如果给定条边，也很简单，枚举所有边

for(int i = 1; i <= m; i++)
{
	int u,v,w;
	cin >> u >> v >> w;
	G[u][v] = w; 
}

当我们需要访问时(这里假设用dfs访问整张图),代码如下

int vis[MAXN]; 
void dfs(int u)
{
	vis[u] = true;
	for(int v = 1; v <= n; v++)
	{
		if(G[u][v]) printf("%d &d &d\n",u,v,G[u][v]); //输出所有边的信息
		if(vis[v]) continue;
		else dfs(v);
	}
}
......
dfs(1)

时间复杂度:

空间复杂度:

适用于点数不多的稠密图，因为初始化的复杂度就已经很大了。

边集数组

我们使用一个结构体数组来存储 $起点、终点和边权$ ,这样我们就不用枚举任意两个点的点关系，大大降低了复杂度

具体操作如下

struct edge{
	int u,v,w;
}e[MAXN];
int vis[MAXN];
void dfs(int u)
{
	vis[u] = true;
	for(int i = 1; i <= m; i++)
	{
		if(e[i].u == u)
		{
			int v = e[i].v,w = e[i].w;
			print("%d %d %d\n",u,v,w);
			if(vis[v]) continue;
			else dfs(v);
		}
	}
}
int main(){
	cin >> n >> m; //n个点 m条边
	for(int i = 1; i <= m; i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		e[i] = {u,v,w}; //花括号里面顺序与结构体定义的顺序一一对应
	}
	dfs(1);
	return 0;
}

时间复杂度:

空间复杂度:

应用：常用于Kruskal算法中,按边权排序存边

邻接表

使用vector维护一个出边数组,存储点的所有出边以及边权

本博客后续大多数图论内容也将以此为基础进行展开，大多数情况下采取此种方法进行建边

实现代码：

struct node{
	int v,w;
};
vector<node> G[MAXN];
void dfs(int u,int fa)
{
	for(auto ed : G[u])  
	{
		int v = ed.v, w = ed.w;
		if(v == fa) continue;
		printf("%d %d %d\n",u,v,w);
		dfs(v, u);
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		G[u].push_back({v,w}); //花括号中顺序与结构体定义的顺序一一对应 
		G[v].push_back({u,w}); //假设是无向边
	}
	return 0;
}

时间复杂度:

空间复杂度:

缺点:在网络流中无法处理反向边

链式邻接表

使用两个数组,一个边集数组存储第条边的起点终点和边权

然后使用一个表头数组存储点的所有出边

struct edge{
	int u,v,w;
};
vector<edge> e //边集
vector<int> G[MAXN] //点的所有出边

void add(int u,int v,int w)
{
	e.push_back({u,v,w});
	G[u].push_back(e.size() - 1) //对边进行编号存储 
}
void dfs(int u,int fa)
{
	for(int i = 0; i < G[u].size(); i++
	{
		int j = G[u][i];
		int v = e[j].v,w = e[j].w;
		if(v == fa) continue;
		printf("%d %d %d\n",u,v,w);
		dfs(v,u);
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		add(u,v,w);
		add(v,u,w); 
	}
	return 0;
}

时间复杂度:

空间复杂度:

应用：可以应用到各种图，并且可以处理反向边

链式前向星

我们使用两个数组，一个数组就是以为起点的第一条边的存储位置

数组是一个边集，存边的信息

struct node{
	int to; //第i条边的终点 
	int w; //第i条边的边权 
	int nxt; //与第i条边同起点的下一条边的位置 
}edge[MAXN]; //边数组
int head[MAXN] //头数组，最近一次输入的以i为起点的边在edge数组中的下标

void add(int u,int v,int w)
{
	edge[cnt].to = v; //cnt为edge(边)的索引 
	edge[cnt].w = w;
	edge[cnt].nxt = head[u]; //理解为头插法 
	head[u] = cnt++; //更新头节点 
}
void dfs(int u,int fa)
{
	for(int i = head[u]; ~i; i = edge[i].nxt) //~i即表示枚举到-1,按位取反得0，退出循环表示没有其他出边 
	{
		int v = edge[i].to,w = edge[i].w;
		if(v == fa) continue;
		printf("%d %d %d\n",u,v,w);
		dfs(v,u);
	}
}
int main(){
	cin >> n >> m;
	memset(head,-1,sizeof(head)); //初始化所有点第一条出边为-1 
	for(int i = 1; i <= m; i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0)
	return 0;
}

时间复杂度:

空间复杂度:

应用：可以用于所有图，可以处理反向边

小结

时间复杂度:

邻接矩阵:、边集数组:、邻接表:、链式邻接表:

链式前向星:

空间复杂度:

邻接矩阵:、边集数组:、邻接表:、链式邻接表:

链式前向星:

后续文章我们图论的主要内容将围绕邻接表、链式前向星、邻接矩阵展开

这三种建图存边的方法也是应用最多的三种方法。

图论基础—图的存储

目录

本文目录

图论简介

邻接矩阵

边集数组

邻接表

链式邻接表

链式前向星

小结