数据结构-图

图是一种比线性表和树更为复杂的数据结构。在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

图结构在计算机科学和算法设计中有广泛的应用。例如，在社交网络分析中，可以使用图结构来表示用户之间的关系；在路线规划中，可以使用图结构来表示道路网络和城市之间的连接关系；在人工智能领域中，图结构可以用于表示知识图谱和推荐系统等。

在离散数学中，图论是专门研究图的性质的数学分支，而在数据结构中，则应用图论的知识讨论如何在计算机上实现图的操作，因此主要学习图的存储结构，以及若干图的操作的实现。

一、定义#

图（Graph） $G$ 由两个集合 $V$ 和 $E$ 组成，记为 $G=(V, E)$ ，其中 $V$ 是顶点的有穷非空集合， $E$ 是 $V$ 中顶点偶对的有穷集合，这些顶点偶对称为边。 $V(G)$ 和 $E(G)$ 通常分别表示图 $G$ 的顶点集合和边集合， $E(G)$ 可以为空集。若 $E(G)$ 为空，则图 $G$ 只有顶点而没有边。

如上图所示，左图为有向图，右图为无向图。

对于图 $G$ ，若边集 $E(G)$ 为有向边的集合，则称该图为有向图；若边集 $E(G)$ 为无向边的集合，则称该图为无向图。

在有向图中，顶点对 $<x, y>$ 是有序的，它称为从顶点 x 到顶点 y 的一条有向边。因此， $<x, y>$ 与 $<y, x>$ 是不同的两条边。顶点对用一对尖括号括起来，x 是有向边的始点，y 是有向边的终点。 $<x, y>$ 也称作一条弧，其中 x 为弧尾，y 为弧头。

1
A ──→ B
2
│     │
3
↓     ↓
4
C ──→ D

<A,B> 表示从顶点 A 到顶点 B 的有向边
<A,C> 表示从顶点 A 到顶点 C 的有向边
<B,D> 表示从顶点 B 到顶点 D 的有向边
<C,D> 表示从顶点 C 到顶点 D 的有向边
箭头表示方向，<A,B> ≠ <B,A>

在无向图中，顶点对 $(x, y)$ 是无序的，它称为与顶点 x 和顶点 y 相关联的一条边。这条边没有特定的方向， $(x, y)$ 与 $(y, x)$ 是同一条边。为了有别于有向图，无向图的顶点对用一对圆括号括起来。

1
A ---- B
2
|      |
3
|      |
4
C ---- D

(A,B) 表示顶点 A 和顶点 B 之间的无向边
(A,C) 表示顶点 A 和顶点 C 之间的无向边
(B,D) 表示顶点 B 和顶点 D 之间的无向边
(C,D) 表示顶点 C 和顶点 D 之间的无向边
没有方向性，(A,B) = (B,A)

二、基本术语#

下面介绍图结构中的一些基本术语（注：n 表示图中顶点数目，e 表示边的数目）。

子图：假设右两个图 $G=(V, E)$ 和 $G'=(V', E')$ ，如果 $V′⊆V$ 且 $E′⊆E$ ，则称 $G'$ 为 $G$ 的子图。如下图所示，图（b）是图（a）的子图。

无向完全图和有向完全图：对于无向图，若具有 $n(n-1)/2$ 条边，则称为无向安全图。对于有向图，若具有 $n(n-1)$ 条弧，则称为有向完全图。
稀疏图和稠密图：边或弧很少（如 $e<nlog2⁡n$ ）的图称为稀疏图，反之称为稠密图。
权和网：若在图的每条边上标上具有某种含义的数值，该数值称为该边上的权值。这些权值可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。
邻接点：对于无向图 G，如果图的边 $(v,v′)∈E$ ，则称顶点 $v$ 和 $v'$ 互为邻接点，即 v 和 v’相邻接。边 $(v, v')$ 依附于顶点 $v$ 和 $v'$ ，或者说边 $(v, v')$ 与顶点 $v$ 和 $v'$ 相关联。
度、入度和出度：顶点 $v$ 的度是指和 $v$ 相关联的边的数目，记为 $TD(v)$ 。例如，下图（b）中的顶点 $v_1$ 的度是 2。

对于有向图，顶点 v 的度分为入度和出度。入度是以顶点 v 为头的弧的数目，记为 $ID(v)$ ；出度是以顶点 v 为尾的弧的数目，记为 $OD(v)$ 。顶点 v 的度为 $TD(v)=ID(v)+OD(v)$ 。

