图

图是一种比较复杂的数据结构，这是一种网状结构，并且任何数据都可以用图来表示

图的相关概念

1）有向图

如果图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也被称为弧，将边的始点称为弧尾，将边的终点称为弧头。

2）无向图

如果图中的每条边都是没有方向的，这种图被称为无向图。无向图中的边都是顶点的无序对，通常用圆括号来表示无序对。

3）顶点

通常将图中的数据元素称为顶点，通常用v来表示顶点的集合。

4）完全图

如果无向图中的任意两个顶点之间都存在着一条边，则将此无向图称为无向完全图。如果有向图中的任意两个顶点之间都存在着方向相反的两条弧，则将此有向图称为有向完全图。

结论：包含n个顶点的无向完全图有n(n-1)/2条边，包含n个顶点的有向完全图有n(n-1)条边。

5）稠密图和稀疏图

当一个图接近完全图时便称为稠密图，反之将含有较少的边数（即当e<<n(n/2)）的图称为稀疏图。

6）权和网

图中每一条边（弧）都可以有一个相关的数值，将这种与边相关的数值称为权。权能够表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。

7）子图

假设存在两个图 G=( V， E) 和 G’=( V’， E’ )，如果V’是V的子集（ 即 V’⊆ V），并且E’是E的子集（即E’ ⊆ E），则称G’是G的子图。

8）邻接点

在无向图 G ＝( V， E) 中，如果边( vi， vj) ∈ E，则称顶点vi和vj互为邻接 点（ adjacent）；边( vi， vj) 依附于顶点 vi 和 vj， 即 vi 和 vj 相关联。

9） 顶点的度

顶点的度是指与顶点相关联的边的数量。在有向图中，以顶点 vi 为弧尾的弧的值称为顶点 vi 的出度，以顶点 vi 为弧头的弧的值称为顶点vi的入度，顶点 vi 的入度与出度的和是顶点 vi 的度。

10）路径

如果图中存在一个从顶点vi到顶点vj的顶点序列，则这个顶点序列被称为路径。在图中有如下两种路径。

• 简单路径：指路径中的顶点不重复出现。
• 回路或环：指如果路径中除第一个顶点和最后一个顶点相同以外，其余顶点不重复。一条路径上经过的边的数目称为路径长度。

11）连通图和连通分量

在无向图G中，当从顶点vi到顶点vj有路径时vi和vj是连通的。

12）强连通图和强连通分量

13）生成树

一个连通图的生成树是指一个极小连通子图，虽然它含有图中的全部顶点，但只有足已构成一棵树的n-1条边。

一棵有n个顶点的生成树有且仅有n-1条边，如果它多于n-1条边，则一定会有环。但是有n-1条边的图不一定是生成树，如果一个图有n个顶点和小于n-1条边，则该图一定是非连通图。

14）无向边和顶点关系

存储结构

构建数据结构的最终目的是存储数据，除了存储图中各个顶点本身的信息之外，还要存储顶点之间的所有关系。存储结构有3种，分别是邻接矩阵、邻接表和十字链表。

图我的理解还是不够，我发现数据结构的存储基本都是以链式存储方式的，所以打算再次学习线性表。