【数据结构】邻接表
一、概念
邻接表是一个顺序存储与链式存储相结合的数据结构，用于描述一个图中所有节点之间的关系。
若是一个稠密图，我们可以选择使用邻接矩阵；但当图较稀疏时，邻接矩阵就显得比较浪费空间了，此时我们就可以换成邻接表。
邻接表的逻辑结构有些类似于哈希桶，都是由数组与链表相结合的结构。一维数组存储结构体元素，结构体中需要包含每个节点的编号以及一个指针域，指针指向后续的所有邻接点
下面是邻接表的逻辑结构示意图（无向图）：
可以看到，我们只需要顺着每个链表，就可以找到图中所有的边。但是对于无向图而言，还是存在一定的数据冗余情况，每条边都被记录了两次
因为邻接表的数组存放了所有的节点，我们又可以将其称为顶点数组。邻接表的实现方式有很多种，只要能够描述出所有节点与这些节点对应的所有边就是一个邻接表
二、数组实现邻接表
在做题的时候，为了效率，我们常常采用数组来模拟邻接表。但是数组实现邻接表的方式也五花八门，这里以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的所有出边已经全部访问完毕了
因为所有的边都有自己的编号，我们是通过使用编号来访问这条边的尾和下一条边的，在数组模拟实现邻接表中边的编号非常重要！如果不能理解编号的作用就不能很好的理解数组模拟邻接表的原理。
如果看了上面还不是很理解，接下来是详细过程：
第一步，我们按顺序对所有的边进行编号
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]]中
最后idx++变为1，开始存下一条边
到这里相信大家已经明白如何将边存入邻接表了
以上面的例子为例，此时节点0的出边已经全部存入邻接表。我们通过访问h[0]就能得到节点0的第一条出边编号1，然后获取到其指向的节点e[h[0]]即节点2，通过ne[h[0]获取到其下一条出边编号0
最后编号会变为-1，此时说明该节点的所有出边已经遍历完毕
完.
原文地址：https://blog.csdn.net/Eristic0618/article/details/142768112
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！