例如，下图（a）中的顶点 $v_1$ 的入度 $ID( v_1 )=1$ ，出度 $OD( v_1 )=2$ ，度 $TD( v_1 )=ID( v_1 )+OD( v_1 )=3$

路径和路径长度：在无向图 $G$ 中，从顶点 $v$ 到顶点 $v'$ 的路径是一个顶点序列 $(v=vi,0,vi,1,...,vi,m=v′)$ ，其中 $(vi,j−1,vi,j)∈E$ ， $1≤j≤m$ 。
如果 G 是有向图，则路径也是有向的，顶点序列应满足 $<vi,j−1,vi,j>∈E$ ， $1≤j≤m$ 。路径长度是一条路径上经过的边或弧的数目。
回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
连通、连通图和连通分量：在无向图 $G$ 中，如果从顶点 $v$ 到顶点 $v'$ 有路径，则称 $v$ 和 $v'$ 是连通的。如果对于图中任意两个顶点 $v_i,v_j∈V$ ， $v_i$ 和 $v_j$ 都是连通的，则称 $G$ 是连通图。而所谓连通分量，指的是无向图中的极大连通子图。例如，下图（a）就是一个连通图，而图（b）则是非连通图，但它有 3 个连通分量，见图（c）。

强连通图和强连通分量：在有向图 $G$ 中，如果对于每一对 $v_i,v_j∈V$ ， $v_i≠v_j$ ，从 $v_i$ 到 $v_j$ 和从 $v_j$ 到 $v_i$ 都存在路径，则称 $G$ 是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。例如，下图（a）就是一个强连通图，而图（b）则不是强连通图，但它有两个强连通分量，见图（c）。

连通图的生成树：一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的 n-1 边，这样的连通子图称为连通图的生成树。例如，下图（c）是图（a）的最大连通分量的一棵生成树。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。

有向树和生成森林：有一个顶点的入度为 0，其余顶点的入度均为 1 的有向图称为有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。例如，下图（a）是一棵有向树，图（b）是一个有向图，它的森林是图（c）。

三、存储结构#

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序存储结构，但可以借助二维数组来表示元素之间的关系，即邻接矩阵表示法。

另一方面，由于图的任意两个顶点间都可能存在关系，因此，用链式存储表示图是很自然的事，图的链式存储有多种，有邻接表、十字链表和邻接多重表，应根据实际需要的不同选择不同的存储结构。

3.1、邻接矩阵#

3.1.1、表示法#

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设 $G(V, E)$ 是具有 n 个顶点的图，则 $G$ 的邻接矩阵是具有如下性质的 n 阶方阵：

$A[i][j] = \begin{cases} 1 & \text{<}v_i, v_j\text{>} \text{ 或 } (v_i, v_j) \in E \\ 0 & \text{其他} \end{cases}$

例如，下图为一个有向图和它的邻接矩阵:

若 G 是网，则邻接矩阵可以定义为：

$A[i][j] = \begin{cases} 1 & \text{<}v_i, v_j\text{>} \text{ 或 } (v_i, v_j) \in E \\ 0 & \text{其他} \end{cases}$

其中， $w_{ij}$ 表示边上的权值， ∞ 表示计算机允许的、大于所有边上权值的数。例如，下图为一个有向网和它的邻接矩阵:

用邻接矩阵表示法表示图，除了一个用于存储邻接矩阵的二维数组外，还需要用一个一维数组来存储顶点信息。在 C 语言中，图的邻接矩阵类型描述如下：

1
// 表示极大值
2
#define MaxInt 32767
3
// 最大顶点数
4
#define MVNum 100
5
6
// 假设顶点的数据类型为字符型
7
typedef char VerTexType;
8
9
// 假设边的权值类型为整型
10
typedef int ArcType;
11
12
typedef struct {
13
    // 顶点表
14
    VerTexType vexs[MVNum];
15
    // 邻接矩阵
16
    ArcType arcs[MVNum][MVNum];
17
    // 图的当前顶点数和边数
18
    int vexnum, arcnum;
19
}AMGraph;

3.1.2、创建无向网#

已知一个图的顶点和边，使用邻接矩阵表示法来创建此图的方法比较简单，下面以一个无向网为例来说明创建图的算法。该算法的步骤为：

