大家对链式前向星一定不陌生，毕竟是常用的建图模型。

链式前向星其实可以看作一个关于边信息的链表。

我在做一道题目时发现了一个奇怪的现象：链式结构的效率在同等规模数据下，效率出现偏差。

我做了一个测试，$300$个点，$3\times 10^7$条边，给每个点建立$10^5$条边。

然后我遍历了每一条边，遍历方式是按顺序访问每个点的边。（不是图的遍历方法，因此边的指向"to"的值不重要，代码中用rand()代替）

我发现，不同的加边顺序将对遍历的时间产生较为显著的影响。

下面给出两份代码：

#define George_Plover
#include <list>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <algorithm>
#define MAXM 100101
#define MAXN 100101
#define MAXL (100101*430)
#define LL long long
#define RG register
using namespace std;
int tot,pre[MAXN],lin[MAXL],to[MAXL];
void add(int x,int y)
{
    tot++;
    lin[tot]=pre[x];
    pre[x]=tot;
    to[tot]=y;
}
int main()
{
    int clk=clock();
    
    for(int i=1;i<=100000;i++)
    {
        for(int j=1;j<=300;j++)//以分散的顺序给每个点加边
            add(j,rand());
    }
    cout<<((clock()-clk)*1.0)/1000000<<endl;
    for(int i=1;i<=300;i++)
    {
        for(int j=pre[i];j;j=lin[j]);
    }
    cout<<((clock()-clk)*1.0)/1000000<<endl;
    return 0;
}

该代码的加边顺序是，进行$10^5$轮加边，每次给每个点加一条边。 运行时间在2s左右。

#define George_Plover
#include <list>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <algorithm>
#define MAXM 100101
#define MAXN 100101
#define MAXL (100101*430)
#define LL long long
#define RG register
using namespace std;
int tot,pre[MAXN],lin[MAXL],to[MAXL];
void add(int x,int y)
{
    tot++;
    lin[tot]=pre[x];
    pre[x]=tot;
    to[tot]=y;
}
int main()
{
    int clk=clock();
    i
    for(int i=1;i<=300;i++)
    {
        for(int j=1;j<=100000;j++)//一次性给一个点添加1e5条边
            add(i,rand());
    }
    cout<<((clock()-clk)*1.0)/1000000<<endl;
    for(int i=1;i<=300;i++)
    {
        for(int j=pre[i];j;j=lin[j]);
    }
    cout<<((clock()-clk)*1.0)/1000000<<endl;
    return 0;
}

该代码的加边顺序是，枚举每个点，一次性给每个点添加$10^5$条边。

运行时间约0.33s

两者的加边用时差别不大，但是遍历用时差别很大。

目前我还不能给出一个清晰的解释，不知各位有何高见？

欢迎大家讨论。