数组模拟建立邻接表

佚名 4年前 (2020-01-12) 算法 1499人围观抢沙发百度已收录

所有的边用一个e[]数组来存储，每条边对应的索引就是其编号。在建立邻接表时，表中存放的实质是边的编号。

注意：点的编号和边的编号不同

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 int N,M; //N为点的最大数量，M为边的最大数量
 2 int idx; //为当前边的编号
 3 int head[N],e[M],ne[M];

 4 head[a]; //存放一个a点连接的边的编号
 5 e[idx]; //抽象为表示idx当前边,但结果存放的是b点的编号
 6 ne[idx]; //表示当前编号为idx的边的后面一条边
 7 
 8 //注意:head[a]中索引存放的是(a->b)a点的编号
 9 //e[idx]的结果存放的是(a->b)中b点的编号,表示新建一个结点
10 //其他的所有位置均表示边的编号
11 
12 void addEdge(int a,int b)    //加入一条从a到b的边
13 {
14     //头插法
15     e[idx] = b;    //建一个a->b的结点
16     ne[idx] = h[a];
17     h[a] = idx++;
18 }