数组实现邻接表：构建与理解

"数组建邻接表用于表示图的结构，通过u、v、w数组记录每条边的起始顶点、结束顶点及权值，并使用first数组记录每个顶点第一条边的编号，next数组标记每条边在顶点链表中的后续边。" 在计算机科学中，图是一种数据结构，用于表示对象之间的关系。邻接表是表示图的常用方法，尤其适用于稀疏图（边的数量远小于顶点数量的平方）。在数组实现的邻接表中，每个顶点对应一个数组元素，该元素存储指向与其相连的所有边的指针或引用。这个过程通常涉及到以下步骤： 1. 初始化：创建u、v、w三个数组，分别存储每条边的起始顶点、结束顶点和权值；first数组用于存储每个顶点第一条边的编号；next数组用于链接以相同顶点为起点的多条边。 2. 编号边：读入每条边的信息，例如（1 4 9）表示从顶点1到顶点4的边，权值为9。为每条边按读入顺序分配唯一的编号，如1、2、3等。 3. 存储边信息：将边的起始顶点、结束顶点和权值存入u、v、w数组中，对应的数组下标为边的编号。 4. 更新first数组：根据边的起始顶点更新first数组。例如，第一条边（1 4 9）的起始顶点为1，将first[1]设置为1，表示1号顶点的第一条边编号为1。 5. 使用next数组：当有多个边以相同顶点为起点时，next数组记录这些边之间的关联。如果某条边是其顶点的第一条边，next数组对应的值设为-1，否则记录下一条边的编号。 举例来说，读入第二条边（4 38），将其信息存入相应数组，编号为2，first[4]设为2，因为这是4号顶点的第一条边，next[2]设为-1。 继续这个过程，直到所有边都被处理。这样构建的邻接表在遍历图的边时效率较高，只需要遍历每个顶点对应的first数组和next数组即可。对于稀疏图，这种数据结构节省了大量的空间，因为它只存储实际存在的边，而不是所有可能的边。在处理大规模图问题时，数组实现的邻接表是优选的数据结构。