图关系-邻接关系列表的概念和特点，C/C++语言代码实现

1。邻接表的概念

邻接表（Adjacency List），顾名思义，就是通过链表连接图，或者用字段来模拟链表。关系表示法。存储方法类似于树的子字符串表示。它是一种结合了顺序分配和链式分配的存储结构。如果头节点对应的顶点有相邻顶点，则将相邻顶点存储在头节点指向的单向链表中。

如图所示：

（图中显示了图形中的关系）

示例图片显示了类似于图形的关系。节点1指向2和3，2可以指向4和5，3指向4……这样的指向表明该图是单向的，也就是说只允许1到2，而不允许2到1（除非有不是两个指向彼此的箭头）。那么根据这个指针关系，可以得到邻接表如下：

（如图所示就是邻接表）

这里需要特别注意的是，邻接表的末尾列表为空或有特殊标记表明已到达末尾。在某些需要快速表达概念的情况下，可以忽略显示空节点而不进行表达。

那么，如果是双向图，即1和2相连，可以同时从1到2，从2到1，则表格表达如下

可以看到，该双向图和单向图的邻接表表达式是不同的。双向图也表达了连接的方法。 1连接2。在节点1的连接关系中，必须添加节点2来表示1可以到2。另外，节点1必须添加到节点2来表示2可以向1移动。可以是虽然有点麻烦，但确实很划算。

具体表达为：n个顶点、e条边的连续无向图列表的表示有n个顶点表节点和2e个边表节点。 （换句话说，每条边 (i,j) 在邻居列表中出现两次：一次相对于 i，一次相对于 j）。

注意上面两张图，连接到空节点的边没有被计算在内，那么双向图的边正好是单向图的两倍。？ （点很多但边很少）有大量无效元素

b）浪费时间——数稀疏图中有多少条边

显然使用矩阵只能让我们人类更直观地观察它只是图之间的关系。对于稀疏图（即节点多但边少的图，或者表示为弱连通图），时间和空间的浪费还是很大的。邻居列表相当于改进。对于稀疏图像适应良好，可以使用更少的空间和时间来表达。

通常，邻接表的复杂度为 O(n+e)（n 为节点数，e 为边长），临界矩阵的复杂度为 O(n^2)。

3。代码组成

设计思路并不独特。您甚至可以使用结构化数组进行模拟。此代码仅提供适用于指针的单向 C++ 图形代码。想法是：将 adjvex 值赋给节点 For v 将指向下一条边的指针赋为 NULL。输入后，检查图中初始顶点所指向的第一条边的指针是否为空。如果为空，则将当前顶点的第一弧指针添加到该节点。如果不为null，则调用插入链表的insertNode方法，循环遍历链表，将节点插入到链表末尾。