图的存储结构

邻接表

邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点vi建立一个单链表，把与vi相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息，把这一结点看成链表的表头，其余结点存放有关边的信息，这样的邻接表便由两部分组成： 表头结点和边表。

  • 表头结点：由所有表头结点以顺序结构的形式存储，以便可以随机访问任一顶点的边链表。表头结点包括数据域和链域两部分。链域指向与顶点vi邻接的第一个邻接点
  • 边表：由表示图中顶点间关系的2n个边链表组成。边链表中边结点包括邻接点域，数据域，链域，邻接点域指示与顶点vi邻接的点在图中的位置；数据域存储与边相关的信息；链域指示与顶点vi邻接的下一条边的结点