【图论 | 数据结构】用链式前向星存图（保姆级教程，详细图解+完整代码）

一、概述

链式前向星是一种用于存储图的数据结构，特别适合于存储稀疏图，它可以有效地存储图的边和节点信息，以及边的权重。

它的主要思想是将每个节点的所有出边存储在一起，通过数组的方式连接（类似静态数组实现链表）。这种方法的优点是存储空间小，查询速度快，尤其适合于处理大规模的图数据，在一些笔试或者竞赛的场景中经常使用。

下面，我们用这张图来图解一下链式前向星的存储逻辑：

二、前置准备

注意看这里的设定，以及我加粗的提示。

1. head数组：head[i]存储的是节点i的第一条边的编号。这样，我们可以通过head[i]快速找到从节点i出发的所有边。

2. next数组：next[j]存储的是编号为j的边的下一条边的编号。这样，我们可以通过next[j]快速找到从同一个节点出发的下一条边。

3. to数组：to[j]存储的是编号为j的边的终点节点编号。这样，我们可以通过to[j]快速找到边j的终点，也就是这条边要去往哪里。

4. weight数组：weight[j]存储的是编号为j的边的权重。这样，我们可以通过weight[j]快速找到边j的权重。

5. cnt变量：cnt用于存储边的数量，也表示边的编号。每添加一条边，cnt就会增加1。这样，我们可以通过cnt快速知道当前图中边的数量，同时我们也认为cnt是新添加边的编号。

三、初始化

public static void build(int n) {cnt = 1; // 边从1开始编号Arrays.fill(head, 1, n + 1, 0); // head[1 ... n] 全设为 0
}

在链式前向星中，我们使用cnt来作为边的编号，由于边的编号是从1开始的，所以初始化时我们将cnt设置为1。同时，将head数组的所有元素设置为0。因为head[i]存储的是节点i的第一条边的编号，所以，如果节点i没有出度（即没有从节点i出发的边），那么head[i]就应该为0。初始化时所有节点都没有出度，后续在添加边的时候，会更新对应的head[i]的值。

四、添加边（重点）

在链式前向星中添加边的操作是最核心的，它涉及到head、next、to、weight数组的更新，以及边的编号cnt的自增。

在看代码之前，我们先回顾一下各个结构的下标以及值的含义：

1. head数组：下标i表示节点编号，值head[i]表示从节点i出发的第一条边的编号。

2. next数组：下标j表示边的编号，值next[j]表示编号为j的边的下一条边的编号。

3. to数组：下标j表示边的编号，值to[j]表示编号为j的边的终点节点编号。

4. weight数组：下标j表示边的编号，值weight[j]表示编号为j的边的权重。

结合上述含义，我们来看代码就很清晰了：

// (u, v, w): 有一条边，从u节点指向v节点，权重为w
// 在每一次添加边时，cnt都表示当前未分配的边的编号，添加边后cnt需++
public static void addEdge(int u, int v, int w) {next[cnt] = head[u];to[cnt] = v;weight[cnt] = w;head[u] = cnt;++cnt;
}

首先，我们需要更新next数组。next[cnt]存储的是编号为cnt的边的下一条边的编号。在添加新边时，我们将新边的next置为旧的头边号head[u]，这样就可以通过next[cnt]快速找到从节点u出发的下一条边。

然后，我们需要更新to数组，将新边的终点设置为v，这样就可以通过to[cnt]快速找到边cnt的终点。

更新weight数组也很自然，就是将新边的权重设置为w，最后，我们将节点u的头边号修改为当前新边的编号，这样就可以通过head[u]快速找到从节点u出发的第一条边。

备注：记得每添加一条边，边的编号cnt就需要增加1

五、建图

建图分为有向图与无向图，输入的参数是一个二维数组edges作为输入，这个数组的每个元素都是一个长度为3的数组，代表一条边的两个端点和这条边的权重。

// 建有向图
public static void directGraph(int[][] edges) {for (int[] edge : edges) {addEdge(edge[0], edge[1], edge[2]); // 添加有向边