JZTXT

34. 图的概念

发布时间 2023-06-21 17:18:05作者: 夏冰翎

一、什么是图

  图G 由 顶点集V 和 边集E 组成，记为 G=(V,E)，其中 V(G) 表示 图G 中顶点的有限非空集，E(G) 表示 图G 中顶点之间的关系（边）的集合。若 \(V = \{ v_{1},v_{2},...,v_{n} \}\)，则用 \(|V|\) 表示 图G 中 顶点的个数，也称 图G的阶，\(E = \{ (u,v) | u ∈ V, v ∈ V \}\)，用 \(|E|\) 表示 图G 中边的条数。

  若 E 是 无向边（简称 边）的有限集合时，则 图G 为 无向图。边是顶点的无序对，记为 \((v,w)\) 或 \((w,v)\)，因为 \((v,w) = (w,v)\) 。其中 v、w 是顶点。可以说 顶点w 和 顶点v 互为邻接点。边 \((v,w)\) 依附于 顶点w 和 v，或者说边 \((v,w)\) 和顶点v、w 相关联。

  若 E 是 有向边（也称 弧）的有限集合时，则 图G 为 有向图。弧是顶点的有序对，即为 \(<v,w>\)，其中 v、w 是顶点，v 称为 弧尾，w 称为 弧头，\(<v,w>\) 称为从 顶点v 到 顶点w 的弧，也称 v 邻接到 w，或 w 邻接自 v。\(<v,w> ≠ <w,v>\)。

  如果图中不存在重复边并且不存在顶点到自身的边的图称为 简单图。如果图中某两个节点之间的边数多于一条，有允许顶点通过同一条边和自身关联，则为 多重图。

  对于 无向图 来说，顶点v的度 是指依附于该顶点的边的条数，记为 \(TD(v)\)；在具有 n 个顶点，e 条边的无向图中，\(\sum_{i=1}^{n}{TD(V_{i})} = 2e\) ，即无向图的全部顶点的度的和等于边数的 2 倍。

  对于 有向图 来说，入度 是以 顶点v 为终点的有向边的数目，记为 \(ID(v)\)，出度 是以顶点v 为起点的有向边的数目，记为 \(OD(v)\)。顶点v的度 等于其 入度和出度之和，即 \(TD(v) = ID(v) + OD(v)\)。在具有 n 个顶点、e 条边的有向图中，\(\sum_{i=1}^{n}{ID(V_{i})} = \sum_{i=1}^{n}{OD(V_{i})} = e\)。
  设有两个图 \(G=(V,E)\) 和 \(G' = (V',E')\)，若 \(v'\) 是 \(V\) 的子集，且 \(E'\) 是 \(E\) 的子集，则称 \(G'\) 是 \(G\) 的 子图。并非任意挑几个点、几条边都能构成子图。若有满足 \(V(G') = V(G)\) 的子图 \(G'\)，则称其为 \(G\) 的 生成子图。

  • 类型名称：图（Graph）
  • 数据操作集：G(V,E) 由一个非空的有限顶点集合 V 和一个有限边集合 E 组成。
  • 操作集：对任意图 G ∈ Graph，以及 v ∈ V，e ∈ E
Graph Create();                                     // 建立并返回空图
Graph InsertVertex(Graph G, Vertex v);              // 将v插入G
Graph InsertEdge(Graph G,Edge e);                   // 将e插入G
void DFS(Graph G, Vertex v);                        // 从顶点v出发深度优先遍历图G
void BFS(Graph G, Vertex v);                        // 从顶点v触发宽度优先遍历图G
void ShortestPath(Graph G, Vertex v, int Dist[]);   // 计算图G中顶点v到任意其它顶点的最短距离
void MST(Graph G);                                  // 计算图G的最小生成树

二、常见术语

  • 连通：如果从 V 到 W 存在一条（无向）路径，则称 V 和 W 是连通的；
  • 路径：V 到 W 的路径是一系列顶点 \({V,v_{1},v_{2},...,v_{n},W}\) 的集合，其中任意对相邻的顶点间都有图中的边。
  • 路径的长度：是指路径中的边数（如果带权，则是所有边的权重和）；
  • 简单路径：如果 V 到 W 之间的所有顶点都不同，则称为简单路径。
  • 回路：起点等于终点的路径；
  • 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
  • 点到点的距离：从 顶点u 出发到 顶点v 的 最短路径 若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。
  • 连通：无向图中，若从 顶点v 到 顶点w 有路径存在，则称 v 和 w 是连通的。
  • 连通图：无向图中任意两顶点均连通；
  • 连通分量：无向图的极大连通子图；
    • 极大顶点数：再加 1 个顶点就不连通了；
    • 极大边数：包含子图中所有顶点相连的所有边；
  • 强连通：有向图中顶点 V 和 W 之间存在双向的路径，则称 V 和 W 是强连通的；
  • 强连通图：有向图中任意两顶点均强连通；
  • 弱连通图：如果一个有向图不是强连通的，但它的基础图，即其弧去掉方向所形成的图是连通的，那么该有向图称为弱连通的；
  • 强连通分量：有向图的极大强连通子图；
  • 生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图，即边极可能的少，但要保持连通；
  • 生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林；
  • 边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值；
  • 带权图/网：边上带有权值的图称为 带权图，也成 网；
  • 在权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带全路径长度；
  • 无向完全图：无向图中任意两个顶点之间都存在边；
  • 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧；
  • 稀疏图：边树很少的图；
  • 稠密图：边数很多的图；
  • 树：不存在回路，且连通的无向图；
  • 有向树：一个顶点的入度为 0，其余顶点的入度均为 1 的有向图，称为 有向树；

对于有 n 个顶点的 无向图G，若 G 是连通的，则最少有 n-1 条边；若 G 是非连通图，则最多可能有 \(c_{n-1}^{2}\) 条边；

对于有 n 个顶点的 有向图G，若 G 是强连通图，则最少有 n 条边（形成回路）；

若图中顶点数为 n，则它的生成树含有 n-1 条边。对生成而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

稀疏图和稠密图之间没有绝对的界限，一般来说 \(|E| < |V|log|V|\) 时，可以将 G 视为 稀疏图；

三、图的表示

3.1、邻接矩阵表示法

  节点数为 n 的图 \(G = (V,E)\) 的邻接矩阵 A 是 n*n 的。将 G 的顶点编号为 \(v_{1},v_{2},...,v_{n}\)，则

\[A[i][j] = \begin{cases} 1 &,若(v_{i},v_{j}) 或 <v_{i},v_{j}> 是 E(G) 中的边\\ 0 & ,若 (v_{i},v_{j}) 或 <v_{i},v_{j}> 不是 E(G) 中的边 \end{cases} \]

  如果边有一个权，那么我们可以置 \(A[i][j]\) 等于该权，而使用一个很大或者很小的权作为标记表示不存在的边。

img

#define WeightType      int                         // 带权图中边上权值的数据类型
#define VertexType      char                        // 顶点的数据类型
#define MaxVertexNum    10                          // 顶点数目的最大值

typedef struct GNode *PtrToGNode;
typedef PtrToGNode MGraph;                          // 以邻接矩阵存储的图类型

// 用邻接矩阵存储图
struct GNode
{
    VertexType Vertex[MaxVertexNum];                // 顶点表
    WeightType Edge[MaxVertexNum][MaxVertexNum];    // 邻接矩阵，边表
    int VertexNum;                                  // 顶点数
    int EdgeNum;                                    // 边数
};

  从图中可以看到，无向图的邻接矩阵的主对角线的元素为 0，并且该矩阵为一个对称矩阵。因此，我们可以用一个长度为 \(\frac{N*(N+1)}{2}\) 的一维数组存储 \(G_{0,0},G_{1,0},G_{1,1},...,G_{n-1,0},...G_{n-1,n-1}\)，则 \(G_{i,j}\) 在 A 中对应的下标是：\((\frac{i * (i+1)}{2} + j)\)。对于网络，只要把 G[i][j] 的值定义为边 \(<v_{i},v_{j}>\) 的权重即可。

  邻接矩阵表示法直观、简单、好理解。并且它方便检查任意一对顶点间是否存在边，它也方便找任一顶点的所有“邻接点”（有边直接相连的顶点）。它方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）。对于无向图而言，对应行（或列）非 0 元素的个数为度。对于有向图而言，对应行非 0 元素的个数是“出度”，对应列非 0 元素的个数是“入度”。

  邻接矩阵存在浪费空间的问题。例如在存稀疏图（点很多而边很少）有大量无效元素。对稠密图（特别是完全图）还是很合算的。邻接矩阵也存在浪费时间的问题。在统计稀疏图中一共有多个条边时，需要对整个矩阵进行扫描。

3.2、邻接表表示法

  邻接表：对于每一个顶点，我们使用一个链表存放所有邻接的顶点。

img

#define WeightType      int                     // 带权图中边上权值的数据类型
#define VertexType      char                    // 顶点类型
#define MaxVertexNum    10                      // 顶点数目的最大值

typedef struct GNode *PtrToGNode;
typedef PtrToGNode LGraph;                      // 以邻接表存储的图类型
typedef struct AdjVNode *PtrToAdjVNode;

// 用邻接表存储图
struct GNode
{
    AdjList Vertices;                           // 邻接表
    int VertexNum;                              // 顶点数
    int EdgeNum;                                // 边数
};

// 顶点信息
typedef struct VNode
{
    VertexType Vertex;                          // 存顶点数据
    PtrToAdjVNode FirstEdge;                    // 第一条边
}AdjList[MaxVertexNum];

// 边信息
struct AdjVNode
{
    int AdjVex;                                 // 边指向哪个节点（邻接点下标）
    WeightType Weight;                          // 边权重
    PtrToAdjVNode Next;                         // 指向下一条边的指针
};

  对于网络，结构中要增加权重的域。

  使用邻接表，可以方便找任一顶点的所有“邻接点”，它可以用来节省系数图的空间，它需要 N 个头指针 + 2E 个节点（每个节点至少 2 个域）。对于无向图而言，它可以方便计算任一顶点的度。对于有向图而言，只能计算“出度”。这时，我们需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”。

3.3、邻接矩阵和邻接表的对比

邻接表 邻接矩阵
空间复杂度 无向图\(O(|V| + 2|E|)\)；有向图 \(O(|V| + |E|)\) \(O(|V|^{2})\)
适合用于 存储稀疏图 存储稠密图
表示方法 不唯一 唯一
计算度/出度/入度 计算有向图的度、入度不方便，其余很方便 必须遍历对应行或列
找相邻的边 找有向图的入边不方便，其余很方便 必须遍历对应行或列