资源简介

(共66张PPT)
第5章 章 图
图的基本概念
图的存储
图的创建
图的遍历
图的基本概念
图的存储
图的创建
5.2
5.3
5.1
点击查看本小节知识架构
点击查看本小节知识架构
点击查看本小节知识架构
图的遍历
5.4
点击查看本小节知识架构
学习目标
掌握
掌握
掌握
掌握
掌握图的基本概念与专业术语
1
掌握编写图的操作代码
4
2
掌握图的存储结构
3
掌握图的创建方法与遍历方法
本章将介绍另一种非线性数据结构——图。图在高级嵌入式系统中应用非常广泛，车载GPS导航系统就是图的典型应用实例。图形结构相较于树形结构要更加复杂，树形结构中的结点之间存在一对多的关系，而在图形结构中，结点之间的关系可以是任意的。本章将从图的概念与专业术语开始介绍，重点讲解图的存储结构以及通过代码实现图的基本操作，包括创建、遍历等。
5.1 图的基本概念
5.1.1
图的定义
返回目录
5.1.2
图的基本术语
5.1.1 图的定义
在图形结构中，结点之间的关系是任意的，每个结点都可以有任意个前驱或后继。换一种方式说，图是由任意个顶点和任意条边组成的结构，顶点可以看作数据元素，边是数据元素之间存在的关系。
图的形式化定义为 G=(V,E)，其中：G表示一个图，V表示图中顶点的集合，E表示图中边（顶点间的关系）的集合。图的逻辑结构如图所示。
图中，顶点共有9个，即 V={A,B,C,D, E,F,G,H,I}，边共有14条，即 E={AB,AC,AD,BD, BE,CD,CG,CF,DG,DH,DE,EI,GH,HI}。
5.1.2 图的基本术语
1.无向图
如果顶点 V i 到顶点 V j 之间的边没有方向，则称这条边为无向边，用无序偶对(V i ,V j )来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。如图所示。
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有 条边。如图所示。
5.1.2 图的基本术语
2.有向图
如果顶点V i 到顶点 V j 之间的边有方向，则称这条边为有向边（也可以称为弧），从顶点V i 到顶点 V j 的有向边用有序偶对来表示。V i 称为弧尾，V j 称为弧头。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。如图所示。
在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有 n×（n－1）条边。如图所示。
5.1.2 图的基本术语
在有向图中，如不存在顶点到自身的边，且同一条边不重复出现，则称这样的图为简单图。图所示为非简单图。（本章介绍的图都是简单图）
5.1.2 图的基本术语
3.稀疏图与稠密图
有很少条边或弧的图称为稀疏图，反之称为稠密图。稀疏与稠密是相对模糊的概念，没有具体的量化标准。如果图的边或弧具有与其相关的数字，则将这些数字称为权。这些权可以表示从一个顶点到另一个顶点的距离。这种带权的图通常称为网，如图所示。
5.1.2 图的基本术语
4.子图
如果存在两个图G=(V,E)和 G'=(V',E')，并且满足 V' V 和 E' E，则称 G'为G的子图。图（b）、图（c）、图（d）都是图（a）的子图。
5.1.2 图的基本术语
5.顶点的度
对于无向图来说，某一个顶点的度是与该顶点相关联的边的数量。如图所示，顶点A的度为3，表示为 D(A)=3；顶点B的度为2，表示为 D(B)=2。
对于有向图来说，以顶点V i 为弧头的弧的数量称为 V i 的入度，以顶点 V i 为弧尾的弧的数量称为V i 的出度，V i 的度为入度与出度的和。如图所示，顶点C的入度为2，出度为2，度为4；顶点F的入度为1，度为1。
5.1.2 图的基本术语
6.路径
从顶点 V i 到顶点 V j 经过的顶点与弧称为 V i 与 V j 之间的路径。对于有向图来说，其路径也是有向的。路径上弧的数量称为路径的长度。例如，图中的顶点E到顶点F的路径长度为3或4。
如果路径中的顶点不重复出现，则称该路径为简单路径。第一个顶点与最后一个顶点相同的路径称为回路或环。除了第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路或简单环。
图中，B→C→A、E→B→C→F都是简单路径；B→C→A→B为简单回路。
7.连通性
如果顶点 V i 与顶点 V j 之间存在路径，则称 V i 与 V j 是连通的。若图中任意两顶点都连通，则称该图为连通图。在有向图中，任意一对顶点 V i 与 V j ，从 V i 到 V j 和从 V j 到 V i 都存在路径，则称该有向图为强连通图。
5.2 图的存储
5.2.1
邻接矩阵
返回目录
5.2.2
邻接表
5.2.3
十字链表
5.2.4
邻接多重表
5.2 图的存储
图形结构的存储涉及两部分内容：顶点（数据元素）的信息与顶点之间的关系（边或弧的信息）。本节将介绍4种存储图形结构的方法，分别为邻接矩阵、邻接表、十字链表、邻接多重表。
5.2.1 邻接矩阵
邻接矩阵使用两个数组（一个一维数组与一个二维数组）来表示图形结构，一维数组用来存储图中顶点的信息，二维数组用来存储图中弧的信息。
假设图G有n个顶点，则需要创建一个可以存储n个数据元素的一维数组V[n]，并且创建一个可以存储 n×n 个数据元素的二维数组arc[n][n]，也可以将二维数组理解为一个 n×n 的矩阵，其定义如下。
5.2.1 邻接矩阵
上述公式中，1 表示顶点 V i 与顶点 V j 之间存在弧，0 表示不存在弧。
如图所示，创建一个无向图，并使用一维数组存储顶点信息，使用二维数组（矩阵）表示顶点之间的关系。
5.2.1 邻接矩阵
图所示，存放图顶点数据的数组为V[4]={A,B,C,D}，二维数组arc[4][4]对应图中的矩阵，由此可知，arc[2][0]=1表示的是顶点A与顶点C之间存在弧，arc[3][2]=1表示的是顶点C与顶点D之间存在弧。
如果图为有向图，则表示方法与无向图类似，如图所示，同样使用一维数组存储图中顶点的信息，使用二维数组存储顶点之间的关系。
图中，arc[3][0]=1表示从顶点D到顶点A具有弧，而arc[0][3]=0表示从顶点A到顶点D不具有弧。矩阵最后一行与最后一列表示顶点D的出度与入度，可知顶点D的度为3。
5.2.2 邻接表
虽然邻接矩阵可以解决图形结构的逻辑存储问题，但是当图中的弧明显少于顶点时，采用这种存储方式会浪费大量的存储空间。
如图所示，无向图中的大部分顶点之间不存在连接关系，而二维数组本身占用的存储空间不会随着记录信息的减少而减少。因此，使用二维数组记录顶点关系，可能会造成大量存储资源浪费。
5.2.2 邻接表
由线性表的存储方式（第2章）可知，顺序存储（一维数组）由于预先分配内存可能会造成存储资源浪费，而采用链式存储则很好地解决了这一问题。图形结构同样可以采用链式存储的方式记录顶点关系，这种方式称为邻接表。
邻接表使用数组与链表结合的方式表示图形结构。使用一维数组存储顶点信息，使用链表存储顶点之间的关系。在一维数组中，每个数据元素分为两部分，一部分为顶点数据，另一部分为指针。指针用来指向一个链表，该链表用来记录当前顶点的邻接点的信息。因为邻接点的数量不固定，所以链表的长度也是不固定的。
使用邻接表表示无向图，如图所示。
5.2.2 邻接表
图所示，一维数组中的每一个数据元素由data和ver组成。data中存储的是顶点的数据，ver中存储的是指针，该指针指向一个链表，链表中的结点存储的是当前顶点的邻接点的下标。其中，adj表示邻接点在一维数组中的下标，next用来指向下一个邻接点。
图中无向图的顶点B，与其邻接的是顶点A与顶点C，而顶点A与顶点C在一维数组中的下标分别为0、2，因此顶点B对应的ver指向的链表中有两个结点，分别存储的值为0、2。
如果图是有向图，其邻接表的结构也是类似的。由于有向图的弧是有方向的，因此既需要记录以顶点为弧头的弧，也需要记录以顶点为弧尾的弧。使用邻接表的方式表示有向图，如图所示。
5.2.2 邻接表
图所示，邻接表中的adj存储的是某一顶点（该顶点为弧尾，出度）的邻接点在一维数组中的下标。逆邻接表与邻接表相反，adj存储的是作为弧头（入度）的顶点的邻接点所在的下标。由图可知，顶点B为弧尾，邻接点为顶点A与顶点C，顶点A与顶点C在一维数组中的下标分别为0、2。顶点B为弧头，邻接点为顶点C，邻接点在一维数组中的下标为2。
如果图中顶点之间的关系具有权值，则需要在邻接表中添加一个记录权值的数据域，如图所示。
图中，顶点C为弧尾时，其邻接点为顶点A与顶点D，对应的权值为15与13。
5.2.3 十字链表
对于有向图而言，邻接表具有一定的缺陷。如图所示，邻接表只能解决顶点出度的问题，而逆邻接表只能解决顶点入度的问题。因此，可以考虑将邻接表与逆邻接表结合到一起，这种存储方式就是十字链表。
十字链表与邻接表都采用了数组与链表结合的方式来表示图形结构。十字链表相对于邻接表而言，数据的结构更加复杂。其中，一维数组中的数据元素的结构如图所示。
图中，data表示有向图中顶点的数据，in表示指针，指向以该顶点为弧头的邻接点的记录（即链表中的结点），out同样为指针，指向以该顶点为弧尾的邻结点的记录（即链表中的结点）。
5.2.3 十字链表
链表中的结点保存的是邻接点的记录，其结构如图所示。
图中，tail表示弧尾顶点在数组中的下标，head表示弧头顶点在数组中的下标，headlink为指针，指向以顶点为弧头的下一个邻接点的记录，taillink同样为指针，指向以顶点为弧尾的下一个邻接点的记录。
假设存在一个有向图，使用十字链表表示该有向图，如图所示。
5.2.3 十字链表
顶点 A 作为弧尾时，邻接点为顶点 D，而作为弧头时，邻接点为顶点 B 与顶点 C。因此，顶点 A的 in 指向的结点中，tail 值为 1（即邻接点 B 的数组下标），head 值为 0（即顶点 A 的数组下标），headlink 指向下一个邻接点的记录，其 tail 值为 2（即邻接点 C 的数组下标），head 值为 0（即顶点 A的数组下标）。顶点 A 的 out 指向的结点中，tail 值为 0（即顶点 A 的数组下标），head 值为 3（即邻接点 D 的数组下标）。
顶点 B 作为弧尾时，邻接点为顶点 A 与顶点 C，而作为弧头时，邻接点为顶点 C。因此，顶点 B的 in 指向的结点中，tail 值为 2（即邻接点 C 的数组下标），head 值为 1（即顶点 B 的数组下标）。顶点 B 的 out 指向的结点中，tail 值为 1（即顶点 B 的数组下标），head 值为 0（即邻接点 A 的数组下标），taillink 指向下一个邻接点的记录，其 tail 值为 1（即顶点 B 的数组下标），head 值为 2（即邻接点 C 的数组下标）
顶点 C 与顶点 D 的情况可参考上述分析，这里不再详细描述。十字链表的优势就是将邻接表与逆邻接表进行了结合。由图 5.19 可以看出，十字链表的本质是链表交叉，即同一个结点可以存在于多条链表中。
5.2.4 邻接多重表
邻接多重表与邻接表类似，不同的是，邻接多重表重点关注的是顶点之间的关系（边或弧），而非顶点。使用邻接表表示无向图时，如果选择操作图中的某一条边，则需要找到这条边的两个顶点在邻接表中的信息，然后才能进行操作。如果当前需要频繁地处理顶点之间的关系，那么使用邻接表表示图形结构并不是一个很好的选择。
邻接多重表使用数组与链表结合的方式表示图形结构，其不同于邻接表的是，链表中的结点表示的是与顶点相关联的边，而非顶点。邻接多重表中结点的结构如图所示。
图中，iver与jver表示与边相关联的两个顶点在数组中的下标，ilink指向与顶点iver相关联的下一条边的记录（下一个链表结点），jlink指向与顶点jver相关联的下一条边的记录（下一个链表结点）。
5.2.4 邻接多重表
使用邻接多重表表示无向图如图所示。
5.2.4 邻接多重表
图所示，与顶点A相关联的边有3条，分别为(A,B)、(A,C)、(A,D)。如果转换为用数据下标表示，则分别为(0,1)、(0,2)、(0,3)。因此，顶点A的ver指向的结点中，iver为0（顶点A），jver为1（顶点B），且ilink指向下一个结点，该结点的jver为0（顶点A），iver为3（顶点D），jlink指向下一个结点，该结点的iver为0，jver为2。
邻接多重表与邻接表类似，邻接表关注的是顶点的信息，而邻接多重表关注的是顶点之间（的关系边或弧）。
5.3 图的创建
5.3.1
定义图形结构
返回目录
5.3.2
创建图形结构
5.3.3
确定顶点关系
5.3.4
输出顶点关系
5.3.5
整体测试
5.3 图的创建
5.2节主要介绍了如何实现图形结构的存储，即图形结构在计算机中的实现方法。本节将通过具体的代码实现图形结构的创建以及操作。
5.3.1 定义图形结构
下面展示通过邻接矩阵的方式对图形结构进行定义。邻接矩阵采用一维数组与二维数组组合的方式表示图形结构。因此，通过代码实现对图形结构的定义如下所示。
以上述定义通过结构体将一维数组与二维数组组合在一起表示图形结构。如果采用5.2节中介绍的其他方式表示图形结构，只需将结构体中的二维数组替换成其他结构即可。
5.3.2 创建图形结构
下面展示通过邻接矩阵的方式创建无向图，具体代码如下。（变量定义与5.3.1节一致）。
以上代码使用malloc()函数为结构体申请内存空间，对结构体中的一维数组赋值就是向顶点中保存数据。需要特别注意的是，该函数并未确定图中顶点之间的关系。
5.3.3 确定顶点关系
确定图中顶点之间的关系需要对二维数组赋值，假设数字1表示顶点之间存在关系（顶点之间存在弧），数字0表示顶点之间不存在关系。具体代码如下。（变量定义与5.3.1节一致）。
以上代码通过函数scanf()读取终端输入，输入内容为二维数组的坐标。赋值为1，表示存在关系。
5.3.4 输出顶点关系
输出顶点关系即输出二维数组中的数据，通过数据可以判定无向图中顶点之间的关系。具体代码如下所示。（变量定义与5.3.1节一致）。
以上代码遍历整个二维数组，通过某一个结点的值，即可推出顶点之间是否存在弧。例如，matrix[1][2]=1表示一维数组中保存的第2个顶点与第3个顶点之间存在弧。
5.3.5 整体测试
对5.3.1节至5.3.4节的功能代码进行整体测试，示例代码参考教材5.3.5节。
例中，主函数调用子函数完成图的创建，然后执行确定顶点关系的函数，最后输出图中顶点的关系。程序运行结果如下所示。
5.3.5 整体测试
运行程序，按照格式输入坐标值，当输入格式错误的内容时，程序自动结束读取。根据输出内容可知，具有关系的边有(V 0 ,V 1 )、(V 0 ,V 2 )、(V 0 ,V 3 )、(V 1 ,V 2 )、(V 1 ,V 3 )、(V 2 ,V 3 )、(V 2 ,V 4 )、(V 3 ,V 4 )。因此，根据输入的顶点数据与关系，可以确定程序创建的无向图的逻辑结构，如图所示。
5.4 图的遍历
5.4.1
深度优先搜索
返回目录
5.4.2
广度优先搜索
5.4.3
最短路径
5.4 图的遍历
图的遍历与树的遍历类似，即从图中的某个顶点开始，经过一定的路线访问图中所有可以访问的顶点，并且这些顶点只能被访问一次，这个过程称为图的遍历。图的遍历方式通常可以分为深度优先搜索与广度优先搜索两种。
5.4.1 深度优先搜索
1.深度优先搜索的概念
深度优先搜索（Depth First Search，DFS）类似于树的先序遍历。从图中的某个顶点开始访问，访问完成后，需要按照深度优先的原则，继续访问其邻接点，并以此类推。若某顶点的邻接点全部访问完毕，则回溯到它的上一个顶点，然后从此顶点开始，按照深度优先的原则继续搜索，直到可以被访问的顶点都访问完毕为止。
如图所示，假设从无向图中的顶点A开始访问，定义一个访问规则（参考树的先序遍历）：访问顶点的下一个邻接点时，首先访问顶点右边（顶点角度）的邻接点。
5.4.1 深度优先搜索
图 中，按照先访问顶点右边的邻接点的规则，从访问顶点 A开始，顶点 A 的邻接点有 B、F，应该先访问顶点 B。顶点 B 的邻接点有 C、G、H，应该先访问顶点 C。顶点 C 的邻接点有 B、G、D，应该先访问顶点 D。顶点 D 的邻接点有 C、G、H、I、E，应该先访问顶点 E。顶点 E 的邻接点有 D、I、F，应该先访问顶点 F。顶点 F的邻接点有 A、H、I、E，因为顶点 A 已经被访问，所以应该先访问顶点 H。顶点 H 的邻接点为 B、D、I、F，其中顶点 B、D、F 都已经被访问，因此只能访问顶点 I。经过上述遍历后，可以发现顶点G 并没有被访问，因此在访问到 I 时，遍历并没有结束，而需要按照原来访问的路径返回。当返回到顶点 D 时，邻接点 C、H、I 都已经被访问，只剩下顶点 G 未被访问。顶点 G 访问完成后，继续返回，直到返回到顶点 A 停止。
综上所述，图中顶点的访问顺序为 A-B-C-D-E-F-H-I-G。由上述遍历过程可以看出，该遍历方式与树的遍历一样，需要借助递归的方式实现。
5.4.1 深度优先搜索
2.深度优先搜索的实现
下面介绍基于邻接矩阵存储方式的深度优先搜索，其核心操作为采用递归调用的思想寻找顶点的邻接点。如果某个顶点的所有邻接点都已经被访问，则返回到上一个顶点，继续访问。具体代码如下所示。（变量定义与5.3.1节一致）。
5.4.1 深度优先搜索
5.4.1 深度优先搜索
以上代码中采用递归调用的方式，依次寻找顶点的邻接点。其设计思想如图所示。
graph_DFS()函数的功能为输出顶点数据，并调用graph_adj()函数寻找顶点的邻接点。
5.4.1 深度优先搜索
3.整体测试
整体测试需要结合邻接矩阵存储图形结构的代码（例5-1），示例代码参考教材5.4.1节。
例中，主函数调用子函数创建图，并需要终端输入顶点关系，通过深度优先搜索函数输出访问结果。程序运行结果如下所示。
5.4.1 深度优先搜索
5.4.1 深度优先搜索
无向图中的顶点共有 9 个，根据输入的顶点数据与关系，可以确定程序创建的无向图的逻辑结构，如图 所示。
例输出的搜索结果为 0–1–2–3–4–5–7–8–6，结合图 5.25 可知，运算结果与推理一致，深度搜索成功。
5.4.2 广告优先搜索
1.广度优先搜索的概念
广度优先搜索（Breadth First Search，BFS）类似于树的层序遍历,。例如，5.4.1节中的图5.23中，从顶点A开始访问（顶点A作为层序遍历的第一层）；顶点A的邻接点为顶点B、顶点F，因此将顶点B、顶点F作为层序遍历的第二层，其邻接点为C、G、H、E；同样将顶点C、顶点G、顶点H、顶点E作为层序遍历的第三层，其邻接点为顶点D、顶点I（顶点D、I作为遍历的第四层）。将图按照层序遍历的思想重新设计，如图所示。
5.4.2 广告优先搜索
无论是树还是图，层序遍历都需要借助于队列来完成（队列实现数据先进先出）。图中，第一层为顶点A，第二层为顶点B、顶点F，第三层为顶点C、顶点G、顶点H、顶点E，第四层为顶点D、顶点I。因此，通过队列实现遍历的原理如图所示。
5.4.2 广告优先搜索
图所示原理为：将无向图中每一层的顶点按照顺序入队、出队，并访问数据。广度优先搜索即每次必须先找到顶点的所有邻接点，访问完成后，再寻找这些邻接点的下一层邻接点。
2. 广度优先搜索的实现
下面介绍基于邻接矩阵存储方式的广度优先搜索，具体代码如下所示。（队列函数实现可参考3.6节链式队列的代码实现）。
5.4.2 广告优先搜索
以上代码实现的原理如图所示。
5.4.2 广告优先搜索
3.整体测试
整体测试需要结合邻接矩阵存储图形结构的代码（例5-1）以及3.6节链式队列的操作代码。首先将链式队列的操作代码直接封装为头文件，然后使用操作图形结构的代码调用该头文件，即可完成测试。
链式队列的操作代码，链式队列的操作代码参考教材5.4.2节。
广度优先搜索的代码参考教材5.4.2节。
例中，主函数调用子函数完成图的创建，然后执行确定顶点关系的函数，最后输出图中顶点的关系。通过广度优先搜索函数实现遍历，程序运行结果如下所示。
5.4.2 广告优先搜索
5.4.2 广告优先搜索
无向图中的顶点共有 9 个，根据输入的顶点数据与关系，可以确定程序创建的无向图的逻辑结构与 5.4.1 节中的图 5.25 一致。其中，顶点 V 0 的邻接点为顶点 V 1 、顶点 V 5 ，顶点 V 1 、顶点 V 5 的邻接点为顶点 V 2 、顶点 V 4 、顶点 V 6 、顶点 V 7 ，顶点 V 2 、顶点 V 4 、顶点 V 6 、顶点 V 7 的邻接点为顶点 V 3 、顶点 V 8 。按照层序遍历的思想重新设计，如图所示。
结合图和广度优先搜索的规则，可以推理出顶点被访问的 顺 序 为 V 0 -V 1 -V 5 -V 2 -V 6 -V 7 -V 4 -V 3 -V 8 。 程 序 输 出 的 结 果 为0–1–5–2–6–7–4–3–8。程序输出结果与推理结果一致，表示广度优先搜索成功。
5.4.3 最短路径
1．最短路径的概念
在非网图（边或弧不具有权值）中，最短路径指的是两顶点之间经过边数最少的路径。而在网图（边或弧具有权值）中，最短路径指的是两顶点之间经过的边的权值之和最小的路径，路径上的第一个顶点称为源点，最后一个顶点称为终点。
2．迪杰斯特拉算法
迪杰斯特拉（Dijkstra）算法是按照路径长度递增次序产生最短路径的算法。迪杰斯特拉算法主要讨论的是从一个顶点到其余各个顶点的最短路径（也称为单源最短路径）。算法的基本思想为：将图中的顶点分为两个集合 S 和 T，集合 S 中存放已确定最短路径的顶点，集合 T 中存放未确定最短路径的顶点，按照最短路径长度递增的次序将集合 T 中的顶点逐个加入集合 S，直到从源点出发可以到达的所有顶点都在集合 S 中。
5.4.3 最短路径
如图所示，创建一个具有权值的图。接下来通过该图形结构对迪杰斯特拉算法的原理进行分析。
（1）在集合 S 中加入顶点 A，即 S=(A)，此时最短路径为 A→A（权值为 0）。集合 T 中的顶点有 B、C、D、E、F，即 T=(B,C,D,E,F)。顶点 A 的邻接点为顶点 B、顶点 C，A→B 的权值为 6，A→C 的权值为 3，其中 A→C 的权值较小。
5.4.3 最短路径
（2）在集合 S 中加入顶点 C，即 S=(A,C)。集合 T 中的顶点有 B、D、E、F，即 T=(B,D,E,F)。顶
点 C 的邻接点有顶点 A、顶点 B、顶点 D、顶点 E，A→C→B 的权值为 5，A→C→D 的权值为 6，A→C→E的权值为 7，其中 A→C→B 的权值最小。
（3）在集合 S 中加入顶点 B，即 S=(A,C,B)。集合 T 中的顶点有 D、E、F，即 T=(D,E,F)。顶点 B的邻接点有顶点 A、顶点 C、顶点 D，A→C→B→D 的权值为 10，该权值大于上一步中 A→C→D 的权值。因此，这里需要变更为权值较小的路径，即 A→C→D。
（4）在集合 S 中加入顶点 D，即 S=(A,C,B,D)。集合 T 中的顶点有 E、F，即 T=(E,F)。顶点 D 的邻接点有顶点 B、顶点 C、顶点 E、顶点 F，A→C→D→E 的权值为 8，A→C→D→F 的权值为 9。路径 A→C→D→E 的权值大于上一步中 A→C→E 的权值。因此，这里需要变更为权值较小的路径，即A→C→E。
（5）在集合 S 中加入顶点 E，即 S=(A,C,B,D,E)。集合 T 中的顶点有 F，即 T=(F)。顶点 E 的邻接点为顶点 C、顶点 D、顶点 F，A→C→E→F 的权值为 12，该权值大于上一步中 A→C→D→F 的权值。因此，这里需要变更为权值较小的路径，即 A→C→D→F。
5.4.3 最短路径
（5）在集合 S 中加入顶点 E，即 S=(A,C,B,D,E)。集合 T 中的顶点有 F，即 T=(F)。顶点 E 的邻接点为顶点 C、顶点 D、顶点 F，A→C→E→F 的权值为 12，该权值大于上一步中 A→C→D→F 的权值。因此，这里需要变更为权值较小的路径，即 A→C→D→F。
（6）在集合 S 中加入顶点 F，即 S=(A,C,B,D,E,F)。集合 T 为空，查找完毕。顶点 A 到顶点 A 的最短路径为 A→A（0），顶点 A 到顶点 B 的最短路径为 A→C→B（5），顶点 A 到顶点 C 的最短路径为
A→C（3），顶点 A 到顶点 D 的最短路径为 A→C→D（6），顶点 A 到顶点 E 的最短路径为 A→C→E（7），顶点 A 到顶点 F 的最短路径为 A→C→D→F（9）。
由上述分析可知，通过迪杰斯特拉算法计算两顶点之间的最短路径并非一步完成，而是在已经得出最短路径的基础上，求到更远顶点的最短路径。上述操作中，按最短路径长度的递增次序依次把集合 T 中的顶点加入集合 S。在加入的过程中，总保持从源点 A 到集合 S 中各顶点的最短路径长度不大于从源点 A 到集合 T 中任何顶点的最短路径长度。
5.4.3 最短路径
3．弗洛伊德算法
如果每次以图中的一个顶点（不重复）作为源点，重复执行迪杰斯特拉算法，便可求出每对顶点之间的最短路径，但显然这种处理方式是比较复杂的。接下来将介绍一种适合计算任意两顶点之间的最短路径的算法——弗洛伊德（Floyd）算法。
弗洛伊德算法的核心为：对于任意一对顶点 V i 和 V j ，判断是否存在一个顶点 V x ，使得从顶点 V i到顶点 V x 再到顶点 V j 比己知的路径更短，如果存在，则更新该路径。
如图所示，创建一个有向图。接下来通过该图形结构对弗洛伊德算法的原理进行分析。
5.4.3 最短路径
使用矩阵（二维数组E）表示图中有向图的顶点关系，如图所示。
顶点 A 到顶点 B 的路径为 2，则设 E[0][1]=2。顶点 C 到顶点 B 不存在弧，则设 E[2][1] =∞。顶底 D 到顶点 C 的路径为 12，则设 E[3][2]=12。
根据弗洛伊德算法的核心思想，如果需要将任意两个顶点（例如，从顶点 A 到顶点 C）之间的路径变短，则需要引入第三个顶点（假设为顶点 K），并通过这个顶点中转（即 A→K→C）。而有些时候需要经过两个或更多的顶点中转才能使路径变短，如 A→K→L→M→C。
5.4.3 最短路径
图中，从顶点 D 到顶点 C 的路径权值为 12，如果通过顶点 A 中转（D A C），路径将缩短为权值 11（E[3][0]+E[0][2]=5+6=11）。其中，顶点 A 到顶点 C 也可以通过顶点 B 中转，使得顶点A 到顶点 C 的路径缩短为权值 5（E[0][1]+E[1][2]=2+3=5）。因此，同时经过顶点 A 和顶点 B 中转，从顶点 D 到顶点 C 的路径会进一步缩短为权值 10。
图中，如果任意两个顶点之间不允许通过其他顶点中转，那么顶点之间的最短路径就是初始路径，权值如图 5.32 所示。如果只允许通过顶点 A 进行中转，那么需要对任意两点之间的最短路径进行更新，如图所示。
5.4.3 最短路径
图中，顶点 C 到顶点 B 的路径更新后权值为 9，即 E[2][1]=9，顶点 D 到顶点 B 的路径更新后权值为 7，即 E[3][1]=7，顶点 D 到顶点 C 的路径更新后权值为 11，即 E[3][2]=11。
如果允许通过顶点 A 与顶点 B 进行中转，那么需要对任意两点之间的最短路径再次进行更新，如图所示。
5.4.3 最短路径
图中，顶点 A 到顶点 C 的路径更新后权值为 5，即 E[0][2]=5，顶点 D 到顶点 C 的路径更新后权值为 10，即 E[3][2]=10。
如果允许通过顶点 A、B、C 进行中转，那么需要对两点之间的最短路径再次进行更新，如图所示。
图中，顶点 B 到顶点 A 的路径更新后权值为 10，即 E[1][0]=10，顶点 B 到顶点 D 的路径更新后权值为 4，即 E[1][3]=4。
5.4.3 最短路径
如果允许通过所有顶点进行中转，那么需要对两点之间的最短路径再次进行更新，如图所示。
如图中，顶点B到顶点A的路径更新为9，即E[1][0]=9，顶点C到顶点A的路径更新为6，即E[2][0]=6，顶点C到顶点B的路径更新为8，即E[2][1]=8。
5.4.3 最短路径
将图与图 5.32 进行对比可以看出，通过逐个添加顶点中转（弗洛伊德算法的核心），图中部分顶点之间的路径缩短。顶点 A 到 C 的路径更新后权值为 5（A→B→C），顶点 B 到 A 的路径更新后权值为 9（B→C→D→A），顶点 B 到顶点 D 的路径更新后权值为 4（B→C→D），顶点 C 到 A 的路径更新后权值为 6（C→D→A），顶点 C 到顶点 B 的路径更新后权值为 8（C→D→A→B），顶点 D 到顶点 B 的路径更新后权值为 7（D→A→B），顶点 D 到顶点 C 的路径更新后权值为 10（D→A→B→C）。图中各顶点之间的路径就是最短路径。
本章小结
本章主要介绍了一种非线性数据结构——图，包括图的基本概念、图的存储、图的创建、图的遍历四个部分。其中，需要重点关注的是图形结构的存储方法，即邻接矩阵、邻接表、十字链表、邻接多重表。本章在最后展示了图形结构（基于邻接矩阵表示）的操作代码，包括图的创建、图的遍历。图的遍历主要有深度优先搜索与广度优先搜索。望读者理解图形结构的存储方法以及图的遍历，熟练编写操作代码。

展开更多......

收起↑