7. 第五章：图

7.1 图的基本概念和基本术语

7.1.1 定义：

树是 个结点的有限集合， 时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

1）有且仅有一个特定的称为根的结点。

2）当 时，其余结点可分为 个互不相交的有限集合 ，其中每一个集合本身又是一棵树，并且称为根结点的子树。

图 由顶点集 和边集E组成，记为

1. 表示图 中顶点的有限非空集。用 表示图 中顶点的个数，也称为图 的阶
2. 表示图 中顶点之间的关系（边）集合。用 表示图 中边的条数。

7.1.2 分类

有向图

若图 中每条边都是有方向的，则称为有向图。有向边也称为弧，每条弧都是由两个顶点组成的有序对。

• 有向边（弧）的有限集合
• 弧是顶点的有序对
• 
• 是弧尾， 是弧头
• 邻接到 或 邻接自

无向图

若图 中每条边都是没有方向的，则称为无向图，每条边都是两个顶点组成的无序对。

• 无向边的有限集合
• 边是顶点的无序对
• 
• 
• 互为邻接点

注意：尖括号 表示有序对，圆括号 表示无序对。

7.1.3 简单图

既不含平行边也不含环的图称为简单图

• 1.不存在顶点到自身的边
• 2.同一条边不重复出现

7.1.4 多重图

• 若图G中某两个结点之间的边数多于一条，又允许顶点通过通过同一个边和自己关联

7.1.5 完全图

• 无向完全图：如果任意两个顶点之间都存在边
• 有向完全图：如果任意两个顶点之间都存在方向相反的两条弧

7.1.6 子图与生成子图

子图：设有两个图 ，则称G1是G的子图。从图中选择若干个顶点、若干条边构成的图称为原图的子图。

生成子图：从图中选择所有顶点，若干条边构成的图称为原图的生成子图。

7.1.7 连通图：图中任意两个顶点都是连通的

连通图：在无向图中，如果顶点vi到vj有路径，则称vi和vj是连通的。如果图中任何两个顶点都是连通的，则称G为连通图。

7.1.8 连通分量：无向图中的极大连通子图

连通分量：无向图G的极大连通子图称为G的连通分量。

• 连通：顶点A到顶点B有路径
• 极大：

• 1.顶点足够多
• 2.极大连通子图包含这些依附这些顶点的所有边

• 结论1:如果一个图有n个顶点，并且有小于n-1条边，则此图必是非连通图。

找连通分量的方法：从选取一个顶点开始，以这个顶点作为一个子图，然后逐个添加与这个子图相连的顶点和边直到所有相连的顶点都加入该子图

7.1.9 强连通：顶点V到顶点W和顶点W到顶点V都有路径

7.1.10 强连通图和强连通分量

强连通图：在有向图中，如果图中任何两个顶点vi到vj有路径，且vj到vi也有路径，则称G为强连通图。

强连通分量：有向图G的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，如果再加入一个顶点，该子图不再是强连通的。

7.1.11 连通图的生成树：包含图中全部n个顶点，但是只有n-1条边的极小连通子图

• 结论2:生成树去掉一条边则变成非连通图，加上一条边就会形成回路。

7.1.12 度：以该顶点为一个端点的边数目

• 无向图中顶点V的度是指依附于该顶点的边的条数，记为
• 有向图中顶点V的度分为出度和入度

• 入度（ID）是以顶点v为终点的有向边的数目
• 出度（OD）是以顶点V为起点的有向边的数目

7.1.13 简单路径和简单回路：

回路（环）：第一个顶点和最后一个顶点相同的路径。

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。

简单回路：顶点不重复出现的路径称为简单路径。对于回路，除了第一个和最后一个顶点其余顶点不重复出现的回路称为简单回路

7.1.14 权和网：

在实际应用中，经常在边上标注如距离、时间、耗费等数值，该数值称为边的权值。带权的图称为网

图中每条边考研赋予一定意义的数值，这个数值叫做这条边的权，有权值得图称为带权图，也叫做网

7.1.15 路径和路径长度：

顶点p到q之间的路径是指顶点序列怕保存的，p,a,b,c,d,……q。路径上边的数目就是路径长度

7.1.16 回路（环）：

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

7.1.17 距离：

从顶点u到v的最短路径长度。不存在路径则为无穷

