查看“︁链式前向星”︁的源代码

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

== 比较 ==
[[w:邻接矩阵|邻接矩阵]]比链式前向星好写，链式前向星比[[w:邻接表|邻接表]]好写。

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

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

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

== 代码实现 ==
C++代码实现：<syntaxhighlight lang="cpp">
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);
    }
}
</syntaxhighlight>

== 参考 ==
# 李煜东 《算法竞赛进阶指南》
# 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
[[Category:软件]]
[[Category:数据结构]]