打开网易新闻 查看精彩图片

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、邻接多重表的结构和十字链表类似。在邻接多重表中,每一条边用一个结点表示。