菜鸟笔记
提升您的技术认知

图的存储结构(邻接表)-ag真人游戏

为什么要采用邻接表:

对于边数相对顶点较少的图,这种结构无疑是存储空间的极大浪费。

所以把数组和链表结合起来存储,这种方式在图结构中适用,称为邻接表(adjacencylist)

邻接表的处理方法如下:

-顶点用一个一位数组存储(也可以用单链表存储),但数组可以比较容易的读取。

-每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不确定,所以要选择单链表存储。

邻接表(无向图)

邻接表(有向图)

有向图有两种:

1.把顶点当弧尾建立的邻接表,这样就很容易得到每个顶点的出度,如下图所示:

如果要确定顶点入度,可以建立逆邻接表:

如下图所示:

对于带权值的网图,可以在边表结点定义中再增加一个数据域来存储权值

如下图所示:

网站地图