7.1.18 邻接和关联

邻接是指顶点和顶点之间的关系，关联是指边和顶点之间的关系。有边/弧相连的两个顶点之间的关系，如无向边 ，则称 和 互为邻接点；有向边 ，则称 邻接到 ， 邻接于 。若存在 或 ，则称该边或弧关联于 和 ，如图7-10所示。在图中，每条边关联（依附）两个顶点。

7.1.19 路径、路径长度和距离

路径：接续的边的顶点构成的序列。

路径长度：路径上边或弧的数目。

距离：从顶点到另一顶点的最短路径长度。

7.1.20 回路（环）、简单路径和简单回路

回路（环）：第一个顶点和最后一个顶点相同的路径。在图7-13中，v2、v4、v3、v2是回路。

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。在图7-13中，s、v2、v4、v3、t是简单路径，而s、v2、v4、v3、v2、v1不是简单路径。

简单回路：除路径起点和终点相同外，其余顶点均不相同的路径。在图7-13中，v2、v4、v3、v2是简单回路。

7.2 图的存储结构

图的结构比较复杂，任何两个顶点之间都可能有关系。如果采用顺序存储，则需要使用二维数组表示元素之间的关系，即邻接矩阵（adjacency matrix），也可以使用边集数组，把每条边顺序存储起来。如果采用链式存储，则有邻接表、十字链表和邻接多重表等表示方法。其中，邻接矩阵和邻接表是最简单、最常用的存储方法。

7.2.1 顺序存储_邻接矩阵

邻接矩阵是表示顶点之间关系的矩阵。邻接矩阵存储方法，需要用一个一维数组存储图中顶点的信息，用一个二维数组存储图中顶点之间的邻接关系，存储顶点之间邻接关系的二维数组称为邻接矩阵。

1）无向图的邻接矩阵

在无向图中，如果 到 有边，则邻接矩阵 ，否则 。

• 1）无向图的邻接矩阵是对称矩阵，并且是唯一的。
• 2）第i行或第i列非零元素的个数正好是第i个顶点的度。

2）有向图的邻接矩阵

在无向图中，如果 到 有边，则邻接矩阵 ，否则 。

注意：尖括号 表示有序对，圆括号 表示无序对。

• 1）有向图的邻接矩阵不一定是对称的。
• 2）第i行非零元素的个数正好是第i个顶点的出度，第i列非零元素的个数正好是第i个顶点的入度。

3）网的邻接矩阵

网是带权图，需要存储边的权值，则邻接矩阵表示为：

其中， 表示边上的权值， 表示无穷大。尖括号 表示有序对，圆括号 表示无序对。当i=j时， 也可以设置为0。

邻接矩阵的数据结构定义

7.2.2 链式存储

邻接表

邻接表（Adjacency List）是图的一种链式存储方法。邻接表包含两部分：顶点和邻接点。顶点包括顶点信息和指向第一个邻接点的指针。邻接点包括邻接点的存储下标和指向下一个邻接点的指针。顶点 的所有邻接点构成一个单链表。

邻接表的数据结构定义

邻接表的优缺点

（1）优点

• 便于增删顶点。
• 便于访问所有邻接点。访问所有顶点的邻接点，时间复杂度为O(n+e)。
• 空间复杂度低。顶点表占用n个空间，无向图的邻接点表占用n+2e个空间，有向图的邻接点表占用n+e个空间，总体空间复杂度为O(n+e)，而邻接矩阵的空间复杂度为O(n2)，因此对于稀疏图可采用邻接表存储，对于稠密图可以采用邻接矩阵存储。

（2）缺点

• 不便于判断两顶点之间是否有边。要判断两顶点是否有边，需要遍历该顶点后面的邻接点链表。
• 不便于计算各顶点的度。在无向图邻接表中，顶点的度为该顶点后面单链表中的节点数；在有向图邻接表中，顶点的出度为该顶点后面单链表中的节点数，但求入度困难；在有向图逆邻接表中，顶点的入度为该顶点后面单链表中的节点数，但求出度困难。

十字链表（有向图）

