图的存储 - 链式前向星

其实本质上就是用链表实现的邻接表

基本信息

链式前向星是图论中一种牛逼高效的存储结构

时间复杂度：

添加边： $O(1)$
和邻接矩阵的复杂度一样，但是我们要在 head 数组的末尾添加新边，并更新头指针
遍历节点的出边： $O(k)$
其中： $k$ 为这个节点的出边数量。直接通过头指针开始遍历链表即可
断边：最坏情况 $O(m)$
需要遍历 edges 边数组找到目标边，但是通常如果涉及到了删除功能，我们不会用链式前向星
删除节点： $O(n)$
需要遍历所有的边，删除与该节点相关的边。如果我们真的需要这个功能的话，我们通常使用标记删除（也叫做“懒删除”，就是把这个点标记为被删除，实际上还存在于数据结构里）

空间复杂度： $O(n+m)$ ，其中： $n$ 为节点数， $m$ 为边数

添加与遍历

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int NODE_LEN=1e5+5;
const int EDGE_LEN=2e5+5;
//最多有 NODE_LEN 个节点，和最多 EDGE_LEN 条边

//定义边，存储指向的目标节点和下一条边的索引，以及边权
struct Edge
{
    int to,nxt,weight;
}edges[EDGE_LEN];//图中的所有边

int head[NODE_LEN];//对于每一条边，记录第一条边在 edges 数组中的下标
int cnt_edge=0;//边的数量

void add_edge(int u,int v,int w)//添加一条边，由出发节点 u 到目标节点 v ，边权为 w
{
    edges[cnt_edge].to=v;
    //当前计数边（也就是目前输入的第几个边）将会指向目标节点 v

    edges[cnt_edge].nxt=head[u];
    head[u]=cnt_edge;
    //下一条边
    edges[cnt_edge].weight=w;//由出发节点伸出的边的权值
    cnt_edge++;//存完一个啦！提前准备好下一个！
    cout<<"添加边：( "<<u<<" -> "<<v<<" ) 成功！且权值为 "<<w<<endl;
    return;
}

void traverse_nodes(int u)//遍历出发节点 u 的所有目标节点
{
    cout<<"节点 "<<u<<" 的所有出边信息："<<endl;
    for(int i=head[u];i!=-1;i=edges[i].nxt)
    {
        cout<<"( "<<u<<" -> "<<edges[i].to<<" )，权值为 "<<edges[i].weight<<endl;
    }
    /*
    初始化循环变量：首先令当前的边为第一个出发节点 u 伸出的边的索引
    循环条件：如果 i（其实就是 head[u] ）还存在边，那就继续！
    处理当前边：edges[i].to 指出发节点 u 目前使用 head[u] 边连接到的目标节点，也就是出发节点 u 的邻居
    循环终止操作：找下一条边
    */
    return;
}

signed main()
{
    memset(head,-1,sizeof(head));//请注意：这里需要初始化为 -1 ，表示目前每个节点都没被连接
    
    //由于下面就是示例了，所以就用局部变量了
    int n;//共计 n 个节点
    cin>>n;
    for(int i=1;i<=n;i++)//读入节点
    {
        int u,v,w;//出发节点和目标节点
        cin>>u>>v>>w;
        add_edge(u,v,w);
        //add_edge(v,u,w);
        //请注意：如果这张图是一张 **无向图** ，你还要把从目标节点到出发节点的边也建立起来！
    }
    for(int i=1;i<=n;i++)  traverse_nodes(i);//遍历节点 i
    exit(0);
}

提示：学到这里已经足够应对大部分算法了，链式前向星 非常不适合删除操作

断边

下面介绍如何在链式前向星数据结构上增加删除边的功能。

需要注意的是，链式前向星本质上是一种一边 只增不减 的“静态”存储方式
删除边的操作我们只能通过修改指针来“跳过”被删除的边，而不是真正将数组中的元素清除或移位。
下面提供一种物理删除的方法，即在遍历该结点的链表时找到要删除的边，然后更新前后边的指针，使该边不再被遍历到。

注意：

如果你的图中 经常需要删除边 ，链式前向星可能不是最适合的选择；
2. 如果你不要求立刻释放边的存储，也可以采用“懒删除”，在每条边中增加一个标志位表示是否有效，在遍历时跳过删除的边。