输入总顶点数和总边数。
依次输入顶点的信息存入顶点表中。
初始化邻接矩阵，使每个权值初始化为极大值。
构造邻接矩阵。依次输入每条边依附的顶点和其权值，确定两个顶点在图中的位置之后，使相应边赋予相应的权值，同时使其对称边赋予相同的权值。

相应的算法描述为：

1
// 采用邻接矩阵表示法，创建无向网G
2
Status CreateUDN(AMGraph &G) {
3
    // 输入总顶点数和总边数
4
    cin>>G.vexnum>>G.arcnum;
5
6
    // 依次输入顶点信息
7
    for(i=0; i<G.vexnum; ++i)
8
        cin>>G.vexs[i]
9
10
    // 初始化邻接矩阵，边的权值均为极大值MaxInt
11
    for(i=0; i<G.vexnum; ++i)
12
        for(j=0; j<G.vexnum; ++j)
13
            G.arcs[i][j]=MaxInt;
14
15
    // 构造邻接矩阵
16
    for(k=0;k<G.arcnum;++k) {
17
        // 输入一条边依附的顶点和其权值
18
        cin>v1>>v2>>w;
19
        // 确定v1和v2在G中的位置，即顶点数组的下标
20
        i=LocateVex(G,v1);
21
        j=LocateVex(G,v2);
22
        // 边<v1, v2>的权值置为w
23
        G.arcs[i][j]=w;
24
        // 置<v1, v2>的对称边<v2, v1>的权值置为w
25
        G.arcs[j][i]=G.arcs[i][j];
26
    }
27
28
    return OK;
29
}

该算法的时间复杂度是 $O(max(n2,n∗e))$

若要建立无向图，只需对上述算法做两处小的改动：一是初始化邻接矩阵时，将边的权值均初始化为 0；二是构造邻接矩阵时，将权值 w 改为常量值 1 即可。同样，将该算法稍做修改即可建立一个有向网或有向图。

3.1.3、优缺点#

邻接矩阵表示法的优点是：

便于判断两个顶点之间是否有边，即根据 $A[i][j]=0$ 或 1 来判断。
便于计算各个顶点的度。对于无向图，邻接矩阵第 i 行元素之和就是顶点 i 的度；对于有向图，第 i 行元素之和就是顶点 i 的出度，第 i 列元素之和就是顶点 i 的入度。

邻接矩阵表示法的缺点是：

不便于增加和删除顶点。
不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为 O(n2) 。
空间复杂度高。如果是有向图，n 个顶点需要 n2 个单元存储边。如果是无向图，因其邻接矩阵是对称的，所以对规模较大的邻接矩阵可以采用压缩存储的方法，仅存储下三角（或上三角）的元素，这样需要 $n(n−1)/2$ 个单元即可。但无论以何种方式存储，邻接矩阵表示法的空间复杂度均为 $O(n2)$ ，这对于稀疏图而言尤其浪费空间。

3.2、邻接表#

3.2.1、表示法#

邻接表（Adjacency List）是图的一种链式存储结构。

在邻接表中，对图中每个顶点建立一个单链表，把与 vi 相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息，把这一结点看成链表的表头，其余结点存放有关边的信息，这样邻接表便由两部分组成：表头结点表和边表。

表头结点表，由所有表头结点以顺序结构的形式存储，以便可以随机访问任一顶点的边链表。表头结点包括数据域（data）和链域（firstarc）两部分，如下图（a）所示。其中，数据域用于存储顶点 vi 的名称或其他信息；链域用于指向链表中第一结点（即与顶点 vi 相邻接的第一个邻接点）。

边表，由表示图中顶点间关系的 2n 个边链表组成。边链表中边结点包括邻接点域、数据域和链域三部分，如下图（b）所示。其中，邻接点域指示与顶点 vi 相邻接的点在图中的位置；数据域存储和边相关的信息，如权值等；链域指示与顶点 vi 相邻接的下一个邻接点。

例如，在下图（a）中有两个图，图（b）则是它们对应的邻接表。

在无向图的邻接表中，顶点 $v_i$ 的度恰为第 i 个链表中的结点数；而在有向图中，第 i 个链表中的结点个数只是顶点的出度，为求入度，必须遍历整个邻接表。在所有链表中，其邻接点域的值为 i 的结点的个数就是顶点 $v_i$ 的入度。有时，为了便于确定顶点的入度，可以建立一个有向图的逆邻接表，即对每个顶点 $v_i$ 建立一个链接所有进入 $v_i$ 的边的表。例如，下图（c）为有向图的逆邻接表。

