图的基本概念

图的定义

图G由顶点集V和边集E组成，记为，其中表示图G中顶点的有限非空集；表示图中顶点之间的关系（边）集合。

线性表可以是空表、树可以有空树，但图不能是空图，图中至少有一个节点，但可以没有边

  1. 有向图
    若E是有向边(弧)的有限集合时，图G为有向图，。弧是顶点的有序对，记为<v,w>，其中v,w是顶点，v称为弧尾，w称为弧头。也称v邻接到w。

  2. 无向图
    若E是无向边(边)的有限集合时，图G为无向图。边是顶点的无序对，记为(v,w)或(w,v)。可以说w和v互为邻接点。

  3. 简单图、多重图
    一个图若满足：

    1. 不存在重复边
    2. 不存在顶点到自身的边

    则称该图为简单图。
    若图中某两个顶点之间的边数大于1，又允许顶点通过一条边和自身关联，则称该图为多重图。

  4. 完全图（简单完全图）
    对于无向图，|E|的取值范围在0~之间，有条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边；对于有向图，|E|的取值范围在0~之间，有条边的有向图称为完全有向图，有向完全图中任意两个顶点之间都存在方向相反的两条弧。

  5. 子图
    若存在一个使得是的子集，是的子集，则将称为的子图。若，则将称为的生成子图。

  6. 连通、连通图和连通分量(特指无向图)

  • 连通：在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。
  • 连通图：若图中任意两个顶点都是连通的，则称该图为连通图，否则便是非连通图。
  • 连通分量：无向图中的极大连通子图称为该图的连通分量。(极大连通子图即该图的连通子图且该子图拥有的顶点数无法再增加，若增加就不在连通，且包含所有边)
  1. 强连通图、强连通分量(特指有向图)
  • 强连通：有向图中若v到w和w到v之间都存在路径，则称这两个顶点是强连通的。
  • 强连通图：有向图中的任意两个结点都是强连通的，则该图称为强连通图。
  • 强连通分量：有向图中的极大强连通子图。
  1. 生成树、生成森林
  • 生成树：包含图中所有结点的一个极小连通图。若图中有n个顶点，则生成树有n-1条边(极小连通图需要保证的是图的连通且边数最少)(若砍去生成树中的一条边，则该极小连通图退化为非连通图，若加上一条边则会产生一个回路)
  • 生成森林：非连通图中的连通子图的生成树构成了一片生成森林。
  1. 顶点的度、出度、入度
  • 度：依附于顶点的边的条数，记为。对于具有n个顶点、e条边的无向图，所有顶点的度之和为2e(一条边代表两个度嘛)。有向图的顶点的度为该顶点出度和入度之和。
  • 入度：在有向图中以顶点v为终点的边的数目，记为
  • 出度：在有向图中以顶点v为起点的边的数目，记为
  • 在有向图中所有顶点的出度和等于所有顶点的入度和
  1. 边的权和网
  • 权值：每条边都可以标注具有某种意义的数值，该值称为权值
  • 网： 边上带有权值的图称为带权图，或网
  1. 稠密图、稀疏图
  • 稀疏图：边数很少的图
  • 稠密图：边数很多的图
  • 判断条件：，则为稀疏图
  1. 路径、路径长度、回路
  • 路径:顶点到之间的一条路径指顶点序列
  • 路径长度：路径上边的数量
  • 回路：第个顶点和最后一个顶点相同的路径称为回路。若一个图有n个顶点，但有大于n-1条边，则此图一定存在回路。

  1. 距离
    从顶点u出发到v的最短路径长度，若该路径不存在，则距离为无穷∞

  2. 有向树
    一个顶点的入度为0、其余顶点的入度均为1 的图称为有向树。

图的存储以及基本操作

图的存储必须要完整、准确地反应顶点集和边集的信息。根据不同图的结构和算法，采用不同的存储方式将对程序的效率产生相当大的影响，因此所选的存储结构应适合于待求解的问题。

邻接矩阵法

采用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息(即各个顶点之间的关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。

点中的数据使用一维数组保存，一维数组下表代表顶点编号，边使用二维数组保存，边的两个端点即二维数组的两个下标，由于这两个下标有ij和ji两种排列状态，故可以表示有向图。若为无向图时，该矩阵为对称矩阵。二维数组中的值代表有无边或者边的权值

代码定义如下

#define MaxVertexNum 100
typedef char VertesType;
typedef int EdgeType;
typedef struct{
    VertexType vex[MaxVertNum]; //数据
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接表
    int vexnum,arcnum; //图的当前顶点数和弧数
} MGraph;
  • 在简单应用中，可以直接使用二维数组存储图，即忽略掉图的顶点信息
  • 当邻接矩阵的元素仅表示相应边是否存在时，EdgeType可采用值为0和1的枚举类型
  • 无向图的邻接矩阵是对称矩阵，对规模大的图可以压缩存储
  • 邻接矩阵表示法的空间复杂度为，其中n为图的顶点数

特点：

  1. 无向图的邻接矩阵一定是一个对称矩阵(并且唯一)
  2. 对于无向图，邻接矩阵的第i行(或第i列)非零元素分个数正好是顶点i的度
  3. 对于无向图，邻接矩阵的第i行非零元素的个数正好是顶点i的出度，第i列的非零元素刚好是顶点的入度
  4. 用邻接矩阵存储图，很容易确定图中的任意两个顶点是否有边相连。但是，要确定图中有多少条边，则必须按行、列扫描检测，时间开销巨大。
  5. 稠密图适合使用邻接表表示

邻接表法

当一个图为稀疏图时，使用邻接矩阵***浪费大量空间。