1. 增加删除边所需要的代码

假设我们在前面的加权图结构基础上（包括 to、weight 和 nxt 字段）进行扩展。我们给出一个 delete_edge 函数，函数参数为起点 u 和目标 v ，表示删除一条从 u 到 v 的边（如果存在多条，则只删除第一个碰到的）。

我们来逐步说明删除边的思路，再给出代码：

找到目标边所在的链表位置
对于某个起点 u ，其边链表保存在从 head[u] 开始的一条单链表中。我们用两个变量：
- cur 用于遍历链表，初始设为 head[u] 。
- pre 记录前驱节点的索引，初始为 -1（表示当前边是链表的第一个）。
遍历链表，搜索符合条件的边
从 cur 开始，遍历链表：如果发现 edges[cur].to==v（满足目标条件），则说明找到了要删除的边。
更新指针实现删除
- 如果 pre 为 -1，说明要删除的边正好位于链表头部，此时更新 head[u]=edges[cur].nxt；
- 否则，将前驱边的 nxt 指针更新为 edges[cur].nxt，这样跳过了当前边。
结束遍历
找到并删除后可以直接退出函数；若遍历完链表还未找到，则说明该边不存在。

下面是完整的删除边函数代码：

// 删除从 u 指向 v 的边（仅删除第一次匹配的边）
void delete_edge(int u,int v)
{
    int cur=head[u];
    int pre=-1;
    while(cur!=-1)
    {
        if(edges[cur].to==v)//找到目标边
        {
            if (pre==-1)  head[u]=edges[cur].nxt;//目标边位于链表头部，更新 head[u]
            else  edges[pre].nxt=edges[cur].nxt;//将前驱边的 nxt 指向当前边的下一条边，从而跳过 cur
            //删除成功：这里可以选择将 edges[cur].nxt 置为 -1，帮助调试（非必须）
            edges[cur].nxt=-1;
            cout<<"删除边 ("<<u<<" -> "<<v<<") 成功。"<<endl;
            return;
        }
        pre=cur;
        cur=edges[cur].nxt;
    }
    cout<<"边 ("<<u<<" -> "<<v<<") 不存在，删除失败。"<<endl;
    return;
}

2. 遍历节点，验证删除功能

为了完整展示删除操作，我们增加一个遍历函数，输出某结点所有出边的信息。这样你可以在删除前后进行对比。
（其实这已经在添加与遍历演示了）

// 遍历并输出结点 u 的所有出边（包括边的终点和权值）
void traverse_nodes(int u)//遍历出发节点 u 的所有目标节点
{
    cout<<"节点 "<<u<<" 的所有出边信息："<<endl;
    for(int i=head[u];i!=-1;i=edges[i].nxt)
    {
        cout<<"( "<<u<<" -> "<<edges[i].to<<" )，权值为 "<<edges[i].weight<<endl;
    }
    /*
    初始化循环变量：首先令当前的边为第一个出发节点 u 伸出的边的索引
    循环条件：如果 i（其实就是 head[u] ）还存在边，那就继续！
    处理当前边：edges[i].to 指出发节点 u 目前使用 head[u] 边连接到的目标节点，也就是出发节点 u 的邻居
    循环终止操作：找下一条边
    */
    return;
}

3. 示例

下面是一个完整的示例程序，展示如何添加边、删除边以及遍历输出：

/*
省略，真的太长了...
可以翻到上面看看 添加与遍历
*/

// 删除从 u 指向 v 的边（仅删除第一次匹配的边）
void delete_edge(int u,int v)
{
    int cur=head[u];
    int pre=-1;
    while(cur!=-1)
    {
        if(edges[cur].to==v)//找到目标边
        {
            if (pre==-1)  head[u]=edges[cur].nxt;//目标边位于链表头部，更新 head[u]
            else  edges[pre].nxt=edges[cur].nxt;//将前驱边的 nxt 指向当前边的下一条边，从而跳过 cur
            //删除成功：这里可以选择将 edges[cur].nxt 置为 -1，帮助调试（非必须）
            edges[cur].nxt=-1;
            cout<<"删除边 ("<<u<<" -> "<<v<<") 成功。"<<endl;
            return;
        }
        pre=cur;
        cur=edges[cur].nxt;
    }
    cout<<"边 ("<<u<<" -> "<<v<<") 不存在，删除失败。"<<endl;
    return;
}

