欢迎各大佬,大牛对本文指正,也希望本文能对各位有所帮助
一.基本概念
前向星是什么??
前向星是一个边集数组.啥玩意啊,拽什么专业词汇啊.也就是说,与邻接矩阵相比,前向星更像是用vector储存的邻接链表,是储存边的数组.
这个数组储存的是图里的每一条边.(下面上图)
下面是一组图的数据
$4$个顶点,$6$条边,起点,终点,这条边的长度
4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
前向星储存什么呢,存的是
第i条边 | 起点 | 终点 | 长度 |
---|---|---|---|
1 | 1 | 2 | 2 |
2 | 2 | 3 | 2 |
3 | 2 | 4 | 1 |
4 | 1 | 3 | 5 |
5 | 3 | 4 | 3 |
6 | 1 | 4 | 4 |
二.代码实现
看了一下存储方式是不是感觉so~~easy,确实如此.
但是依然改变不了这是一个很优秀的数据结构(雾)
1.核心代码
1 | struct edge { |
2.保存和输出
1 | bool operator <(edge a, edge b) |
当一个巨大的图却只有几个边的时候,这种保存方式的优势就大大的体现了出来.但是储存后需要按照起点排序.才能进行搜索或者求最短路.
于是复杂度就要加上了排序的耗时.
三.优化–链式前向星
1.基本概念
没错,就是优化,让我们来考虑如何去掉这个鬼畜的排序$呢^呢$??
只需要稍微改变一点点储存方式,再加入一个next就可以了.于是就像是从一个点发出去的链子一样.所以称为链式前向星(雾).
怎么弄呢?
$head[i]$保存的是第i个点的始边的位置,edge保存的是第i点的一条边的终点与长度,以及第i个点的下一条边的位置.分别用$end$,$cost$,$next$表示.
于是就这样子了
还是这个数据,会变成什么样子呢??
第i条边 | 起点 | 终点 | 长度 |
---|---|---|---|
1 | 1 | 2 | 2 |
2 | 2 | 3 | 2 |
3 | 2 | 4 | 1 |
4 | 1 | 3 | 5 |
5 | 3 | 4 | 3 |
6 | 1 | 4 | 4 |
2.代码实现(边的储存以及输出)
(1).数组实现
1 | struct edge { |
为什么边的位置是倒着的,木措,就是因为这两行,保存方式为下图演示.
1 | p[i].next=head[s]; |
让$head[i]$储存输入的边的位置,再让这条边的指向变为$head[i]$储存的位置.那么就意味着,越晚输入的边,它越靠近$head[i]$.
(2).指针实现
作为一个忠于指针写数据结构的人,怎么可能不用指针写一下这个家伙呢(雾).
看懂上面的,这个应该没什么问题吧(逃)
1 | typedef struct edge* nd; |