链式前向星建图

回顾邻接局矩阵和邻接表建图：

​ 在之前的图论基础中，我们提到了两种建图方式：邻接矩阵、邻接表。

邻接矩阵实现：

int N; //所有节点个数
int Graph[N][N];
for(int i : Numbers){  //Numbers表示所有节点for(int j : Neighbors) {// Neighbors表示节点i的所有邻接节点Graph[i][j] = 1;  // 无权图：Graph[i][j] = 1代表存在边(i,j)Graph[i][j] = weight // 有权图：Graph[i][j] = weight 代表存在边(i,j)并且此边权重为weight}
}

邻接表实现：

int N;
vector<vector<int>> Graph(N); //无权图
vector<vector<pair<int,int>>> Graph(N); //有权图
for(int i : Numbers){for(int j : Neighbors){Graph[i].push_back(j);	//无权图: Graph[i]中存在j，则说明存在边(i,j)Graph[i].push_back(make_pair(j,weight))/有权图：Graph[i]中存在{j,weight}，说明存在边(i,j)并且权重为weight}
}

这两种表示图的方式在比赛中效率有所欠佳，我们现在来学习一个在$ACM$比赛中常用的表示图的方式：链式前向星。【空间要求严苛情况下】

链式前向星建图

链式前向星建图要用到三个数组和一个int型变量$cnt$(记一个图中节点数为$N$，边数为$M$)：

1. head[N+1]：head[]下标为节点编号【节点编号从1开始，所以head[0]我们舍弃不用】，head[i]存储的是编号$i$节点的头部边编号（如果为0，说明节点$i$无出向边）。
2. next[M+1]：next[]下标为边编号【边编号也是从1开始】，next[i]存储的是编号$i$边对应的下一条边的编号（如果为0，说明无对应的下一条边）。
3. to[M+1]：to[]下标为边编号【边编号从1开始】，to[i]存储的是编号$i$边指向的节点的编号。（有边就会有对应的指向节点，所以to[i]为$0$说明无编号为$i$的边）。
4. int cnt：记录建图过程中已经建好的边数，如果cnt为$r$，说明已经建好了$r$条边，最终cnt为$m$，说明此图中有m条边。

示例：

现在我们来看一个链式前向星建图的详细操作示例：

图中节点和边如下图：

​

【注意】链式前向星建图是需要提前知道边数的，根据边来建图。

​ 现在我来建立$1$号边$(1,3)$，此时cnt ++，cnt变为1，$1$号节点是边的出射点，所以要更新$1$号节点的头部边，$1$节点原来并没有头部边（没有出现过$1$号节点座位出射点的边），其head[1] = 0，所以要执行head[1] = 1操作，但是在此之前，我们需要更新next[1]，next[1]表示 $1$号边对应的下一条边，也就是$1$节点原来的头部边。最近记录$1$号边的指向点to[1] = 3。 总的来说，我们需要执行一下操作（有顺序）：

cnt++; // 0 -> 1
next[1] = head[1];
head[1] = 1;
to[1] = 3;

​ 现在建立$2$号边$(4,3)$，cnt++，cnt变为2，$4$号节点是边的出射点，所以要更新$4$号节点的头部边，在此之前更新$2$号边对应的下一条边，next[2]表示$2$号边对应的下一条边，也就是$4$节点原来的头部边。最近记录$2$号边的指向点to[2] = 3。同样执行一下操作：

cnt++;//1 -> 2
next[2] = head[4];
head[4] = 2;
to[2] = 3;

​ 现在建立$3$号边$(2,4)$，cnt++，cnt变为3，$2$号节点是边的出射点，所以要更新$2$号节点的头部边，在此之前更新$3$号边对应的下一条边，next[3]表示$3$号边对应的下一条边，也就是$2$节点原来的头部边。最近记录$3$号边的指向点to[3] = 4。同样执行一下操作：

cnt++;//2 -> 3
next[3] = head[2];
head[2] = 3; 
to[3] = 4;

​ 现在建立$4$号边$(1,2)$，cnt++，cnt变为4，$1$号节点是边的出射点，所以要更新$1$号节点的头部边，这里$1$号节点的头部边不再为0，而是$1$号边，所以next[4] = head[1] = 1，之后更新head[1] = 4。最近记录$4$号边的指向点to[4] = 2。

cnt++;//3->4
next[4] = head[1];
head[1] = 4;
to[4] = 2;

现在能发现链式前向星建图的规律以及通式了吧，其实就是下面这段代码：

// 加入边 (发射点i, 入射点j)
cnt++;
next[cnt] = head[i];
head[i] = cnt;
to[cnt] = j;

三种方式建图代码合集：

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>using namespace std;const int MAXN = 10000;  // 节点个数最大值
const int MAXM = 1000;   // 边的条数最大值// 邻接矩阵方式
int Graph1[MAXN + 1][MAXN + 1];  // 静态最大空间// 邻接表方式  只能用动态结构去实现
vector<vector<pair<int, int>>> Graph2Direction(MAXN + 1);// 链式前向星方式
vector<int> head(MAXN + 1, 0);
vector<int> nextEdge(MAXM + 1, 0);
vector<int> to(MAXM + 1, 0);
vector<int> weightEdge(MAXM + 1, 0);  // 需要权重
int cnt = 0;                          // 表示已经建立好了的边数// 对图的三种实现方式分别初始化，以便之前的实例不用影响下一个实例
void build() {// 邻接矩阵初始化memset(Graph1, 0, sizeof(Graph1));// 邻接表初始化Graph2Direction.assign(MAXN + 1, vector<pair<int, int>>());// 链式前向星初始化cnt =0;  // 边数为0，说明建图重新开始,next[],to[]都会被覆盖,head[],weight[]需要重新置0fill(head.begin(), head.end(), 0);fill(weightEdge.begin(), weightEdge.end(), 0);
}// 链式前向星加边
void addEdge(int u, int v, int weight) {cnt++;nextEdge[cnt] = head[u];to[cnt] = v;head[u] = cnt;weightEdge[cnt] = weight;
}// 三种方式建立有向有权图
void directGraph(const vector<vector<int>>& edges) {  // m条边int m = edges.size();// 邻接矩阵建图for (int i = 0; i < m; i++) {int u = edges[i][0];int v = edges[i][1];int w = edges[i][2];Graph1[u][v] = w;}// 邻接表建图for (int i = 0; i < m; i++) {int u = edges[i][0];int v = edges[i][1];int w = edges[i][2];Graph2Direction[u].push_back(make_pair(v, w));}// 链式前向星建图for (int i = 0; i < m; i++) {int u = edges[i][0];int v = edges[i][1];int w = edges[i][2];addEdge(u, v, w);}
}// 三种方式建立无向有权图
void undirectGraph(const vector<vector<int>>& edges) {int m = edges.size();// 邻接矩阵建图for (int i = 0; i < m; i++) {int u = edges[i][0];int v = edges[i][1];int w = edges[i][2];Graph1[u][v] = w;Graph1[v][u] = w;}// 邻接表建图for (int i = 0; i < m; i++) {int u = edges[i][0];int v = edges[i][1];int w = edges[i][2];Graph2Direction[u].push_back(make_pair(v, w));Graph2Direction[v].push_back(make_pair(u, w));}// 链式前向星建图for (int i = 0; i < m; i++) {int u = edges[i][0];int v = edges[i][1];int w = edges[i][2];addEdge(u, v, w);addEdge(v, u, w);}
}// 现在对三种建图方式建成的图进行遍历
void travse(int N)  // N为图中节点个数
{printf("邻接矩阵:\n");for (int i = 1; i <= N; i++) {printf("%d (邻居，边权): ", i);for (int j = 1; j <= N; j++) {if (Graph1[i][j] != 0) {printf("(%d,%d) ", j, Graph1[i][j]);}}printf("\n");}printf("邻接表:\n");for (int i = 1; i <= N; i++) {printf("%d (邻居，边权): ", i);for (const auto& p : Graph2Direction[i]) {printf("(%d,%d) ", p.first, p.second);}printf("\n");}printf("链式前向星:\n");for (int i = 1; i <= N; i++) {printf("%d (邻居，边权): ", i);for (int ei = head[i]; ei > 0; ei = nextEdge[ei]) {printf("(%d,%d) ", to[ei], weightEdge[ei]);}printf("\n");}
}int main() {int n1 = 4;vector<vector<int>> edges = {{1, 3, 6}, {2, 4, 2}, {4, 3, 4}, {1, 2, 8}, {4, 3, 3}};build();directGraph(edges);travse(n1);return 0;
}