signed main()
{
    memset(head,-1,sizeof(head));//请注意：这里需要初始化为 -1 ，表示目前每个节点都没被连接
    
    //这是张 **无向图** 
    add_edge(1,2,5);add_edge(2,1,5);
    add_edge(1,3,10);add_edge(3,1,10);
    add_edge(1,4,3);add_edge(4,1,3);
    add_edge(2,3,7);add_edge(3,2,7);
    cout<<"建边后的图"<<endl;
    for(int i=1;i<=4;i++)  traverse_nodes(i);
    delete_edge(1,3);
    cout<<"现在的图"<<endl;
    for(int i=1;i<=4;i++)  traverse_nodes(i);
    exit(0);
}

示例中的初始图长这样：
graph

程序执行过程说明

添加边阶段：
- 对于结点 1，经过多次调用 add_edge(1, ...)，其边链表可能为（头插法的结果是最新添加的边在链表头）：
  - 头部指向边：1 -> 4
  - 通过 nxt 链到边：1 -> 3
  - 再通过 nxt 链到边：1 -> 2
- 结点 2 拥有边：2 -> 3。
删除操作：
- 调用 delete_edge(1,3) 后，会遍历结点 1 的边链。
- 当遍历到边记录 edges[i].to==3 时，将其从链表中“删除”：
  - 如果该边不是头部，就把前一个边的 nxt 指向当前边的 nxt。
- 此后，遍历结点 1 时，1 -> 3 就不会再被输出。
遍历验证：
- 调用 traverse_node 验证删除后，结点 1 的链表中只剩下 1 -> 4 和 1 -> 2。

4. ASCII 图示辅助理解删除操作

假设初始结点 1 的边链如下（头插法结果，从 head[1] 开始）：

1
2
3

head[1] --> [index 2: (1 -> 4), nxt = index 1]
           [index 1: (1 -> 3), nxt = index 0]
           [index 0: (1 -> 2), nxt = -1]

删除 1->3 的过程：

遍历时，cur 先指向 index 2 (边 1->4)，不匹配；
然后 cur 指向 index 1 (边 1->3)，匹配目标。此时 pre 指向 index 2。
更新 edges[pre].nxt，即 edges[2].nxt = edges[1].nxt（即 index 0）。
结果链表变为：

1 2	head[1] --> [index 2: (1 -> 4), nxt = index 0] [index 0: (1 -> 2), nxt = -1]

删除后的遍历顺序即输出 1->4 和 1->2。

5. 小结

删除边的思路：
- 在链表中找到目标边的位置。
- 通过修改上一节点的 nxt 指针或更新 head[u]，跳过目标边，令其不参与后续遍历。
局限性：
- 这种删除操作只更新了指针，并没有真正回收数组中的空间。
- 如果后续还需要添加边，可以继续使用 add_edge，但是删除的空间不会被重用（除非重新构造数据结构）。
扩展思考：
- 如果需要频繁删除和添加，可以考虑采用“懒删除”或其他更适合动态变化的容器结构。

通过以上代码和说明，你可以在链式前向星上实现边的删除功能。

删除节点

下面讨论如何在链式前向星中实现“删除节点”的功能。
需要注意的是，与插入和删除边相比，“删除节点”更复杂，因为节点通常涉及到两部分：

删除该节点的所有出边（从该节点出发的边）， 这部分比较简单；
删除其他节点中所有指向该节点的入边， 这部分由于链式前向星只存储出边信息，需要遍历所有链表才能找到指向目标节点的边。

因此，链式前向星更适合作为静态图的存储结构，在节点（或边）频繁动态更新的场景中并不高效。如果确实需要支持节点删除，你可以考虑下面两种方法：

方法 1：物理删除（实际修改链表结构）

在物理删除时，我们需要同时删除：

节点 u 的出边（即把 head[u] 置为 -1 或清空整个链表），
其他所有节点链表中指向 u 的边。

这种方法的基本思路如下：

删除 u 的出边
直接将 head[u] 设为 -1，相当于断开了 u 对外的所有边。
删除所有指向 u 的入边
遍历图中所有其他节点 v 的边链表，在每个链表中查找边：
1
if (edges[cur].to == u)
找到后，用类似删除单链表节点的方法跳过它（更新前驱节点的 nxt 指针或更新 head[v]）。

