跳转到内容

链式前向星

来自维基学院

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

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

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

邻接矩阵空间复杂度为;而邻接表的空间复杂度与链式前向星差不多,为

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

代码实现

[编辑 | 编辑源代码]

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