根据上述讨论，要定义一个邻接表，需要定义存放顶点的头结点和表示边的边结点。在 C 语言中，图的邻接表存储结构的类型描述如下：

1
// 最大顶点数
2
#define MVNum 100
3
4
// 边结点
5
typedef struct ArcNode {
6
    // 该边所指向的顶点的位置（邻接点域）
7
    int adjvex;
8
    // 指向下一条边的指针（链域）
9
    struct ArcNode *nextarc;
10
    // 和边相关的信息（数据域）
11
    OtherInfo info;
12
}ArcNode;
13
14
// 顶点信息
15
typedef struct VNode {
16
    VerTexType data;
17
    // 指向第一条依附该顶点的边的指针
18
    ArcNode *firstarc;
19
}VNode, AdjList[MVNum];
20
21
// 邻接表
22
typedef struct {
23
    AdjList vertices;
24
    // 图的当前顶点数和边数
25
    int vexnum, arcnum;
26
}ALGraph;

3.2.2、创建无向图#

基于邻接表表示法创建一个图，需要创建其相应的顶点表和边表。下面以一个无向图为例来说明创建图的算法。该算法步骤为：

输入总顶点数和总边数。
依次输入顶点的信息存入顶点表中，使每个表头结点的指针域初始化为 NULL。
创建邻接表。依次输入每条边依附的两个顶点，确定这两个顶点的序号 i 和 j 之后，将此边结点分别插入 $v_i$ 和 $v_j$ 对应的两个边链表的头部。

相应的算法描述为：

1
// 采用邻接表表示法，创建无向图G
2
Status CreateUDG(ALGraph &G) {
3
    // 输入总顶点数，总边数
4
    cin>>G.vexnum>>G.arcnum;
5
6
    // 输入顶点信息，构造表头结点表
7
    for(i=0; i<G.vexnum; ++i) {
8
        // 输入顶点的值
9
        cin>>G.vertices[i].data;
10
        // 初始化表头结点的指针域为NULL
11
        G.vertices[i].firstarc=NULL;
12
    }
13
14
    // 输入各边，构造邻接表
15
    for(k=0; k<G.arcnum; ++k) {
16
        // 输入一条边依附的两个顶点
17
        cin>>v1>>v2;
18

19
        // 确定v1和v2在G中的位置，即顶点在G.vertices中的下标
20
        i=LocateVex(G,v1);
21
        j=LocateVex(G,v2);
22
23
        // 生成一个新的边结点*p1
24
        p1=new ArcNode;
25
        // 邻接点序号为j
26
        p2->adjvex=j;
27
        // 将新结点*p1插入到顶点vi的边表头部
28
        p1->nextarc=G.vertices[i].firstarc;
29
        G.vertices[i].firstarc=p1;
30
31
        // 生成另一个对称的新边结点*p2
32
        p2=new ArcNode;
33
        // 邻接点序号为i
34
        p2->adjvex=i;
35
        // 将新结点*p2插入到顶点vj的边表头部
36
        p2->nextarc=G.vertices[j].firstarc;
37
        G.vertices[j].firstarc=p2;
38
    }
39
40
    return OK;
41
}

该算法的时间复杂度是 $O(n*e)$ 。

建立有向图的邻接表与此类似，只是更加简单，每读入一个顶点对序号<i, j>，仅需生成一个邻接点序号为 j 的边表结点，并将其插入到 $v_i$ 的边链表头部即可。若要创建网的邻接表，可以将边的权值存储在 info 域中。

需要注意的是，一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法，以及边的输入次序。

3.2.3、优缺点#

邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。与邻接矩阵相比，邻接表有其自己的优缺点。其优点是：

便于增加和删除顶点。
便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为 O(n+e)。
空间效率高。对于一个具有 n 个顶点 e 条边的图 G，若 G 是无向图，则在其邻接表表示中有 n 个顶点表结点和 2e 个边表结点；若 G 是有向图，则在它的邻接表表示或逆邻接表表示中均有 n 个顶点表结点和 e 个边表结点。因此，邻接表或逆邻接表表示的空间复杂度为 O(n+e)，适合表示稀疏图。对于稠密图，考虑到邻接表中要附加链域，因此常采取邻接矩阵表示法。

其缺点是：

