链式前向星建图

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

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

邻接矩阵实现：

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[]需要重新置0
  fill(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;
}