图

图

非线性表结构。

基本概念

• 顶点：图中的元素称为顶点。

• 边：顶点与顶点之间的连接关系。

• 路径：从一个顶点到另一个顶点的顶点序列。包含两个顶点。

• 路径长度：路径上边的个数。

• 简单路径：顶点不重复出现的路径，称为简单路径。

• 环：第一个顶点和最后一个顶点相同的路径，称为回路或者环。

• 简单环：除了第一个和最后一个顶点，其余顶点都不重复出现的环，称为简单环。

• 度：跟顶点相连接的边的条数。

• 无向图：边没有方向的图称为无向图。

• 有向图：边有方向的图称为有向图。

• 入度：有向图中，有多少条边指向这个顶点。

• 出度：有向图中，有多少条边是以这个顶点为起点，指向其它顶点。

• 带权图：每条边都有一个权重的图。

• 简单图：在图中，若不存在某顶点到其自身的边，且不存在重复的边，则称之为简单图。

• 无向完全图：在无向图中，若任意两顶点之间存在边，则称之为无向完全图。边的个数为n(n-1)/2。

• 有向完全图：在有向图中，若任意两顶点之间存在方向相反的两条边，则称之为有向完全图。边的个数为n(n-1)。

• 连通图：无向图中，任意两个顶点都有路径相通，称为连通图。

• 强连通图：有向图中，任意两个顶点都有路径相通，称为强连通图。

• 连通网：带权重的连通图，称为连通网。

• 生成树：一个连通图的生成树，是指一个连通子图，它包含图中的所有n个顶点，但只有n-1条边。

• 最小生成树：连通网的所有生成树中，所有边权重和最小的生成树，称为最小生成树。

邻接矩阵存储方式

邻接矩阵使用的是二维数组。

• 对于无向图，如果顶点i和j之间有边，就将A[i][j]和A[j][i]标记为1。

• 对于有向图，如果有一条边，从顶点i指向顶点j，就将A[i][j]标记为1。

• 对于带权图，数组中存储的是权重。

缺点：

• 会造成空间浪费。无向图只需要对角线划分的一半。如果是稀疏图，顶点很多但是边不多，会很浪费存储空间。

优点：

• 存储方式简单。

• 获取值时非常高效。

• 运算简单，可以将图的运算转换成矩阵的运算。

邻接表的存储方式

有点类似于散列表。

• 对于无向图，每个链表存储的是与这个顶点连接的其它顶点。

• 对于有向图，每个链表存储的是这个顶点指向的其它顶点。

缺点：

• 查询顶点关系时，比较消耗时间。

优点：

• 比较节省空间。

优化：

可以将链表换成其它动态数据结构，如平衡二叉查找树、跳表、散列表或者有序动态数组等。