一、概念

邻接表是一个顺序存储与链式存储相结合的数据结构,用于描述一个图中所有节点之间的关系。

若是一个稠密图,我们可以选择使用邻接矩阵;但当图较稀疏时,邻接矩阵就显得比较浪费空间了,此时我们就可以换成邻接表。

邻接表的逻辑结构有些类似于哈希桶,都是由数组与链表相结合的结构。一维数组存储结构体元素,结构体中需要包含每个节点的编号以及一个指针域,指针指向后续的所有邻接点

下面是邻接表的逻辑结构示意图(无向图):

【数据结构】邻接表-LMLPHP

可以看到,我们只需要顺着每个链表,就可以找到图中所有的边。但是对于无向图而言,还是存在一定的数据冗余情况,每条边都被记录了两次

因为邻接表的数组存放了所有的节点,我们又可以将其称为顶点数组。邻接表的实现方式有很多种,只要能够描述出所有节点与这些节点对应的所有边就是一个邻接表

二、数组实现邻接表

在做题的时候,为了效率,我们常常采用数组来模拟邻接表。但是数组实现邻接表的方式也五花八门,这里以y总同款邻接表和有向图为例

int e[N], ne[N], h[N], idx;

void add(int a, int b) // 将a指向b的边加入邻接表
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

起初我看到这种实现邻接表的方式完全摸不着头脑,在一番研究后大致理解了其原理,希望能够对大家有所帮助

首先我们大致了解一下这段代码中不同的数组和变量代表了什么:

  • a:出发点
  • b:边指向的节点 
  • h:下标为节点编号,其中的元素存放对应节点的第一条出边编号,需要被初始化为-1
  • e:存放每条边指向的节点编号
  • ne:存放同一节点的下一条出边的编号
  • idx:边的编号

用数组模拟邻接表的大致思路是,将第i个节点的第一条出边编号放到h[i]中,通过h[i]能够取出其编号,用这个编号访问e[h[i]]就能够得到这条边指向的节点,此时我们就得到了一条完整的边;再用这个编号访问ne[h[i]]就能够得到同一节点的下一条出边编号。顺着这个逻辑我们就可以访问一个节点所有的出边

要使用数组实现的邻接表也很简单,我们只需要选择自己想要访问的节点i,然后得到节点i的第一条出边编号h[i],通过e[h[i]]得到这条出边指向的节点,接着通过ne[h[i]]得到节点i的下一条出边编号

不要忘了数组h一开始被初始化为-1,因此我们通过循环不断访问出边编号,直到当我们访问到-1时就说明节点i的所有出边已经全部访问完毕

因为所有的边都有自己的编号,我们是通过使用编号来访问这条边的尾和下一条边的,在数组模拟实现邻接表中边的编号非常重要!如果不能理解编号的作用就不能很好的理解数组模拟邻接表的原理。

如果看了上面还不是很理解,接下来是详细过程:

第一步,我们按顺序对所有的边进行编号

【数据结构】邻接表-LMLPHP

idx初始值为0,因此我们正好从0开始一个个将边存进邻接表

第0条边指向的节点,我们存进e[idx]中,并将h[a]即节点a的第一条出边编号赋值给ne[idx],然后将h[a]修改为第0条边的编号。此时第0条边变为节点a的第一条出边,最后idx++变成下一条边的编号

也就是说,节点i的第一条出边编号h[i]是一直在被更新的,每有一条新出边存入邻接表,对应节点的h[i]就会被更新为这条边的编号,而原来的h[i]就变为这条新出边的下一条出边编号,存进了ne[h[i]]中

【数据结构】邻接表-LMLPHP

最后idx++变为1,开始存下一条边

【数据结构】邻接表-LMLPHP

到这里相信大家已经明白如何将边存入邻接表了

以上面的例子为例,此时节点0的出边已经全部存入邻接表。我们通过访问h[0]就能得到节点0的第一条出边编号1,然后获取到其指向的节点e[h[0]]即节点2,通过ne[h[0]获取到其下一条出边编号0

最后编号会变为-1,此时说明该节点的所有出边已经遍历完毕

完.

10-13 08:06