数据结构 - 图（基础概念）

2020-10-02 本文已影响0人 Whyn

[TOC]

简介

我们知道，数据结构 是存储相互之间存在的一种或多种特定关系的数据元素的集合。也即，数据结构是对数据的存储与数据关系的描述。
实际上，数据结构强调的是对数据关系的描述，存储只是为了持有数据，同时在底层以一个合适的存储结构对数据进行组织，以便更好地满足对数据关系的描述。

对于数据的存储结构，有按前驱后继的线性组织形式排列的，比如线性表。也有数据按层的方式进行组织的，比如说树（结点与结点之间是一种层次关系）。
但是，无论是哪种数据存储组织方式，其基本底层存储结构主要就是数组和链表。因此，很多其他的数据结构底层真正用于存储数据就是数组和链表，然后在这之上构建出线性或层次组织。

对于数据关系的描述，我们知道，数据之间存在四种关系：

彼此独立：即数据元素之间没有关系。
一对一：线性表就是典型的一对一数据结构。比如数组，它是一块连续的内存，因此只要知道其中一个元素，就能知道它的前驱后继元素，又比如链表，它是一块分散的内存，但是每个元素内部都预置了一个指向下一个结点元素的指针...
一对多：典型的数据结构就是树。比如对于二叉树，一个树枝结点就可以对应左右两个子结点。
多对多：我们本篇博文所要介绍图，就是一个典型的多对多关系数据结构，图中每个顶点（即数据元素）都可能与其他一个或多个顶点存在联系。

简而言之，图是一种较线性表和树等数据结构更加复杂的结构，在图中，元素之间的关系可以是任意的，图中任意两个数据元素之间都可能存在关系。
因此，对于图的元素之间的关系描述就显得比较复杂。

图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： $G(V，E)$ ，其中， $G$ 表示一个图， $V$ 是图 $G$ 中顶点的集合， $E$ 是图 $G$ 中边的集合。

简单来说，图是由顶点和边组合而成，其结构示意图如下所示：

图

对于图的定义，有以下几个地方需要明确注意：

线性表中我们把数据元素叫元素；
树中将数据元素叫结点；
在图中的数据元素，我们称之为顶点（Vertex）。
线性表可以没有数据元素，称为空表；
树中可以没有结点，称为空树；
而在图结构中，不允许没有顶点。在定义中，若 $V$ 是顶点的集合，即强调了顶点集合 $V$ 有穷非空。
线性表中，相邻的数据元素之间具有线性关系；
树结构中，相邻两层的结点具有层次关系；
而 图中，任意两个顶点之间都可能存在关系，顶点之间的逻辑关系用边进行表示，边集可以是空的。

图的相关概念

图是一个相对复杂的数据结构，为了更好地对图进行描述，让我们先来了解下与图相关的一些基础概念，主要包含如下：

顶点（Vertex）：在图中的数据元素，我们称之为顶点。
边：图中，任意两个顶点之间都可能存在关系，顶点之间的逻辑关系用边进行表示，边集可以是空的。其中：
- 无向边（Edge）：若顶点 $v_i$ 到 $v_j$ 之间的边没有方向，则称这条边为无向边，用无序偶对 $(v_i,v_j)$ 来表示。
- 有向边/弧（Arc）：若从顶点 $v_i$ 到 $v_j$ 的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶 $<v_i,v_j>$ 来表示， $v_i$ 称为弧尾（Tail）， $v_j$ 称为弧头（Head）。
度（Degree）：一个顶点的边数叫做度。其中：
- 对于无向图而言，顶点 $v$ 的度就是和该顶点相关联的边的数目，记作： $TD(v)$
- 对于有向图而言，顶点 $v$ 的度分为 入度（箭头朝自己） 和 出度（箭头朝外）。其中：
  - 以顶点 $v$ 为头的弧的数目称为 $v$ 的入度（InDegree），记作： $ID(v)$ ，
  - 以顶点 $v$ 为尾的弧的数目称为 $v$ 的出度（OutDegree），记作： $OD(v)$ 。
  因此，有向图顶点 $v$ 的度为： $TD(v) = ID(v) + OD(v)$
