链式前向星

链式前向星是一种用于存储图的数据结构，一般认为是由Jason911发明的。链式前向星采用了邻接表的思想，本质上就是用链表实现的邻接表。可以使用数组实现链表，定义head,to,nxt,edge数组，其中长度为n的head数组表示从每个节点出发的第一条边在to和edge数组中的位置，长度为m的to和edge是一一对应的，分别记录每条边的终点与边权（对于无权图，edge数组可省略），长度也为m的nxt数组模拟了链表指针，表示从相同节点出发的下一条边在to和edge数组中的位置。因此，链式前向星的空间复杂度为$O(n+m)$。

比较

邻接矩阵比链式前向星好写，链式前向星比邻接表好写。

但邻接矩阵比邻接表效率低，而邻接表比链式前向星效率高。

邻接矩阵空间复杂度为$O(n^{2})$；而邻接表的空间复杂度与链式前向星差不多，为$O(m)$。

综上所述，链式前向星是一个比较中庸的数据结构。但虽然链式前向星还未普及，它也是一种优秀的数据结构。

代码实现

C++代码实现：

int n,m,tot,head[MAXN],to[MAXN],edge[MAXN],nxt[MAXN];
bool vis[MAXN];
void add(int x,int y,int z)//插入有向边，起点为x，终点为y，权值为z
{
    tot++;
    to[tot]=y;  edge[tot]=z;
    nxt[tot]=head[x];  head[x]=tot;  //数组模拟链表，类似于拉链法
}
void dfs(int x)//深搜模板
{
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i])//访问每一条起点为x的边
    {
        int y=to[i];  //y为终点
        if(!vis[y])
            dfs(y);
    }
}

参考

1. 李煜东 《算法竞赛进阶指南》
2. J.Ebert. A versatile data structure for edge-oriented graph algorithms,Communications of the ACM,Volume 30,Issue 6,June 1987,pp 513–519,https://doi.org/10.1145/214762.214769