首页 > 其他 > 详细

前向星存图

时间:2019-04-24 19:59:06      阅读:127      评论:0      收藏:0      [点我收藏+]

图论的第一步:存图

众所周知,邻接矩阵可以存图。但是开二维数组开着开着就MLE了。所以我们就需要一个高大上的存图:链式前向星☆☆☆

什么是链式前向星呢?

技术分享图片

 

这就是链式前向星(我没骗人

不闹了不闹了。

链式前向星是按照边的编号进行存储。将每条边放进edge[i]里面,存入的信息分别是next(这条边的下一条),to(这条边的终点),dis(这条边的权值),这就要用到结构体

struct Edge{
int next,to,dis;
}edge[500001];

同时再开一个head数组,head[i]表示以i为起点,当前编号最大的那条出边(出边就是以i为起点的边)。因为存图的过程是不断更新的,所以是当前。

这也就解释了起点存在哪

int node_num;
void add(int from,int to,int dis)
{ node_num++;
   edge[node_num].to=to;
   edge[node_num].dis=dis;
   edge[node_num].next=head[from];//这里next指向上一条边(当前没有更新的head[from]对于这个from来说,已经是倒数第二大编号的边了)这里比较难懂,嗯
   head[from]=node_num;//以from为起点的最后一条出边的编号更新为num_node
}

好像讲完了233(这样存储的图就像开始的那张图一样,所以我真的没骗人)

 

前向星存图

原文:https://www.cnblogs.com/lcez56jsy/p/10764475.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!