一、前言我们常见的内存映射数据结构有两种。 一个是邻接矩阵，另一个是邻接表。 另一方面，在邻接矩阵中，空间的复杂度为o(n2 ) o ) n^2) o(n2 )，在稀疏图的情况下，与邻接表相比，浪费了很多空间。 由于普通邻桌使用链表操作，不方便竞争，zxdjqm基于邻桌发明了这种简单易操作的结构——链式前星
二、邻表由于链式正向星从邻表(链表)发生变化，邻表为存储图的边集，让我们简单回想一下邻表(具体内容不展开) )。
以下为图G 1、G 2 G_1、G_2 G1、G2 :
邻接表的节点结构如下。
上图中的adjvex是相邻点，即边的终点。 nextarc连接到同一起点的下一个节点； info保存边的长度等信息，firstarc连接与该点对应的第一边(因为是头插入法，所以最后插入的边)。
于是，由G 1、G 2 G_1、G_2 G1、G2得到的邻接表示如下(info域在图中省略)。
相邻表在每次插入节点时使用头插法。
三、链式前星简单想起旁边的列表后，我们开始介绍竞赛中图论常用的内存图结构——链式前星(正文来了)。
有了旁边桌子的思想，链式前星非常容易理解。 从宏观上讲，只需要将链表改为数组即可。 具体介绍如下。
首先，写链式前向星的数据结构和带边的代码。
namespace G{//数据结构int to[MAXM]、head[MAXN]、nxt[MAXM]、tot； voidaddedge(intu，int v，int w )/u，v，w分别表示边缘的起点、终点、边缘权to(tot )=v； adjvex域val[tot]=w； 填写info域。 在此，边界权nxt[tot]=head[u]； //连接下一个节点的head[u]=tot； //头指针移动}}代码中的to对应于邻表中的adjvex域，w对应于info域，nxt对应于nextarc域，head对应于头指针firstarc域，并对附加边缘代码功能进行了评论
最后，链式前向星可以像链表一样使用。 希望你在竞赛中取得好成绩。