最近做到最短路，用到了链式前向星，于是来总结一下

链表

链式前向星的本质其实就是数组模拟的链表，更具体一点就是数组模拟的多个链表，所以才会将普通链表的head指针变为了一个h数组。

数组模拟链表：（yxc模板）

// head存储链表头下标，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

链表这里就不展开了，但是可以看到，由于普通链表都是单个链，所以head指针只需要一个就行了。

链式前向星

链式前向星就是数组模拟的多个链表 - 我理解的是这就是数组模拟的邻接表

链式前向星中使用头插法

加边：

void add(int u, int v, int weight)   // 添加有向边 u->v, 权重为weight
{
    e[idx] = v;        // 记录边的终点
    w[idx] = weight;   // 记录边的权重
    nxt[idx] = h[u];   // 将下一条边指向结点u此时的第一条边
    h[u] = idx;        // 将结点u的第一条边的编号改为此时的idx
    idx++;             // 递增边的编号dix, 为将来使用
}

链式前向星使用的是头插法，每次插入都是在表头插入，即每次都要改变插入的链表的head指针指向的边。

这里实际上，e、w数组都是独立于链外的，他们只是存储了idx这个节点的性质，不要总是想着这两个数组也是串进链中的，这几个数组之间的链接方式就是依靠编号连接在一起的。

这里的nxt数组就等同与上面链表中的ne数组，都是指向上个存储的边 - 因为h是表头 - 指向上个存储的边。

注意：这里的h数组存储的是边的编号，即h数组维护的是边，而不是边的起点或终点！！h自身为一个链表，存储该链所维护的第一个节点

nxt数组也是一样的，存储的是边的编号！！

然后令h指向idx，令表头恢复到首位，完成加边；最后idx++，为了下次加边。

这里h、nxt链表中的其实是关于以某节点u为起点的所有边置于一个链表中。

理解了上面的代码，链式前向星其实就结束了。

遍历：

void iterate(int u)   // 遍历结点u的所有邻边
{
    // 从u的第一条边开始遍历，直到eid==-1为止
    for(int eid = h[u]; eid != -1; eid = nxt[eid])
    {
        int v = e[eid];
        int weight = w[eid];
        cout << u << "->" << v << ", weight: " << weight << endl;
    }
}

初始化：

memset(h, -1, sizeof h);  // 初始化h数组为-1
idx = 0;                 // 初始化边的编号为0

更新

2024/04/07 复习到了图论，重新理解了一遍链式前向星，又写了一点理解

2024/04/16 理解又加深一点