不便于判断顶点之间是否有边，要判定和之间是否有边，就需扫描第 i 个边表，最坏情况下要耗费 O(n)时间。
不便于计算有向图各个顶点的度。对于无向图，在邻接表表示中顶点的度是第 i 个边表中的结点个数。在有向图的邻接表中，第 i 个边表上的结点个数是顶点 vi 的出度，但求 vi 的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易，而求顶点的出度较难。

3.3、十字链表#

十字链表（Orthogonal List）是有向图的另一种链式存储结构。它可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构形式如下图所示。

在弧结点中有 5 个域：其中尾域 tailvex 和头域 headvex 分别指示弧尾和弧头这两个顶点在图中的位置，链域 hlink 指向弧头相同的下一条弧，而链域 tlink 指向弧尾相同的下一条弧，info 域指向该弧的相关信息。弧头相同弧在同一链表上，弧尾相同的弧也在同一链表上。而它们的头结点即为顶点结点。

顶点结点由 3 个域组成：其中 data 域存储和顶点相关的信息，如顶点的名称等；firstin 和 firstout 为两个链域，分别指向以该顶点为弧头或弧尾的第一个弧结点。

例如，下图（b）是下图（a）所示图的十字链表。

若将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的链式存储结构，在图的十字链表中，弧结点所在的链表非循环链表，结点之间相对位置自然形成，不一定按顶点序号有序，表头结点即顶点结点，它们之间不是链接，而是顺序存储。

在 C 语言中，有向图的十字链表存储结构的类型描述如下：

1
#define MAX_VERTEX_NUM 20
2
3
typedef struct ArcBox {
4
    // 该弧的尾和头结点的位置
5
    int tailvex,headvex;
6
    // 分别为弧头相同和弧尾相同的弧的链域
7
    struct ArcBox *hlink,*tlink;
8
    // 该弧相关信息的指针
9
    InfoType *info;
10
}ArcBox;
11
12
typedef struct VexNode {
13
    VertexType data;
14
    // 分别指向该顶点的第一条入弧和出弧
15
    ArcBox *firstin, *firstout;
16
}VexNode;
17
18
typedef struct {
19
    // 表头向量
20
    VexNode xlist[MAX_VERTEX_NUM];
21
    // 有向图的当前顶点数和弧数
22
    int vexnum, arcnum;
23
}QLGraph;

只要输入 n 个顶点的信息和 e 条弧的信息，便可建立该有向图的十字链表。建立十字链表的时间复杂度和建立邻接表是相同的。在十字链表中既容易找到以 vi 为尾的弧，也容易找到以 vi 为头的弧，因而容易求得顶点的出度和入度（或需要，可在建立十字链表的同时求出）。在某些有向图的应用中，十字链表是很有用的工具。

3.4、邻接多重表#

邻接多重表（Adjacency Multilist）是无向图的另一种链式存储结构。虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息。但是，在邻接表中每一条边 (vi,vj) 有两个结点，分别在第 i 个和第 j 个链表中，这给某些图的操作带来不便。例如，在某些图的应用问题中，需要对边进行某种操作，如对已被搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。

邻接多重表的结构和十字链表类似。在邻接多重表中，每一条边用一个结点表示，它由 6 个域组成。其中，mark 为标志域，可用以标记该条边是否被搜索过；ivex 和 jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点 ivex 的边；jlink 指向下一条依附于顶点 jvex 的边；info 指向和边相关的各种信息的指针域。

每一个顶点也用一个结点表示，它由两个域组成。其中，data 域存储和该顶点相关的信息，firstedge 域指示第一条依附于该顶点的边。

例如，下图（b）是下图（a）所示图的邻接多重表。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。可见，对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。因此，除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。

在 C 语言中，邻接多重表的类型描述如下：

1
#define MAX_VERTEX_NUM 20
2
3
typedef enum{unvisited, visited} VisitIf;
4
5
typedef struct EBox {
6
    // 访问标记
7
    VisitIf mark;
8
    // 该边依附的两个顶点的位置
9
    int ivex, jvex;
10
    // 分别指向依附这两个顶点的下一条边
11
    struct EBox *ilink, *jlink;
12
    // 该边信息指针
13
    InfoType *info;
14
}Ebox;
15
16
typedef struct VexBox {
17
    VertexType data;
18
    // 指向第一条依附该顶点的边
19
    EBox *firstedge;
20
}VexBox;
21
22
typedef struct {
23
    VexBox adjmulist[MAX_VERTEX_NUM];
24
    // 无向图的当前顶点数和边数
25
    int vexnum, edgenum;
26
}AMLGraph;

音乐

音乐