十字链表（Orthogonal List）是有向图的另一种链式存储结构。它结合了邻接表和逆邻接表的特性，可以快速访问出弧和入弧，得到出度和入度。十字链表也包含两部分：顶点节点和弧节点。顶点节点包括顶点信息和两个指针（分别指向第一个入弧和第一个出弧），弧节点包括两个数据域（弧尾、弧头）和两个指针域（分别指向同弧头和同弧尾的弧）。

邻接多重表（无向图）

邻接多重表（adjacency multilist）是无向图的另一种链式存储结构。邻接表的关注点是顶点，而邻接多重表的关注点是边，适合对边做访问标记、删除边等操作。邻接多重表类似十字链表，也包含两部分：顶点节点和边节点。顶点节点包括顶点信息和一个指针（指向第一个依附于该顶点的边），边节点包括两个数据域（顶点i、顶点j）和两个指针域（分别指向依附于i、j的下一条边）。如果需要标记是否被访问过，边节点还可以增加一个标志域。

7.2.3 图的4种存储方法比较

7.3 图的遍历

7.3.1 深度优先遍历

深度优先搜索(DFS:Depth-First-Search):深度优先搜索类似于树的先序遍历算法

算法步骤（递归）

1）初始化图中所有顶点未被访问。

2）从图中的某个顶点v出发，访问v并标记已访问。

3）依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复第2步和第3步。

算法步骤（非递归）

1）初始化图中所有顶点未被访问。

2）从图中的某个顶点v出发，访问v并标记已访问。

3）访问最近访问顶点的未被访问邻接点w1，再访问w1的未被访问邻接点w2……直到当前顶点没有未被访问的邻接点时停止。

4）回退到最近访问过且有未被访问的邻接点的顶点，访问该顶点的未被访问的邻接点；

5）重复第3步和第4步，直到所有的顶点都被访问过。

空间复杂度：由于DFS是一个递归算法，递归是需要一个工作栈来辅助工作，最多需要图中所有顶点进栈，所以时间复杂度为O(|V|)

时间复杂度：

1)邻接表：遍历过程的主要操作是对顶点遍历它的邻接点，由于通过访问边表来查找邻接点，所以时间复杂度为O(|E|),访问顶点时间为O(|V|),所以总的时间复杂度O(|V|+|E|)

2)邻接矩阵：查找每个顶点的邻接点时间复杂度为O(|V|),对每个顶点都进行查找，所以总的时间复杂度为O(|V|2)

7.3.2 广度优先遍历

广度优先搜索(BFS:Breadth-First-Search):广度优先搜索类似于树的层序遍历算法

算法步骤

1）初始化图中所有顶点未被访问，初始化一个空队列。

2）从图中的某个顶点v出发，访问v并标记已访问，将v入队。

3）如果队列非空，则继续执行，否则算法结束。

4）队头元素v出队，依次访问v的所有未被访问邻接点，标记已访问并入队，转向步骤3）。

空间复杂度：BFS需要借助一个队列，n个顶点均需要入队一次，所以最坏情况下n个顶点在队列，那么则需要O(|V|)的空间复杂度。    

时间复杂度：

1)邻接表：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，就需要访问这个顶点的所有边，所以时间复杂度为O(|E|)。所以总的时间复杂O(|V|+|E|)

2)邻接矩阵：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，需要遍历一遍矩阵的一行，所以时间复杂度为O(|V|),所以总的时间复杂度为O(|V|2)

7.4 图的应用

7.4.1 最小生成树

• 普利姆（Prlm）

①从图中找第一个起始顶点v0，作为生成树的第一个顶点，然后从这个顶点到其他顶点的所有边中选一条权值最小的边。然后把这条边的另一个顶点v和这条边加入到生成树中。

②对剩下的其他所有顶点，分别检查这些顶点与顶点v的权值是否比这些顶点在lowcost数组中对应的权值小，如果更小，则用较小的权值更新lowcost数组。

③从更新后的lowcost数组中继续挑选权值最小而且不在生成树中的边，然后加入到生成树。

④反复执行②③直到所有所有顶点都加入到生成树中。

双重循环，外层循环次数为n-1，内层并列的两个循环次数都是n。故普利姆算法时间复杂度为O(n2)而且时间复杂度只和n有关，所以适合稠密图

• 克鲁斯卡尔（Kruskal）

将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。