由于链式前向星没有维护“入边”的直接索引，你必须遍历所有节点的链表来删除指向 u 的边。示例代码如下（假设图中节点编号为 1 ~ n，可以事先记录 n）：

// 物理删除节点 u：同时删除 u 的所有出边和其他所有节点指向 u 的入边
void delete_node(int u,int n)//n 表示图中总的节点数
{ 
    // 1. 删除 u 的所有出边：直接断开该链表
    head[u]=-1;
    
    // 2. 删除其他节点中指向 u 的入边
    for(int v=1;v<=n;v++)
    {
        if(v==u)  continue;//已经处理了 u 的出边
        int cur=head[v];
        int pre=-1;
        while(cur!=-1)
        {
            if(edges[cur].to==u)//找到边 v->u，需要删除
            {
                if(pre==-1)
                {
                    //被删除的边在链表头，更新 head[v]
                    head[v]=edges[cur].nxt;
                    //更新 cur 为新的头节点
                    cur=head[v];
                }
                else
                {
                    // 跳过当前边
                    edges[pre].nxt=edges[cur].nxt;
                    cur=edges[cur].nxt;
                }
                // 注意：如果存在多条边指向 u，此处可以继续遍历删除
            }
            else
            {
                pre=cur;
                cur=edges[cur].nxt;
            }
        }
    }
    cout<<"节点 "<<u<<" 删除完成 (出边和入边均已移除）。"<<endl;
    return;
}

注意事项

这种物理删除不会真正回收 edges[] 数组中存储被删除边的内存，因为该数组通常是预先分配好的。如果删除操作不频繁，空间浪费可以忽略；如果操作频繁，就需要设计一个“空闲表”来重用这些“空位”，但这会使结构变得复杂。
删除节点往往是图结构的动态操作，如果图结构频繁变更，可以考虑使用更适合动态更新的其他数据结构（例如基于链表的邻接表或其他动态容器）。

方法 2：懒删除（逻辑删除）

在很多实际场景下，动态删除节点（或边）时，我们可以采用 懒删除 的策略，而不是立即修改链表结构。方法是：

为每个节点维护一个“是否存在”的标志，例如定义一个布尔数组 nodeExist[N]。
当需要删除节点 u 时，只需将 nodeExist[u] 标记为 false
在遍历和算法中，每次遇到一个节点（或其边）时，都检查其状态，跳过那些已被标记“删除”的节点及其入边或出边。

这种方法的优点是实现简单、运行效率高，不需要遍历所有边清除指向 u 的边；缺点是图中可能还保留指向“已删除”节点的边，使用时需要小心处理。

示例代码（仅思路）：

bool nodeExist[N];

// 初始化时，将所有节点设为存在
void init(int n)
{
    for(int i=1;i<=n;i++)  nodeExist[i]=true;
    return;
}

// 懒删除节点 u，标记为不存在
void lazy_delete_node(int u)
{
    nodeExist[u]=false;
    cout<<"节点 "<<u<<" 已被标记为删除。"<<endl;
    return;
}

// 在遍历时，检查目标节点是否存在
void process_edges(int u)
{
    if(!nodeExist[u])  return;//该节点已经被删除，则不处理
    for(int i=head[u];i!=-1;i=edges[i].nxt)
    {
        int v=edges[i].to;
        if(!nodeExist[v])  continue;//如果终点已删除，则跳过该边
        // 此处对边 (u -> v) 做处理
    }
    return;
}

小结

物理删除节点：
- 将该节点的所有出边置为空（如 head[u]=-1），
- 遍历其他所有节点的边链表，删除所有指向该节点的入边。
- 需要扫描所有链表，可能比较耗时，且“删除”的边内存未回收。
懒删除（逻辑删除）：
- 通过维护一个节点存在标志，在删除节点时仅做标记。
- 在遍历和处理时跳过被删除的节点及其相关边。
- 简化了删除操作，但图中依然可能保留对已删除节点的“脏”边，使用时要特别注意。

根据你的需求选择合适的方案。如果图结构比较稳定且删除操作较少，物理删除可以使得后续算法无需额外判断；如果节点、边的动态更新较频繁，建议采用懒删除方式，并在关键操作前做过滤处理。