权（Weight）：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。权可以表示从一个顶点到另一个顶点的距离或耗费。
邻接点（Adjacent）：即相连接的两个顶点。比如：
- 对于无向图 $G = (V,\{E\})$ ，如果边 $(v,v') \in E$ ，则称顶点 $v$ 和 $v'$ 互为邻接点。
- 对于有向图 $G = (V,\{E\})$ ，如果弧 $<v,v'> \in E$ ，则称顶点 $v$ 邻接到顶点 $v'$ ，顶点 $v'$ 邻接自顶点 $v$ 。
路径：对于图 $G = (V,\{E\})$ ，从顶点 $v$ 到顶点 $v'$ 所经历的边连接而成的线段称为路径。即一个顶点到另一个顶点所经过的边。
路径的长度是路径上的边或弧的数目。
回路/环（Cycle）：第一个顶点到最后一个顶点相同的路径称为回路或环。
序列中顶点不重复出现的路径称为简单路径。
除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。比如对于下图：

左侧的环因只有顶点 $B$ 重复访问，但是 $B$ 是访问路径的第一个顶点和最后一个顶点，且 $C$ ， $D$ ， $A$ 顶点没有重复出现，因此是一个简单环。
而右侧的环，由于顶点 $C$ 的重复访问，因此不是一个简单环。
连通（Connected）：在无向图 $G$ 中，如果从顶点 $v$ 到顶点 $v'$ 有路径，则称 $v$ 和 $v'$ 是连通的。
连通分量：无向图中的极大连通子图称为连通分量。
强连通分量：有向图中的极大强连通子图称作有向图的强连通分量。
生成树：对连通图进行遍历，过程中所经历的顶点和边的组合可看作是一棵普通树，通常称为生成树。生成树包含有图中全部的 $n$ 个顶点，但只有足以构成一棵树的 $n-1$ 条边。
无向图中连通且 $n$ 个顶点 $n-1$ 条边叫生成树。有向图中一顶点入度为 $0$ ，其余顶点入度为 $1$ 的叫 有向树，一个 有向图 由若干棵有向树构成 生成森林。

图的种类

无向图（Undirected graphs）：如果图中任意两个顶点之间的边都是无向边，则称该图为 无向图。下图所示即为无向图：
无向图
由于无向图是无方向的，连接顶点 $A$ 与 $D$ 的边，可以表示成无序对 $(A,D)$ ，也可以写成 $(D,A)$ 。

对于上图中的无向图 $G$ 来说， $G = (V,\lbrace E\rbrace )$ ，其中：
- 顶点集合 $V = \lbrace A,B,C,D \rbrace$
- 边集合 $E = \lbrace (A,B),(B,C),(C,D),(D,A),(A,C) \rbrace$

有向图（Directed graphs）：如果图中任意两个顶点之间的边都是有向边，则称该图为 有向图（Directed graphs）。如下图所示即为一个有向图：
有向图
连接到顶点 $A$ 到 $D$ 的有向边就是弧， $A$ 是弧尾， $D$ 是弧头， $<A,D>$ 表示弧，注意不能写成 $<D,A>$ 。

对于上图的有向图 $G$ 来说， $G = (V,\lbrace E \rbrace)$ ，其中：
- 顶点集合 $V = \lbrace A,B,C,D \rbrace$
- 弧集合 $E = \lbrace <A,D>,<B,A>,<C,A>,<B,C> \rbrace$
注：无向边用小括号 $"()"$ 表示，而有向边则是使用尖括号 $"<>"$ 表示。

简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。如下所示的两个图就不属于简单图：
非简单图
注：本篇博文主要讨论的就是简单图。
无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为 无向完全图。如下图所示即为一个无向完全图：
无向完全图
有向完全图：在有向图中，如果任意两个顶点之间都存在 方向互为相反 的两条弧，则称该图为 有向完全图。如下图所示即为一个有向完全图：
有向完全图

稀疏图：图的边（弧）很少。
稠密图：图的边（弧）很多。

注：稀疏和稠密的判断条件是： $e < nlogn$ ，其中 $e$ 表示图中边（或弧）的数量， $n$ 表示图中顶点的数量。如果式子成立，则为稀疏图；反之为稠密图。
网（Network）：指带权的图。比如下图就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。
网
子图（Subgraph）：如果一个图的所有顶点和边都存在与另一个图中，则称前一个图为后一个图的子图。比如，假设有两个图 $G = (V,\lbrace E \rbrace)$ 和 $G' = (V',\lbrace E' \rbrace)$ ，如果 $V' \subseteq V$ 且 $E' \subseteq E$ ，则称 $G'$ 为 $G$ 的子图。如下图所示，右侧带底纹的图均为左侧无向图和有向图的子图：
子图
连通图（Connected Graph）：如果对于图中任意两个顶点 $v_i、v_j \in E$ ， $v_i$ 和 $v_j$ 都是连通的，则称 $G$ 是连通图。也即，图中任意两个顶点之间都是直接或间接地连接在一起。比如，对于下图所示：

对于图1，比如顶点 $A$ 与顶点 $E$ 或 $F$ 显然不存在路径进行连接，无法满足任意两个顶点之间直接或间接连接，因此其不是一个连通图。
正确来说，图1是一个无向非连通图，但是它包含有两个连通分量，即图2和图3。而尽管图4是图1的一个子图，但是它却不满足连通子图的极大顶点数（图2满足），因此它不是图1的连通分量。

而对于图2，顶点 $A$ ， $B$ ， $C$ 和 $D$ 中任意两个顶点都是连通的，因此它是一个连通图。
强连通图：在有向图 $G$ 中，如果对于每一对 $v_i、v_j \in V、v_i \neq v_j$ ，从 $v_i$ 到 $v_j$ 和从 $v_j$ 到 $v_i$ 都存在路径，则称 $G$ 是强连通图。即有向图中，任意两个顶点都直接或间接连接在一起（路径需考虑方向）。

注：实际上，如果一个图有 $n$ 个顶点和小于 $n-1$ 条边，则它是非连通图。

图的存储结构

由前面的内容可以知道，图中的元素主要由顶点和边（或弧）组成，任意两个顶点之间都可能存在联系，而顶点和边本身也存在联系，因此图的结构比较复杂，很难以数据元素在内存中的物理位置来表示图中元素之间的关系，也就是说，图不可能仅用简单的顺序存储结构（即数组）来表示。而多重链表尽管可以实现图结构（即以一个数据域和多个指针域组成的结点表示图中的一个顶点），但是却存在内存浪费或操作不便的问题。因此，图存储结构最终还是得通过结合顺序存储和链式存储才能做到比较好地实现。

当前用于图的存储主要有以下 5 种结构：

邻接矩阵（Adjacency Matrix）：采用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧信息。

注：顶点和顶点之间的关系称为边或弧，对于弧来说（即有向图），其存在方向，因此， $<v_i,v_j>$ 和 $<v_j,v_i>$ 表示两条反向的弧，这个信息可以很方便用二维数组进行标识： $V[i][j]$ 、 $V[j][i]$

假设图 $G$ 有 $n$ 个顶点，则邻接矩阵是一个 $n \times n$ 的方阵，定义为：

$arc[i][j] = \begin{cases} 1, & \text{若 $(v_i,v_j) \in E$ 或 $<v_i,v_j> \in E$} \\ 0, & \text{反之} \end{cases}$

也即，图中，任意两顶点之间处于连接状态时，其邻接矩阵（即二维数组）对应索引元素置为 $1$ ，否则为 $0$ 。

举个例子，比如对于下图：
无向图 - 邻接矩阵
对于上图中的图结构，其顶点集合对应数组 $vertex[4] = \{v_0,v_1,v_2,v_3\}$ ，边数组 $arc[4][4]$ 示意图如上图所示。

图中顶点之间的关系可以很方便地从邻接矩阵（即边数组、二维数组） $arc[4][4]$ 得出：
- 对于顶点元素之间的关系，比如 $v_i$ 和 $v_j$ ，只需在查看邻接矩阵 $arc[i][j]$ 的值即可，为 $1$ 表示顶点 $v_i$ 和 $v_j$ 为邻接点，为 $0$ 则表示顶点 $v_i$ 和 $v_j$ 没有连接。
- 一个顶点的度其实就是这个顶点在顶点数组中对应索引（假设为 $i$ ）在邻接矩阵中的第 $i$ 行（或第 $i$ 列）的元素之和。
注：由于我们使用的图都是简单图，因此不存在顶点到自身的边，因此，邻接矩阵中： $arc[0][0] = arc[1][1] = arc[2][2] = arc[3][3] = 0$

注：由于无向图的边没有方向，即 $(v_i,v_j) = (v_j,v_i)$ ，因此，无向图的邻接矩阵是一个对称矩阵，即 $arc[i][j] == arc[j][i]$

对于有向图，比如下图所示：
有向图 - 邻接矩阵
有向图的构造与无向图基本一致，区别在于有向图边具备方向，因此其邻接矩阵不具备对称性，因为 $<v_i,v_j> \neq <v_j,v_i>$ 。

如果要求顶点 $v_i$ 的出度（即 $i$ --> $j$ ），只需遍历邻接矩阵第 $i$ 行的所有值并进行累加即可。
如果要求顶点 $v_i$ 的入度（即 $j$ --> $i$ ），只需遍历邻接矩阵第 $i$ 列的所有制并进行累计即可。

注：如果图的每条边都带有权值，即网结构时，只需修改下邻接矩阵的索引值即可，如下所示：

假设图 $G$ 是网图，有 $n$ 个顶点，则其邻接矩阵是一个 $n \times n$ 的方阵，定义为：

$arc[i][j] = \begin{cases} W_{ij}, & \text{若 $(v_i,v_j) \in E$ 或 $<v_i,v_j> \in E$} \\ 0, & \text{若 $i = j$} \\ \infty, & \text{反之} \end{cases}$

此处 $W_{ij}$ 表示边 $(v_i,v_j)$ 或弧 $<v_i,v_j>$ 的权值。
$\infty$ 表示一个大于所有边取值的一个值，用以区分有效的权值（因为权值有可能为正数，负数或者是 $0$ ），因此对于不存在的边，采用一个不存在的权值进行表示。

网图结构示意图如下所示：
网图 - 邻接矩阵
邻接矩阵的代码表示如下所示：
```
#ifndef __MGRAPH_H__
#define __MGRAPH_H__


#define MAX_VEX  100                  // 最大顶点数
#define WEIGHT_INFINITY 65535         // 无效权值，用 65535 表示正无穷

/*
* V：表示顶点 Vertext 类型
* E：表示边权值类型
*/
template<typename V, typename E>
struct MGraph {                       // 邻接矩阵
    V vexs[MAX_VEX];                  // 顶点数组（顶点表）
    E arc[MAX_VEX][MAX_VEX];          // 邻接矩阵（边表）
    int numsVertex = 0, numsEdge = 0; // 图中顶点数和边数
};
#endif
```
邻接矩阵是一种简单直接的图存储结构，但是当图边数较少时（比如对于稀疏图），这种结构在空间上存在极大的浪费，比如当邻接矩阵只有顶点 $<v_i,v_j>$ 有权值时，其余空间就浪费了，此时可采用 邻接表 进行替代。
邻接表（Adjacency List）：邻接表采用数组和链表相结合的方式存储图的数据，这个方法与哈希表的拉链法存在异曲同工之处。

具体来说，邻接表的处理逻辑如下所示：
- 图中顶点仍然采用一维数组进行存储，但是顶点数组存储的不再仅仅只是顶点的值，而是还会为每个顶点添加一个指向第一个邻接点的指针（即链表头结点），以便查找该顶点的边信息。
- 图中每个顶点 $v_i$ 的所有邻接点构成一个线性表，由于每个顶点的邻接点个数不确定，所以采用单链表存储，灵活且不浪费空间。
  该链表结构对于无向图来说，称作顶点 $v_i$ 的边表，对于有向图来说，称作顶点 $v_i$ 的出边表（此时 $v_i$ 作为弧尾）。
如下图所示就是一个无向图的邻接表结构：
无向图 - 邻接表
从上图可以看出，顶点数组实际存储的是结点元素，包含一个数据域data和一个指针域firstedge，指针域firstedge指向边表的第一个结点。
边表结点也是由两个域组成：邻接点域adjvex和next指针域。其中，adjvex存储邻接顶点在顶点表（顶点数组）中的索引位置，next指针指向边表中的下一个邻接点的边表结点。比如，对于顶点 $v_1$ ，其与 $v_0$ 和 $v_2$ 互为邻接点，所以在 $v_1$ 的边表中，adjvex的值分别为 $v_0$ 的索引0和 $v_2$ 的索引2。

在邻接表结构中，对于图的信息获取也是很方便的，比如：
- 获取某个顶点的度，只需获取该顶点对应边表的长度即可。
- 判断顶点 $v_i$ 和 $v_j$ 是否为邻接点，只需判读顶点 $v_i$ 的边表是否存在adjvex == j即可。
- 获取顶点 $v_i$ 的所有邻接点，则只需遍历该顶点的边表即可，所有边表结点的adjvex就是其邻接点在顶点表的索引集合。
对于有向图，图的邻接表构建与无向图类似，只是因为图是有方向的，因此以当前顶点作为弧尾来存储边表，遍历该边表就可以得到该顶点的所有邻接点，边表的长度就是该顶点的出度，如下图所示：
有向图 - 邻接表
当然，有时候为了方便获取顶点的入度或以顶点为弧头，则可以建立一个有向图的逆邻接表，如下图所示：
有向图 - 逆邻接表
对于带权值的网图，只需为边表结点增添一个数据域weight即可，如下所示：
网图 - 邻接表
邻接表的代码表示如下所示：
```
#ifndef __GRAPHADJLIST_H__
#define __GRAPHADJLIST_H__

#define MAX_VEX  100                         // 最大顶点数


template<typename E>
struct EdgeNode {                            // 边表结点
    int adjvex;                              // 邻接点域，存储邻接点索引
    E weight;                                // 权值，对于非网图可省略
    struct EdgeNode* next;                   // 下一个邻接点的边表结点

    EdgeNode() :adjvex(-1), next(nullptr) {}
};

template<typename V, typename E>
struct VertexNode {                          // 顶点表结点
    V data;                                  // 顶点数据域
    struct EdgeNode<E>* firstedge;           // 第一个邻接点边表结点

    VertexNode() :firstedge(nullptr) {}
};

template<typename V, typename E>
struct GraphAdjList {                        // 邻接表
    VertexNode<V, E> vertex[MAX_VEX];        // 顶点表
    int numsVertex = 0, numsEdge = 0;        // 图中顶点数和边数
};

#endif
```
邻接表解决了邻接矩阵的存储效率问题，但邻接表自身的一个缺陷就是对有向图顶点的度描述能力不足，采用邻接表，可以很方便获取顶点的出度，但是对于入度，则必须遍历整个邻接表（具体来说，就是遍历其余顶点的邻接表，查看其边表是否含有adjvex等于当前顶点索引），而如果采用逆邻接表，同样方便了入度，而出度依旧繁琐。一种结合邻接表与逆邻接表解决出度入度问题的结构就是：十字链表。
十字链表（Orthogonal List）：十字链表其实就是结合了邻接表和逆邻接表的结构。

十字链表的具体构造过程如下所示：
1. 十字链表仍然采用一维数组存储顶点元素，但是元素结点结构更改为如下：
十字链表 - 顶点元素结点
可以看到，顶点表的元素结点包含三方面内容：
- data：表示顶点元素的数据域
- firstin：表示入边表头指针（对应入度），指向当前顶点第一个入边表结点
- firstout：表示出边表头指针（对应出度），指向当前顶点第一个出边表结点
1. 边表结点结构更改为如下：
十字链表 - 边表结点结构
可以看到，边表结构的结点包含如下四方面内容：
- tailvex：表示弧起点（即弧尾）在顶点表的下标（注：弧尾即当前顶点）
- headvex：表示弧终点（即弧头）在顶点表的下标（注：弧头即当前顶点的邻接点）
- taillink：表示出边表指针域，指向当前顶点的下一条出边表结点
- headlink：表示入边表指针域，指向当前顶点的下一条入边表结点
注：如果是网图，只需为边表结点结构添加一个weight属性即可

注： $<tailvex,headvex>$ 表示了一条弧，由顶点 $tailvex$ 到顶点 $headvex$

十字链表的搜索方法如下：假设当前顶点为 $v_i$ ，则：
- 当前顶点的出边表获取方法为：
  1. 首先获取当前顶点的第一个出边表结点，即：firstout
  2. 由firstout指向的第一个出边表结点的taillink获取得到当前顶点的下一个出边表结点
  3. 重复步骤2，直至出边表结点的taillink为空，表示当前顶点的出边表遍历完成
- 当前顶点的入边表获取方法为：
  1. 首先获取当前顶点的第一个入边表结点，即：firstin
  2. 由firstin指向的第一个入边表结点的headlink获取得到当前顶点的下一个入边表结点
  3. 重复步骤2，直至入边表结点的headlink为空，表示当前顶点的入边表遍历完成
举个例子，如下图所示：
十字链表 - 示例
上述示例图中左侧为初始图结构，右侧为使用十字链表法对左侧初始图构造而成的结构，下面我们具体分析下构造过程：
- 对于顶点，由左侧初始图可以看出，其值为V0，因此顶点表索引0中的vertex[0].data = V0，然后：
  - 出边表：顶点 $v_0$ 只有一条出边 $<v_0,v_3>$ ，对应边表结点中的tailvex = 0和headvex = 3的边表结点，所以顶点 $v_0$ 的firstout指向 $<v_0,v_3>$ 的边表结点，由于 $v_0$ 没有其他出边了，因此firstout指向的边表结点中的taillink指向空
  - 入边表：顶点 $v_0$ 总共有两条入边： $<v_1,v_0>$ 和 $<v_2,v_0>$ ，假设 $v_0$ 的第一个入边为 $<v_1,v_0>$ ，则其firstin对应边表结点中的tailvex = 1和headvex = 0，然后该边表结点中的headlink指向顶点 $v_0$ 的下一个入边结点 $<v_2,v_0>$ ，即tailvex = 2和headvex = 0，此时 $v_0$ 没有其他入边， $<v_2,v_0>$ 边表结点的headlink置为空，表示入边结束
- 其余顶点的构建过程与上述顶点 $v_0$ 如出一辙
注：其实，这里就很容易看的出来，firstout就是顶点对应的邻接表，firstin就是顶点对应的逆邻接表。

十字链表的代码表示如下所示：
```
#ifndef __OLGRAPH_H__
#define __OLGRAPH_H__

#define MAX_VEX  100                        // 最大顶点数

template<typename E>
struct EdgeNode {                           // 边表结点
    int tailvex = -1;                       // 弧起点索引
    int headvex = -1;                       // 弧终点索引
    EdgeNode* taillink = nullptr;           // 出边表指针域
    EdgeNode* headlink = nullptr;           // 入边表指针域
    E weight;                               // 权值，对于非网图可省略


};
template<typename V, typename E>
struct VertexNode {
    V data;                                 // 顶点数据域
    struct EdgeNode<E>* firstin = nullptr;  // 第一个入边结点
    struct EdgeNode<E>* firstout = nullptr; // 第一个出边结点
};

template<typename V, typename E>
struct OLGraph {                            // 十字链表
    VertexNode<V, E> arc[MAX_VEX];          // 顶点表
    int numsVertex = 0, numsEdge = 0;       // 图中顶点数和弧数
};
#endif
```
十字链表因为结合了邻接表和逆邻接表，因此很容易找到以 $v_i$ 为尾的弧，也很容易找到以 $v_i$ 为头的弧，因而很容易可以求得顶点的出度和入度。
唯一的一个缺点大概是结构相对复杂，但其实十字链表创建图算法的时间复杂度和邻接表是相同的，因此，在有向图的应用中，十字链表是一种非常好的数据结构模型。
邻接多重表（Adjacent MultiList）：为每条边单独构建一个结构，形成完整独立的边集表。

十字链表是对有向图的优化，而在无向图中，通常我们更关注的是顶点的操作，那么使用邻接表是一个不错的选择，因为邻接表就是基于顶点的视角进行构建，顶点和顶点之间形成的链表关系即为边。但是如果我们关注的对边的操作，由于无向图边不区分方向，因此，在邻接表中，边集是存在一半的重复部分，比如 $(v_i,v_j)$ 和 $(v_j,v_i)$ 就是重复的，假设我们要删除顶点 $v_i$ 和顶点 $v_j$ 之间的边，在邻接表中，就需要删除两个边表结点。如下图所示：

假设我们要删除边 $(v_0,v_2)$ ，则需要删除邻接表中的 $(v_0,v_2)$ 和 $(v_2,v_0)$ 边表结点。

删除一条边，却要进行两次操作，邻接表的结构在这里操作上稍显冗余，此时可采用邻接多重表解决上述问题。

邻接多重表的构建逻辑如下所示：
- 同邻接表一样，顶点表采用一维数组进行存储，且每个数组元素包含一个数据域data和一个指针域firstedge，指向当前顶点的第一条边
- 边表结点结构更改为如下：
邻接多重表 - 边表结点结构
可以看到，边表结点结构包含如下四方面内容：
- ivex：表示当前顶点在顶点表的下标（即代表当前顶点）
- jvex：表示当前顶点的邻接点在顶点表的下标（即代表当前顶点的一个邻接点）
- ilink：表示指向下一条边集结点（即代表当前顶点的下一条边）
- jlink：表示依附于顶点jvex的下一条边（即代表当前顶点的邻接点的下一条边）
注：这里的ivex和jvex很好理解，而ilink和jlink相对容易混乱。
其实，ilink就是当前顶点的下一个边，即 $(v_0,v_j)$ ，比如对于结点 $v_0$ ，ilink就表示结点 $v_0$ 与其一个邻接点构成的边。
而jlink是当前结点不是 $v_0$ 开头，即边表示为 $(v_j,v_0)$ ，所以此处的jlink也表示结点 $v_0$ 的下一条边。

举个例子，如下图所示：

上图左侧为原始图，右侧为邻接多重表的初始构建状态，边表结点中各个ivex和jvex表示为一条边，即 $(v_i,v_j)$ 。

我们可以开始对上图继续进行构建：
- 为顶点表每个顶点构建第一条边：下图中的①②③④就是将顶点的firstedge指向第一条边，指向的边的ivex要与当前顶点相同，表示边以当前顶点为起点
- 从初始图可以看到，顶点 $v_0$ 总共有三条边： $(v_0,v_1)$ ， $(v_0,v_2)$ 和 $(v_0,v_3)$ 。
  上述操作后，顶点 $v_0$ 就指向了边集结点 $(v_0,v_1)$ ，因此， $(v_0,v_1)$ 的ilink会指向顶点 $v_0$ 的下一个边集结点，这里假设为 $(v_0,v_3)$ ，则对应的边集结点为 $(v_3,v_0)$ ，此时， $(v_3,v_0)$ 的jlink会指向当前顶点 $v_0$ 的再下一条边 $(v_0,v_2)$ ，此时没有其他边了，因此，边集结点 $(v_0,v_2)$ 的ilink为空。
  注：当前顶点的ilink指向的结点的jvex一定要和它本身的ivex相同
- 其他的顶点构造方法与 $v_0$ 一致，最终构建出来的邻接多重表如下图所示：
邻接多重表
邻接多重表摈弃了邻接表的顶点链表，而对所有边单独进行构建，并为边结点提供了ilink和jlink，形成一个边集链表。
可以说，邻接表是以顶点为基础，形成顶点链表，顶点链表各个结点构成边的关系；
而邻接多重表是以边为基础，形成边集表，边集表各个结点构成顶点间的关系。

所以，如果是对边进行操作的话，比如上文要删除边 $(v_0,v_2)$ ，使用邻接多重表的话，只需将各边集结点指向 $(v_0,v_2)$ 的ilink和jlink置为空即可，对应于上文示例，只需将⑥和⑨的jlink置为空即可。

邻接多重表的代码表示如下所示：
```
#ifndef __AMLGRAPH_H__
#define __AMLGRAPH_H__

#define MAX_VEX  100    // 最大顶点数

template<typename E>
struct EdgeNode { // 边表结点
    int ivex = -1;
    int jvex = -1;
    EdgeNode* ilink = nullptr;
    EdgeNode* jlink = nullptr;
    E weight; // 权值，对于非网图可省略

};

template<typename V, typename E>
struct VertexNode {// 顶点表结点
    V data; // 顶点数据域
    struct EdgeNode<E>* firstedge; // 第一个邻接点边表结点

    VertexNode() :firstedge(nullptr) {}
};

template<typename V, typename E>
struct AMLGraph { // 邻接多重表
    VertexNode<V, E> vertex[MAX_VEX]; // 顶点表
    int numsVertex = 0, numsEdge = 0; // 图中顶点数和边数
}; 
#endif
```
边集数组（Edgeset Array）：边集数组是由两个一维数组组成。一个存储顶点的信息；另一个存储边的信息，这个边数组每个数据元素由一条边的起点下标begin、终点下标end和权重weight组成。如下图所示：
边集数组
前面内容说过，图的数据元素就是顶点和边（或弧），所以这里边集数组就很好理解了，就是各自使用一个数组来表示图的数据元素。其中：
- 因为顶点只是数据，因此一维数组存储数据域即可
- 边的信息比较多，包含起始顶点、终端顶点和权重，因此一个边结构需要 3 个域进行表示，分别为：起点下标begin、终点下标end和权重weight
显然边集数组更关注的是对边的操作，在边集数组中要查找一个顶点的度需要扫描整个边数组（即出度，扫描边数组begin等于当前顶点下标，入度，扫描边数组end等于当前顶点下标，两者之和即为当前顶点的度），效率并不高。因此边集数组结构更适合对边依次进行处理的操作，而不适合对顶点相关的操作。

边集数组的一个应用主要是用于连通网的最小生成树算法：克鲁斯卡尔（Kruskal）算法，具体内容参考后文。

边集数组的代码表示如下：
```
#ifndef __EDGESETGRAPH_H__
#define __EDGESETGRAPH_H__

#define MAX_VEX  100                            // 最大顶点数
// 完全无向图边数：(MAX_VEX * (MAX_VEX - 1)) /2
// 完全有向图边数：MAX_VEX * (MAX_VEX - 1)
#define MAX_EDGE (MAX_VEX * (MAX_VEX - 1)) >> 1

template<typename E>
struct EdgeNode {                               // 边结点元素
    int begin = -1;                             // 边起始顶点下标
    int end = -1;                               // 边终点顶点下标
    E weight;                                   // 权值，对于非网图可省略
};

/*
* V：表示顶点元素类型
* E: 表示边权重元素类型
*/

template<typename V, typename E>
struct EdgesetGraph {                           // 边集数组
    V vertex[MAX_VEX];                          // 顶点表
    EdgeNode<E> edge[MAX_EDGE];
    int numsVertex = 0, numsEdge = 0;           // 图中顶点数和边数
};
#endif
```

数据结构 - 图（基础概念）

简介

图的定义

图的相关概念

图的种类

图的存储结构

参考

猜你喜欢

热点阅读