链式前向星
外观
链式前向星是一种用于存储图的数据结构,一般认为是由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