前向星 | Kyons'Blog 


 


前向星

欢迎各大佬,大牛对本文指正,也希望本文能对各位有所帮助

一.基本概念

  前向星是什么??
  前向星是一个边集数组.啥玩意啊,拽什么专业词汇啊.也就是说,与邻接矩阵相比,前向星更像是用vector储存的邻接链表,是储存边的数组.
  这个数组储存的是图里的每一条边.(下面上图)
  下面是一组图的数据
  $4$个顶点,$6$条边,起点,终点,这条边的长度
4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

1

  前向星储存什么呢,存的是

第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
2
3
struct edge {
int star, end, cost;
}p[100000];

2.保存和输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool operator <(edge a, edge b)
{
return a.star < b.star;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> p[i].star >> p[i].end>>p[i].cost;
sort(p, p + m);
for (int i = 0; i < m; i++)
printf("%d %d %d\n",p[i].star,p[i].end,p[i].cost);
return 0;
}

  当一个巨大的图却只有几个边的时候,这种保存方式的优势就大大的体现了出来.但是储存后需要按照起点排序.才能进行搜索或者求最短路.
  于是复杂度就要加上了排序的耗时.

三.优化–链式前向星

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
  使$next=0$表示木有出边 为什么边序号是倒着的??(这里先卖个关子,后面会说)

2.代码实现(边的储存以及输出)

(1).数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct edge {
int end, cost,next;
}p[500001];
int head[10001];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int s,e, c;
cin >> s >> e >> c;
p[i].end = e, p[i].cost = c;
p[i].next=head[s];
head[s] = i;
}
for (int i = 1; i <= n; i++) {
int f = head[i];
while (f) {
printf("%d %d %d\n", i, p[f].end, p[f].cost);
f = p[f].next;
}
}
return 0;
}

  为什么边的位置是倒着的,木措,就是因为这两行,保存方式为下图演示.

1
2
p[i].next=head[s];
head[s] = i;

  让$head[i]$储存输入的边的位置,再让这条边的指向变为$head[i]$储存的位置.那么就意味着,越晚输入的边,它越靠近$head[i]$.
杂色不知道为什么

(2).指针实现

  作为一个忠于指针写数据结构的人,怎么可能不用指针写一下这个家伙呢(雾).
  看懂上面的,这个应该没什么问题吧(逃)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef struct edge* nd;
struct edge {
int end, cost;
nd next;
};
nd head[10001];
void close(int n)
{
for (int i = 1; i <= n; i++) {
nd p = head[i];
while (p != NULL) {
nd f = p->next;
delete(p); //free(p);
p = f;
}
}
}

int main()
{
int n, m;
cin >> n >> m;
memset(head, NULL, sizeof(head));
for (int i = 1; i <= m; i++) {
int s, e, c;
cin >> s >> e >> c;
nd p = new(edge); //nd p=(nd) malloc(sizeof(edge));
p->end = e, p->cost = c;
p->next = head[s];
head[s] = p;
}
for (int i = 1; i <= n; i++) {
nd f = head[i];
while (f!=NULL) {
printf("%d %d %d\n", i, f->end, f->cost);
f = f->next;
}
}
close(n);
return 0;
}

 


 


 



 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载