跳至內容

鏈式前向星

來自維基學院

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