链式前向星

关于存图方式常用的有两种

第一种 邻接矩阵

直接暴力存图

int u, v, w;
cin >> u >> v >> w;
a[u][v] = w;

即意为在\(u\)与\(v\)之间连上一条权值为\(w\)的边

也可以借助\(vector\)来存储，但是\(vector\)容易被卡，不建议用

vector<int>q[N];
for (int i = 1; i <= m; ++ i) {
   int u, v, w;
   cin >> u >> v;
   q[u].push_back(v);
}

在\(u\)节点的后面新开一个小空间 存\(v\)，表示\(u\)，\(v\)之间有边

以上存无边权的，下面的\(pair\)类型的\(vector\)是存储有边权的

vector<pari<int,int> >q[N];
for (int i = 1; i <= m; ++ i) {
   int u, v, w;
   cin >> u >> v >> w;
   q[u].push(make_pair(v, w));
}

第二种 邻接表

也就是 链式前向星

链式前向星的原理是通过某种合法又合理的操作，使得整个图联动起来

写链式前向星，一般都是以下格式

struct edge {
   int frm, to, val, nxt;
}e[N];int cnt, head[N];

其中\(cnt\)存边的编号，\(head[x]\)表示\(x\)这个节点最后一次加入的边的编号是多少(也可以理解为以\(x\)为起点最后一次加入的边的编号）

结构体中的\(e[i]\)表示\(i\)这条边的各种信息

\(e[i].frm\) 表示\(i\)这条边的起点是哪里

\(e[i].to\)表示\(i\)这条边的终点是哪里

\(e[i].val\) 表示\(i\)这条边的权值是多少

\(e[i].nx\)t 表示与\(i\)这条边起点相同的上一条边的编号是多少

对于新加入的边，我们首先\(cnt\)(边的编号)要递加

其次我们对于这条边，更新他的各种信息:

inline void add (int u, v, w) {
   e[++cnt].frm = u;
   e[cnt].to = v;
   e[cnt].val = w;
   e[cnt].nxt = head[u];
   head[u] = cnt;
}

上边那个函数表示cnt这条边的起点是u，终点是v，权值是w

我们考虑如何来理解这个nxt与head数组

我们这条边的共起点的上一条边必定是我们这条边的起点最后一次加入的一条边（有点绕）

如下:

对于1 2 1这条边

\(edge[1].to = 2;edge[1].nxt = 0;head[1] = 1;\)

对于2 3 2这条边

\(edge[2].to = 3;edge[2].nxt = 0;head[2] = 2;\)

对于3 4 3这条边

\(edge[3].to = 4;edge[3].nxt = 0;head[3] = 3;\)

对于1 3 4这条边

\(edge[4].to = 3;edge[4].nxt = 1;head[1] = 4;\)

对于4 1 5这条边

\(edge[5].to = 1;edge[5].nxt = 0;head[4] = 5;\)

对于1 5 6这条边

\(edge[6].to = 5;edge[6].nxt = 4;head[1] = 6;\)

对于4 5 7这条边

\(edge[7].to = 5;edge[7].nxt = 5;head[4] = 7;\)

所以我们的\(i\)这条边的\(nxt\)（与\(i\)共起点的上一条边的编号）就是\(head[x]\) (\(x\)这条边最后一次加入的边的编号)(未更新前的)

当我们这条边信息更新完了之后，再去更新\(head\)数组

再次回想\(head\)数组定义，以\(x\)为顶点最后一次加入的边，不就是当前这条边的编号吗

顾:

e[i].nxt = headx[x];
head[x] = cnt;

\(End..\)

---

8.31 update:

现在常用数组版本：

int to[N << 1], len[N << 1], nex[N << 1], head[N << 1], cnt;

inline void add(int x, int y, int z)
{
   to[++ cnt] = y;
   len[cnt] = z;
   nex[cnt]= head[x];
   head[x] = cnt;
   return;//随手打return是个好习惯
}