链式前向星
发布日期:2021-06-29 05:37:42
浏览次数:5
分类:技术文章
本文共 1013 字,大约阅读时间需要 3 分钟。
之前存图用邻接表都是直接使用的vector,但是vector是自动扩容的,在空间不够的时候会自动申请多一倍的空间,这样的话空间浪费比较严重,而且有的题目会卡空间,可能就过不了。如果使用链式前向星,就可以节省不少空间,开一个和边的数目相同的数组就可以了。
链式前向星包括两个部分:head数组,和edge数组。
head[i]表示以i为起点的第一条边的位置。
edge是个结构体数组:
struct Edge{ int to;//表示第i条边的终点 int next;//表示与第i条边同起点的下一条边的存储位置 int w;//权值}edge[M];加边的代码:
void add(int u,int v,int w) { edge[cnt].w = w; edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; }遍历以u为起点的所有边:
for(int i=head[u];i!=-1;i=edge[i].next)整体代码:
#include#include #define N 105 //顶点数目 #define M 10005 //边的数目 struct Edge{ int to; int next; int w;}edge[M];int head[N];int main(){ int n, m, u, v, w, cnt; scanf("%d%d", &n, &m); memset(head, -1, sizeof(head)); cnt = 0; for(int i = 0; i < m; i++){ //建图 scanf("%d%d%d", &u, &v, &w); edge[cnt].w = w; edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } for(int i = 0; i < n; i++){ //遍历以i为头的所有边 for(int j = head[i]; j != -1; j = edge[j].next) printf("%d ", j); printf("\n"); } return 0;}
转载地址:https://blog.csdn.net/zhj_fly/article/details/75270737 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月23日 21时45分39秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
现在做硬件工程师还有前途吗?
2019-04-29
用 50 种编程语言写“Hello,World!”
2019-04-29
GD32替换STM32,这些细节一定要知道。
2019-04-29
华为员工离职心声:菊厂15年退休,感恩,让我实现了财务自由!
2019-04-29
春晚上的“拓荒牛”
2019-04-29
嵌入式驱动自学者的亲身感受,有什么建议?
2019-04-29
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
腾讯机器狗,站起来了!
2019-04-29
我用自己创造的深度学习框架进入腾讯,爽!
2019-04-29
芯片为什么持续缺货?
2019-04-29
又涨了?2021 年 3 月程序员工资统计新出炉
2019-04-29
初入行的C++程序员,如何快速摆脱CRUD阶段?
2019-04-29
研究生跟了一个很棒的导师是种怎样的体验?
2019-04-29
学会扶墙的机器人:没有什么能让我倒下!
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
单片机的几种数字滤波算法
2019-04-29
用单片机控制导弹?
2019-04-29
各种滤波器合集!
2019-04-29
国产CPU深度研究报告(干货,110页)
2019-04-29
在电路中,耦合是什么?有哪些方式?
2019-04-29