数据结构与算法_图结构笔记

#仅供学习

线性表中数据元素是一对一关系；树形结构中数据元素是一对多的关系；图形结构是多对多关系。

基本概念

图的存储

图的结构比较复杂，任何两个顶点之间都可能有关系。

1）如果采用顺序存储，则需要使用二维数组表示元素之间的关系，即邻接矩阵，也可以使用边集数组，把每条边顺序存储起来；

2）如果采用链式存储，则有邻接表，十字链表和邻接多重表表示方法。

还有一种是算法竞赛时经常使用的方法，链式前向星，它是邻接表和边集数组的结合。

其中，邻接矩阵和邻接表是最简单，最常用的存储方法。

1. 邻接矩阵：

    （1）无向图的邻接矩阵

（2）有向图的邻接矩阵

（3）网的邻接矩阵

        邻接矩阵的数据结构

2. 邻接表：

    邻接表（Adjacency List）是图的一种链式存储的方法。邻接表包含两部分，顶点和邻接点。顶点包括定点信息和指向第一个邻接点的指针，邻接点是包括邻接点的存储下标和指向下一个邻接点的指针。顶点vi的所有邻接点构成一个单链表。

        邻接表用到2个数据结构：

        1) 顶点节点，包括顶点信息和指向第一个邻接的指针，可用一维数组存储。

        2）邻接点节点，包括邻接点的存储下标和指向下一个邻接点的指针。顶点vi的所有邻接点构成一个单链表。

        

3. 边集数组

创建一个数组，每输入一条边，把这条边存储在数组里；

每条边存储边的两个顶点u，v,和权重w.

4. 链式前向星

链式前向星是一个静态链表存储，用边集数组和邻接表相结合，它的存储包含两种结构：

1）边集数组：edge[ ], edge[i]表示第i条边；

2）头节点数组：head[ ]， head[i]存以i为起点的第一条边的下标（在edge[ ]中的下标）