前言
我们在之前的一篇文章中已经提到了图的表示：图的表示？关联矩阵、邻接矩阵、邻接链表。其中提到了一种方法，叫做邻接链表。
邻接链表，顾名思义，就是将所有与某个结点相邻的结点收集起来，一一添加在一条单链表上面。这种方法相对于邻接矩阵而言大大节约了内存空间。
但有时候我们不太喜欢使用链表来存储，因为这样显得不太方便。所以，我们可以尝试使用数组来实现邻接链表。那么如何实现呢？
如何实现
我们假设给出的图是 a，b，w，表示结点a与b相连，边ab的权值为w。那么我们可以尝试给每一条边进行编号，比如第一条边编号为1（或者为0），后面的边依次累加。
定义三个数组即可：
- e：即edge，边。
e[i]表示编号为i的边所指向的结点（就是结点b的位置）。 - ne：即next_edge，下一条边。
ne[i]表示编号为i的边的下一条边。 - h：即head，头结点中包含的边。
h[i]表示结点i的最后添加的一条边的编号，就相当于在单链表头部插入新的头结点。
如何添加一条边
首先我们要为每一条边进行编号，可以使用全局变量来实现，每添加一条边就将其加一。然后再想如何添加，比如我们需要添加的一条边是 a，b，w，边的编号为idx，那么：
-
e[idx] = b;//由于每一条边都是唯一，并且累加，所以e[idx]是初次赋值。表示边idx的另一头是结点b。 -
ne[idx] = h[a];//同上，ne[idx]也是初次赋值。但其表示的是边idx的下一条边是之前刚刚添加的那一条边（被挤掉的头结点）。 -
h[a] = idx++;//将当前插入的边作为最后插入的边，也就是最新的边。
如何遍历
对于给出的一个结点a，我们可以通过for (int edge = h[a]; edge != -1; edge = ne[edge]) child = e[edge] 来进行遍历与其相邻的每一个结点。如果给出的图是连通图，那么我们就可以通过给出的任意一个结点访问到图中的所有结点，当然这个过程需要我们自己控制重复访问的问题。这样，就达到了用数组实现邻接链表的效果。
测试代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000;
int e[N]; //edge,e[i]表示标号为i的边的指向的结点
int ne[N]; //next_edge,ne[i]表示标号为i的边的下一条边的编号
int h[N]; //head,h[i]表示结点i的最后添加的一条边的编号(相当于邻接链表头结点)
int idx; //index,边的标号，一般可以从0或1开始
//添加一条从a到b的边
void add(int a, int b) {
e[idx] = b; //边idx指向结点b
ne[idx] = h[a]; //边idx的下一条边为之前最后添加的边(相当于在单链表头部插入新结点)
h[a] = idx++; //更新当前边为最后添加的边
}
void init() {
for (int i = 0; i < N; ++i) {
e[i] = ne[i] = h[i] = -1;
}
idx = 0; //边的编号可以从0或者1开始
}
int main() {
int n, a, b;
while (1) {
init();
cout << "初始化完成，请输入边的数量：" << endl;
cin >> n;
cout << "请输入" << n << "条边，以空格或回车分隔" << endl;
while (n--) {
cin >> a >> b;
add(a, b);
}
for (int i = 0; i < N; ++i) {
if (h[i] == -1) continue;
cout << "node " << i << ": ";
for (int j = h[i]; j != -1; j = ne[j]) { //j为结点i下的每一条边
cout << e[j] << " ";
}
cout << endl;
}
cout << endl;
}
}