2018-06-18

---

今天学习了前向星这种数据结构，前向星是一种非常节省空间的存图方式，在ACM比赛中，常见的的存图方式有三种。

---

——邻接矩阵，即用二维数组实现，G[u][v]为<u,v>边的权值。邻接矩阵适用于存储稠密图，点不多而边很多的时候，邻接矩阵的优点是好写，可读性高，方便删除边。

——邻接表，一般用vector<edge>G[MAXN_V]模拟邻接表，邻接表适用于疏密图，相比于邻接矩阵节省空间。

其优点是写起来快，可读性高，方便执行STL中的一些函数。

——前向星，前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就

按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.

用len[i]来记录所有以i为起点的边在数组中的存储长度.，用head[i]记录以i为边集在数组中的第一个存储位置.

我们输入边的顺序为:

1 2    2 3    3 4    1 3    4 1    1 5    4 5

pair<int,int>G[MAXN_E];

用pair存储并排序后得到

G[0]=(1,2); 

G[1]=(1,3);

G[2]=(1,5);

G[3]=(2,3);

G[4]=(3,4);

G[5]=(4,1);

G[6]=(4,5);

---

则head数组和len数组为:

head[1]=0;  head[2]=3;  head[3]=4;    head[4]=5;    head[5]=-1;

len[1]=3;      len[1]=3;      len[3]=1;        len[4]=2;        len[5]=0;

---

但是利用前向星会有排序操作,如果用快排时间至少为O(nlog(n))

——如果用链式前向星,加入next索引模拟指针指向下一个点的位置，就可以避免排序.

建立结构体为：

struct edge

{

    int to;//边的终点

    int value;//边的权值

    int next;//表示与第i条边同起点的下一条边的存储位置

};

另外还有一个数组head[],它是用来表示以i为起点的索引的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实

在以i为起点的所有边的最后输入的那个编号.

如果按照索引顺序，next表示下一条边的存储位置，如果按照添加顺序，next即为上一条添加的边的位置。

所以我们可以得到，输入顺序和存图顺序或者说是遍历顺序是相反的。

还是上面的图，我们定义全局变量int cnt=0;

并将head[]初始化为-1；

void addedge(int u,int v,int w)

{

    e[cnt].value=w;

    e[cnt].to=v;

    e[cnt].next=head[u];

    head[u]=cnt++;

}

模拟插入为下面的过程：

edge[0].to = 2;    edge[0].next = -1;      head[1] = 0;

edge[1].to = 3;    edge[1].next = -1;      head[2] = 1;

edge[2].to = 4;    edge[2],next = -1;      head[3] = 2;

edge[3].to = 3;    edge[3].next = 0;      head[1] = 3;

edge[4].to = 1;    edge[4].next = -1;      head[4] = 4;

edge[5].to = 5;    edge[5].next = 3;      head[1] = 5;

edge[6].to = 5;    edge[6].next = 4;      head[4] = 6;

---

这样在遍历时是倒着遍历的,也就是说与输入顺序是相反的,不过这样不影响结果的正确性.

比如以上图为例,以节点1为起点的边有3条,它们的编号分别是0,3,5  而head[1] = 5

我们在遍历以u节点为起始位置的所有边的时候是这样的:

for(int i=head[u]; ~i ;i=edge[i].next)

那么就是说先遍历编号为5的边,也就是head[1],然后就是edge[5].next,也就是编号3的边,然后继续edge[3].next,也

就是编号0的边,可以看出是逆序的.

链式前向星的优点：比邻接表还省空间，可以解决某些卡空间的问题，删除边也很方便，只需要更改next指针的指向即可。

总结：根据图的疏密选择存储方式，一般情况下用邻接表，卡空间时间这些要求比较高的题目或者需要删除边操作的用链式前向星。

——本文部分地方引用了acdream大牛的文章。