克鲁斯卡尔算法操作分为对边的权值排序部分和一个单重for循环，它们是并列关系，由于排序耗费时间大于单重循环，所以克鲁斯卡尔算法的主要时间耗费在排序上。排序和图中边的数量有关系，所以适合稀疏图

7.4.2 最短路径

• 迪杰斯特拉

一个源点到其余顶点的最短路径

该算法设置一个集合 记录已求得的最短路径的顶点，可用一个数组 来实现，初始化为0，当 时表示将顶点 放入S中，初始时把源点 放入 中。此外，在构造过程中还设置了两个辅助数组： ：记录了从源点 到其他各顶点当前的最短路径长度， 初值为 。 表示从源点到顶点 之间的最短路径的前驱结点，在算法结束时，可根据其值追溯得到源点 到顶点 的最短路径。假设从顶点0出发，也就是顶点0为源点，集合 最初只包含顶点0，邻接矩阵 表示带权有向图， 表示有向边 的权值，若不存在有向边 ，则 为 。

Dijkstra算法的步骤如下：

1）初始化：集合S初始为{0}，dist[]的初始值dist[i]=arcs[0][i]，i=1，2，…，n-1。

2）找出dist[]中的最小值dist[j]，将顶点j加入集合S，即修改s[vj]=1。

3）修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：如果dist[j] + arcs[j][k]< dist[k]，则令dist[k]=dist[j] + arcs[j][k]。另外更新path[k]=j(也就是顶点j加入集合之后如果有新的路径使得到顶点k路径变短的话就将到顶点k的路径长度修改成较短的)

4）重复2）～3）操作共n-1次，直到所有的顶点都包含在S中。

• 弗洛伊德

所有顶点到所有顶点的最短路径

算法思想：递推产生一个 阶方阵序列 其中 表示从顶点 到顶点 的路径长度， 表示绕行第 个顶点的运算步骤。初始时，对于任意两个顶点 和 ，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以 作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点 作为中间顶点。如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径

• 非带权图

两点之间经过边数最少的路径

• 带权图

两点之间经过的边上权值之和最小的路径

7.4.3 拓扑排序

一个无环的有向图称为有向无环图（Directed Acycline Graph，DAG）。

• AOV

• 如果我们把每个环节看成图中一个顶点，在这样一个有向图中，用顶点表示活动，用弧表示活动之间的优先关系，那么这样的有向图称为AOV网(Activity On Vertex)

• 拓扑排序就是对一个有向图构造拓扑序列的过程，构造会有两种结果：如果此图全部顶点都被输出了，说明它是不存在回路的AOV网；如果没有输出全部顶点，则说明这个图存在回路，不是AOV网。
• 拓扑排序算法：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为弧尾的弧。重复这个步骤直到输出图中全部顶点，或者找不到入度为0的顶点为止。

拓扑排序的基本思想如下。

1）选择一个无前驱的顶点并输出。

2）从图中删除该顶点和该顶点的所有发出边。

3）重复第1步和第2步，直到不存在无前驱的顶点。

4）如果输出的顶点数小于AOV网中的顶点数，则说明网中有环，否则输出的序列即拓扑序列。

7.4.4 关键路径

AOV网可以反映活动之间的先后制约关系，但在实际工程中，有时活动不仅有先后顺序，还有持续时间，即必须经过多长时间该活动才可以完成。这时需要另外一种网络——AOE（Activity On Edge）网，即边表示活动的网。AOE网是一个带权的有向无环图，顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间。

AOE(Activity On Edge):在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网称为AOE网。

如何确定关键路径呢？

首先要清楚4个问题：事件的最早发生时间、最迟发生时间，活动的最早发生时间、最迟发生时间。

（1）事件 的最早发生时间

事件 的最早发生时间是从源点到 的最大路径长度。

（2）事件 的最迟发生时间

事件 的最迟发生时间不能影响其所有后继的最迟发生时间。 的最迟发生时间不能大于其后继 的最迟发生时间减去活动 的持续时间。

（3）活动 的最早发生时间

只要事件 发生了，活动 就可以开始，因此活动ai的最早发生时间等于事件 的最早发生时间。

（4）活动 的最迟发生时间

活动 的最迟开始时间不能耽误事件 的最迟开始时间，因此活动 的最迟开始时间等于事件 的最迟开始时间减去活动 的持续时间 。

7.5 图的小结