7.2 图的存储结构

01数组表示法

1、用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

2、以二维数组表示有n个顶点的图时，需存放n个顶点信息和n的平方个弧信息的存储量。

3、对于有向图，第i行的元素之和为顶点vi的出度OD（vi），第j列的元素之和为顶点vi的入度ID（vi）。

02邻接表

1、邻接表（Adjacency List）是图的一种链式存储结构。

2、在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。

3、在表头结点中，除了没有链域（firstarc）指向链表中第一个结点之外，还设有存储顶点vi的名或其他有关信息的数据域（data）

03十字链表

1、十字链表是有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。

2、在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。

3、在弧结点中有5个域，其中尾域和头域分别指示弧尾和弧头这两个顶点。

04邻接多重表

1、邻接多重表是无向图的另一种链式存储结构。

2、虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息。但是由于邻接表中每一条边有两个结点，这给某些图的操作带来不便。

3、邻接多重表的结构和十字链表类似。在邻接多重表中，每一条边用一个结点表示。

C语言 | 温度转换（1）​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/338748730