图的链式前向星存储结构

一般来讲，图的常用存储结构有邻接矩阵，和邻接表，但我们知道邻接矩阵空间浪费太严重，邻接表不好写，今天来讲一下图的另一只常用的存储结构：前向星和链式前向星，介于上述两种存储结构之间的一种比较均衡的存储结构。

首先我们来说一下图的前向星表示方法：

前向星是一种通过存储边信息的方式来存储图的一种数据结构，他构造简单，读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排列，前向星也就构造完成了。方便查询，我们用另外一个数组head（i）来存储起点为vi的第一条边的位置。

存储结构：

int head[MAXN];
struct Node
{
int from;//起点
int to;//终点
int w;//权值
};
Node map[MAXN];

比较函数：

bool cmp(const Node &a,const Node &b)
{
if(a.from==b.from)
{
if(a.to==b.to) return a.w<b.w;
else return a.to<b.to;
}
else return a.from<b.from;
}

读入数据：

cin>>n>>m;
for(i=1; i<=m; i++)
cin>>map[i].from>>map[i].to>>map[i].w;
sort(map+1,map+m+1,cmp);
memset(head,-1,sizeof(head));
for(i=1; i<=m; i++)
if(map[i].from!=map[i-1].from)
head[map[i].from]=i;

遍历函数：

for(i=1;i<=n;i++)
for(j=head[i];map[j],from==i&&j<=m;j++)
cout<<map[i].from<<map[i].to<<map[i].w<<endl;

可以看出，前向星构造时间的复杂度主要取决于排序函数，一般来说，时间复杂度为O（m logm）；空间上需要两个数组，故空间复杂度为O（m+n）；

前向星的有点在于可以对应点非常多的情况，可以存储重复边，但不能直接判断图中任意两点是有边。

链式前向星又称为邻接表的静态建表方式，其最开始确实是基于前向星，是以提高前向星的构造效率为目的设计的存储方式，最终演变成了一个变形的邻接表这一数据结构。链式前向星采用数组模拟链表的方式实现邻接表的功能（数组模拟链表的主要方式就是记录下一个节点在数组的哪个位置。），并且使用很少的额外空间，可以说是目前建图和遍历效率最高的存储方式了。

数据结构：

int head[MAXN];//表示以i为起点的第一条边的存储位置
struct Node
{
int to;//第i条边的终点
int w;//第i条边的权值
int next;//与第i条边同起点的下一条边的存储位置
};
Node map[MAXN];

信息存储代码：

cin>>i>>j>>w;
map[k].to=j;
map[k].w=w;
map[k].next=head[i];
head[i]=k; 

遍历代码：

for(i=1; i<=n; i++)
for(j=head[i]; j!=-1; j=map[j].next)
cout<<i<<map[j].to<<map[j].w<<endl;

转自该大佬的博客（感谢）：https://www.cnblogs.com/Tovi/p/6194786.html

链式前向星的参考网站：https://malash.me/200910/linked-forward-star/

最后

以上就是激情月光为你收集整理的图的链式前向星存储结构的全部内容，希望文章能够帮你解决图的链式前向星存储结构所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。