鏈式前向星

鏈式前向星是一種用於存儲圖的數據結構，一般認為是由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