所有的边用一个 e[]数组来存储, 每条边对应的索引就是其编号. 在建立邻接表时, 表中存放的实质是边的编号.
注意: 点的编号和边的编号不同
- int N,M; //N 为点的最大数量, M 为边的最大数量
- int idx; // 为当前边的编号
- int head[N],e[M],ne[M];
- head[a]; // 存放一个 a 点连接的边的编号
- e[idx]; // 抽象为表示 idx 当前边, 但结果存放的是 b 点的编号
- ne[idx]; // 表示当前编号为 idx 的边的后面一条边
- // 注意: head[a]中索引存放的是(a->b)a 点的编号
- //e[idx]的结果存放的是 (a->b) 中 b 点的编号, 表示新建一个结点
- // 其他的所有位置均表示边的编号
- void addEdge(int a,int b) // 加入一条从 a 到 b 的边
- {
- // 头插法
- e[idx] = b; // 建一个 a->b 的结点
- ne[idx] = h[a];
- h[a] = idx++;
- }
来源: http://www.bubuko.com/infodetail-3377764.html