鏈式前向星
外觀
鏈式前向星是一種用於存儲圖的數據結構,一般認為是由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);
}
}
- 李煜東 《算法競賽進階指南》
- 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