数据结构概论 第7章 图 董黎刚 浙江工商大学信电学院 2019年4月8日.

Presentation on theme: "数据结构概论 第7章 图 董黎刚 浙江工商大学信电学院 2019年4月8日."— Presentation transcript:

1 数据结构概论 第7章 图 董黎刚 浙江工商大学信电学院 2019年4月8日

2 1. 图的定义和基本术语

3 7.1.1 背景 图状结构是四大逻辑结构之一，是一个非线性结构。
我们这里涉及的是图论（Graph Theory）的基本内容。图论是“离散数学”中的重要内容之一。 图论的应用非常广泛，有很多经典的问题。 7.1 图的定义和基本术语

4 7.1.1 背景 哥尼斯堡七桥问题 能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地？
1736 年 29 岁的欧拉解决了该问题，这也意味新的数学分支——图论的诞生 7.1 图的定义和基本术语

5 7.1.1 背景 四色问题（世界三大数学难题之一） 证明不论地图多么复杂，最多使用四种颜色就能保证相邻地区使用不同颜色。
1976年，美国数学家阿佩尔与哈肯用计算机化了1200个小时，作了100亿次判断，完成证明 7.1 图的定义和基本术语

6 7.1.1 背景 本课程主要不是要解决图论中的问题——这是离散数学的任务。 本课程的任务是理解已有的解决方案，把它转化成算法和程序。
7.1 图的定义和基本术语

7 7.1.2 图的定义 图就是数据元素间为多对多关系的数据结构。怎么理解？
线性表是一对一关系：每一对结点中，前者只有一个直接后继，后者只有一个直接前驱 树是一对多关系：每一对结点中，前者可能有多个直接后继（孩子），而后者只能有一个直接前驱（双亲） 图中每一对顶点中，它们都同时可能有多个邻接点 7.1 图的定义和基本术语

8 7.1.2 图的定义 图的形式化定义 与线性结构、树型结构有什么不同？ ADT Graph {
数据元素：V={vi| vi∈D0, i=1,2,…,n, n≥0, D0为某一数据对象} 结构关系：R＝｛<vi,vi+1> | vi, vi+1∈D0, i=1,2, …,n-1｝ 基本操作： 常规操作：创建/初始化，销毁，清空，插入，删除，查找/定位 ，遍历 新增操作：找到本顶点的第一个邻接点，找到本顶点的下一个邻接点，插入/删除弧 } 7.1 图的定义和基本术语

9 7.1.3 图的基本术语 图G1中有4个顶点（vertex）（一个顶点对应一个数据元素）
<x，y>表示从顶点x到顶点y的一条弧（arc），并称x为弧尾（tail）或起始点，称y为弧头（head）或终端点。 G1是有向图（包含弧的图） 7.1 图的定义和基本术语

10 7.1.3 图的基本术语 G2是无向图（没有弧的图） G2中有边(1,4), (1,2), (2,3), (2,5), (3,5), (3,4) 无序对（x，y）表示x和y之间的一条边（edge）。所谓无序对，就是指（x，y）等同于（y，x） 1条边等于2条弧，即(1,4)等于<1,4>加上<4,1> 7.1 图的定义和基本术语

11 7.1.4 本章的假设 我们只讨论简单图（Simple Graph），即没有自环也没有多重边的图。 自环：两个顶点为同一顶点的边。
多重边：两个点之间不止一条边。 7.1 图的定义和术语

12 2. 图的相关术语

13 7.2.1 完全图 有向完全图：有n（n-1）条弧的有向图（这意味着图中每个顶点和其余n-1个顶点都有弧相连）。
7.2 图的相关术语

14 7.2.2 子图 设有两个图G=（V，R）和图G / =（V/，R/）,若V/V且R/  R，则称图G/为G的子图。 有向图的子图
还有子图吗？ 7.2 图的相关术语

15 7.2.2 子图 无向图的子图 7.2 图的相关术语

16 7.2.3 邻接点 对于无向图G=（V，R），如果边（v，v/）∈R，则称顶点v，v/互为邻接点，即v，v/ 相邻接。边（v，v/）与顶点v和v/ 相关联。 比如，顶点3的邻接点是顶点2,4,5 对于有向图G=（V，R）而言，若弧<v，v/>∈R，则称顶点v邻接到顶点v/，顶点v/ 邻接自顶点v。 7.2 图的相关术语

17 7.2.4 顶点的位置序号 同一个顶点的多个邻接点之间有无前后次序？
我们需要将图中的顶点按某种序列排列起来。顶点在这个人为的随意排列中的位置序号称为顶点在图中的位置。 比如，右下图中各顶点的顺序是顶点1,2,3,4 注意：实际的图中，圈内的数值可能是指顶点的位置序号，也可能是数据元素的值，根据上下文确定 7.2 图的相关术语

18 7.2.5 度 无向图中，顶点v 的度（Degree）是指和v相关联的边的数目，记作TD(v)。 比如，顶点3的度是3。
有向图中，分入度和出度两部分，满足： TD(v) = ID(v) + OD(v) 。 比如，顶点3的入度是1，出度为1， 度为2 Input Output Total 7.2 图的相关术语

19 7.2.5 度 一般地，若图G中有n个顶点，e条边或弧，则图中边与顶点的度的关系如下： 原因是1条边/弧与2个顶点相关联
7.2 图的相关术语

20 7.2.6 权和网 在实际应用中，有时图的边或弧上往往与具有一定意义的数（比如距离或耗费等信息）有关，该数称为权。 网（赋权图）：带权的图。
7.2 图的相关术语

21 7.2.7 图的种类 有向图（Directed Graph, DG） 有向网（Directed Network, DN）
无向图（Undirected Graph, UDG） 无向网（Undirected Network, UDN） 7.2 图的相关术语

22 7.2.8 路径和回路 路径：顶点v到v/的顶点序列。
路径长度：路径上经过的弧或边的条数（对于无权图），或者路径上经过的弧或边的权重之和（对于赋权图）。 比如，顶点1到5的路径有： (V1, V4, V3, V5) ， (V1, V2, V5)， (V1, V2, V3, V5) ，它们的路径长度分别是3、2和3。 7.2 图的相关术语

23 7.2.8 路径和回路 回路（环）：首尾顶点相同的路径。 简单路径：顶点不重复的路径。 简单回路：除首尾顶点外，中间的顶点不重复的回路。
比如，(V1, V3, V4 , V1)是回路和简单回路, (V1, V3, V4 , V1, V2)不是简单路径。 7.2 图的相关术语

24 7.2.9 连通和强连通 图中的任意两个顶点之间都是连通的，则称该图为连通图（对于无向图）或强连通图（对于有向图）。
无向图中的极大连通子图（“极大”是指包括尽可能多的顶点和边/弧的子图）称为该图的连通分量。 左图的三个连通分量 7.2 图的相关术语

25 7.2.9 连通和强连通 有向图中的极大连通子图称为该有向图的强连通分量。 左图的二个强连通分量 7.2 图的相关术语

26 3. 图的存储结构（1）

27 7.3.1 图的存储结构分类 邻接矩阵（Adjacency Matrix）（又称数组表示法）是一种顺序存储结构。
邻接表（Adjacency List）是一种顺序存储和链式存储结合的结构。 十字链表(Orthogonal List)是有向图的另一种链式存储结构。 邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构。 7.3 图的存储结构（1）

28 7.3.2 无权图的邻接矩阵定义 若G是一具有n个顶点的无权图，G的邻接矩阵是具有如下性质的n×n矩阵A： 7.3 图的存储结构（1）

29 7.3.3 赋权图的邻接矩阵定义 若图G是一个有n个顶点的网(赋权图)，则它的邻接矩阵是具有如下性质的n×n矩阵A ：
7.3 图的存储结构（1）

30 7.3.4 对邻接矩阵的评价 一般需要n2个存储空间。但是，对于无向图而言，它的邻接矩阵是对称矩阵，所以可采用压缩存储法，其存储空间只需n(n-1)/2。 稀疏图不适于用邻接矩阵来存储，因为这样会造成存储空间的浪费。 7.3 图的存储结构（1）

31 7.3.4 对邻接矩阵的评价 便于判断图中两个顶点之间是否有边相连，便于求得各个顶点的度。
G1中4个顶点的出度分别是2,0,1,1；4个顶点的入度分别是1,1,1,1。 G2中的5个顶点的度分别是2,3,3,2,2 7.2 图的存储结构

32 7.3.5 邻接矩阵的C语言定义 存储图中顶点之间关联关系 存储顶点信息 typedef struct ArcNode {
AdjType adj;/*1或0（无权图），或者权值（带权图）*/ OtherInfo info; /*其他信息*/ } ArcNode; typedef struct VertexData vexs[MAX_VERTEX_NUM]; ArcNode arcs [MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum, arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类*/ } AdjMatrix; 存储图中顶点之间关联关系 存储顶点信息 7.3 图的存储结构（1）

33 4. 图的存储结构（2）

34 7.4.1 邻接表的定义 邻接表表示由1个顶点表（这是顺序表）与若干个边/弧结点链表两部分构成。 7.4 图的存储结构（2）

35 7.4.1 邻接表的定义——C语言 typedef struct ArcNode { …… }ArcNode;
typedef struct VertexNode }VertexNode;  typedef struct VertexNode vertex[MAX_VERTEX_NUM]; //表头结点表 int vexnum,arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类标志*/ }AdjList; 7.4 图的存储结构（2）

36 7.4.2 对邻接表的评价 存储空间相对较少：n个顶点，e条边的无向图，需要n个顶点结点和2e/e个边/弧结点。 比如下图中，n=5，e=6
顶点顺序要一致 边/弧结点链表中的各结点要遵循相同的顺序，这是为了使结点访问时能有顺序。 7.4 图的存储结构（2）

37 7.4.3 对邻接表的评价 比较容易求得无向图的度和有向图的出度。 比如，下图中结点A有2个边/弧结点，因此，出度是2
要想求得有向图中顶点i的入度，则必须遍历所有边/弧结点，查找邻接点域的值为i的结点并计数求和。 7.4 图的存储结构（2）

38 7.4.4 逆邻接表 目的：逆邻接表法用来解决求顶点的入度不方便的问题。但是，逆邻接表计算出度不方便
思想：逆邻接表中的边/弧链表存放的是入弧顶点下标，而邻接表中的边/弧链表存放的是出弧顶点下标。 有没有计算入度和出度都方便的方法？十字链表 7.4 图的存储结构（2）

39 7.4.5 十字链表（针对有向图） 思想：邻接表和逆邻接表结合起来。每个顶点结点同时有指向入弧和出弧顶点的指针；每个弧结点不仅包含弧头和弧尾，也包含指向弧头或弧尾相同的弧的指针 。 7.4 图的存储结构（2）

40 7.4.5 十字链表（针对有向图） 思想：邻接表和逆邻接表结合起来。每个顶点结点同时有指向入弧和出弧顶点的指针；每个弧结点不仅包含弧头和弧尾，也包含指向弧头或弧尾相同的弧的指针 。 7.4 图的存储结构（2）

41 7.4.6 邻接多重表（针对无向图） 思想：每个边结点不仅包含边的两个顶点，也把有共同顶点的边结点链接在一起。 7.4 图的存储结构（2）

42 5. 图的遍历

43 7.5.1 背景 图遍历：按照一定规律访问图中每个顶点仅一次。
就象树遍历是树的最重要操作，图遍历是图的最重要操作，因为图中多数算法都是基于图遍历设计的。 图中两种遍历 深度优先遍历/搜索。类似于树的先根遍历。 广度优先遍历/搜索。类似于树的按层次遍历。 7.5 图的遍历

44 7.5.1 背景 图遍历时，需要为每个顶点设一个访问标志（用数组visited[n]），用以标示图中每个顶点是否被访问过。
注意：线性表和树中都不需要访问标志，为什么？ 图是多对多关系（任何顶点同时是其他多个顶点的邻接点），因此一个顶点可能作为前一个顶点的邻接点已经被访问过 7.5 图的遍历

45 左图中黒箭头代表访问方向，红箭头代表回溯方向，箭头旁边的数字代表搜索顺序，A为起始顶点。访问序列为：A、B、C、F、D、G、E、H、I。
7.5.2 深度优先遍历算法 左图中黒箭头代表访问方向，红箭头代表回溯方向，箭头旁边的数字代表搜索顺序，A为起始顶点。访问序列为：A、B、C、F、D、G、E、H、I。 4 7.5 图的遍历

46 其中箭头代表搜索方向，箭头旁边的数字代表搜索顺序，A为起始顶点。访问序列为：A、B、D、E、C、G、F、H、I。
7.5.3 广度优先遍历算法 其中箭头代表搜索方向，箭头旁边的数字代表搜索顺序，A为起始顶点。访问序列为：A、B、D、E、C、G、F、H、I。 7.4 图的遍历

47 7.5.4 算法实现 在图遍历时，对于连通图，无论是广度还是深度优先搜索，仅需要调用一次搜索过程，即从任一个顶点出发，便可以遍历图中的各个顶点。 对于非连通图，调用搜索过程的次数就是该图连通分量的个数。 深度优先遍历算法是以递归（或堆栈）技术为基础，而广度优先遍历算法是以队列技术为基础。 7.5 图的遍历

48 7.5.4 算法实现——深度优先遍历(递归) 基于邻接矩阵的连通子图内的深度优先遍历 邻接矩阵 其他还有基于邻接表的深度优先遍历算法
void DepthFirstSearch(AdjMatrix g,int v0) { visit(v0); visited[v0]=True; for(vj=0; vj<n; vj++) if(!visited[vj] &&g.arcs[v0][vj].adj==1) DepthFirstSearch(g,vj); } 其他还有基于邻接表的深度优先遍历算法 邻接矩阵 7.5 图的遍历

49 7.5.4 算法实现——深度优先遍历(递归) 深度优先遍历（基于邻接矩阵）的动画 程序缺少注释。 7.5 图的遍历

50 7.5.4 算法实现——深度优先遍历(递归) 深度优先遍历（基于邻接表）的动画 程序缺少注释。 7.5 图的遍历

51 7.5.4 算法实现——深度优先遍历(堆栈) 7.5 图的遍历

52 7.5.4 算法实现——深度优先遍历(堆栈) 为什么入栈： 该顶点还未被访问 为什么出栈： 该顶点所有邻接点都已经被访问 7.5 图的遍历

53 7.5.4 算法实现——广度优先遍历(队列) 广度优先遍历（基于邻接表）的动画 7.4 图的遍历 图中的出队、入队方向没有标出~
对应于深度优先遍历，此处的广度优先遍历缺少相应的算法实现——程序。 7.4 图的遍历

54 7.5.4 算法实现——广度优先遍历(队列) 7.4 图的遍历

55 6. 图的应用 ——最小生成树

56 7.6.1 背景 问题：若要在n个城市之间建设通信网络，如何以最低的经济代价建设这个通讯网络？ 7.6 图的应用——最小生成树

57 7.6.2 相关术语 n个顶点的（无向）连通图的边数至少是n-1。 但是有n-1条并不一定连通 对于强连通图，边数至少是n
如果图T为无向图G的生成子图（即含有G的所有顶点的子图）且T为树，T称为G的生成树。 树刚好含有n-1条边，且是连通的。 7.6 图的应用——最小生成树

58 7.6.2 相关术语 在一个连通网的所有生成树中，各边的权重之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树。 注意：最小生成树不是唯一的，但是它们都有一致的权重和最小值 7.6 图的应用——最小生成树

59 7.6.3 最小生成树构造算法 普里姆（PRIM）算法思想： 假设N=(V,E)是连通网，TE为最小生成树中边的集合。
（1）初始U={u0}(u0∈V),TE=φ； （2）在所有u∈U, v∈V-U的边中选一条权值最小的边（u0，v0）并入集合TE，同时将v0并入U； （3）重复（2），直到U=V为止。 克鲁斯卡尔（KRUSKAL）算法思想 在保证不产生环的情况下，按权值由小到大的顺序选择边 7.6 图的应用——最小生成树

60 7.6.4 普里姆算法实例 最小生成树构造算法——普里姆（PRIM）算法 U 7.6 图的应用——最小生成树

61 7.6.4 普里姆算法实例 最小生成树构造算法——普里姆（PRIM）算法 U U 1 7.6 图的应用——最小生成树

62 7.6.4 普里姆算法实例 最小生成树构造算法——普里姆（PRIM）算法 U U 1 4 7.6 图的应用——最小生成树

63 7.6.4 普里姆算法实例 最小生成树构造算法——普里姆（PRIM）算法 U U 1 2 4 7.6 图的应用——最小生成树

64 7.6.4 普里姆算法实例 最小生成树构造算法——普里姆（PRIM）算法 U U 1 5 2 4 7.6 图的应用——最小生成树

65 7.6.4 普里姆算法实例 最小生成树构造算法——普里姆（PRIM）算法 U 1 5 3 2 4 7.6 图的应用——最小生成树

66 7.6.5 克鲁斯卡尔算法实例 最小生成树构造算法——克鲁斯卡尔（KRUSKAL）算法 5 7.6 图的应用——最小生成树

67 7.6.5 克鲁斯卡尔算法实例 最小生成树构造算法——克鲁斯卡尔（KRUSKAL）算法 5 6 7.6 图的应用——最小生成树

68 7.6.5 克鲁斯卡尔算法实例 最小生成树构造算法——克鲁斯卡尔（KRUSKAL）算法 5 11 6 7.6 图的应用——最小生成树

69 7.6.5 克鲁斯卡尔算法实例 最小生成树构造算法——克鲁斯卡尔（KRUSKAL）算法 16 5 11 6 7.6 图的应用——最小生成树

70 7.6.5 克鲁斯卡尔算法实例 最小生成树构造算法——克鲁斯卡尔（KRUSKAL）算法 16 5 11 6 18
7.6 图的应用——最小生成树

71 7.6.5 克鲁斯卡尔算法实例 克鲁斯卡尔算法的动画 7.6 图的应用——最小生成树

72 7. 图的应用 ——拓扑排序

73 7.7.1 背景 问题：按照下面课程信息进行排课。 课程编号 课程名称 先修课程 C1 高等数学 无 C2 程序设计基础 C3 离散数学
数据结构 C2,C3 C5 算法语言 C6 编译技术 C4,C5 C7 操作系统 C4,C9 C8 普通物理 C9 计算机原理 7.7 图的应用——拓扑排序

74 7.7.1 背景 用顶点表示课程，弧表示先决条件，则可用一个有向无环图表示课程的先后关系。
可行的课程顺序？比如，C1,C2,C3,C4,C5,C8,C9,C7,C6，或者C1,C2,C3,C8,C4,C5,C9,C7,C6。 称为拓扑序列。 7.7 图的应用——拓扑排序

75 7.7.2 定义 用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（Activity On Vertex Network），简称为AOV-网。 在有向图G=（V，E）中，V中顶点的线性序列（v1,,v2,,v3,…，vn）称为拓扑序列。此序列必须满足：对序列中任意两个顶点vi、vj，假如在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。 产生拓扑序列的过程叫拓扑排序（Topological Sort）。 7.7 图的应用——拓扑排序

76 7.7.3 AOV-网的特性 若vi为vj的先行活动，vj为vk的先行活动，则vi必为vk的先行活动，即先行关系具有可传递性。
7.7 图的应用——拓扑排序

77 7.7.4 拓扑排序算法实例 拓扑排序的动画 7.7 图的应用——拓扑排序

78 7.7.4 拓扑排序算法实例 C5 C2 C6 C4 C3 C7 C1 C8 C9 没有前驱的顶点有C1和C2
7.7 图的应用——拓扑排序

79 7.7.4 拓扑排序算法实例 C5 C2 C6 C4 C3 C7 C8 C9 没有前驱的顶点有C2和C8
7.7 图的应用——拓扑排序

80 7.7.4 拓扑排序算法实例 C5 C6 C4 C3 C7 C8 C9 没有前驱的顶点有C3、C5和C8
7.7 图的应用——拓扑排序

81 7.7.4 拓扑排序算法实例 C5 C6 C4 C7 C8 C9 没有前驱的顶点有C4、C5和C8 任选C5，将此顶点和以它为起点的弧删除
7.7 图的应用——拓扑排序

82 7.7.4 拓扑排序算法实例 C6 C4 C7 C8 C9 没有前驱的顶点有C4和C8 任选C8 ，将此顶点和以它为起点的弧删除
7.7 图的应用——拓扑排序

83 7.7.4 拓扑排序算法实例 C6 C4 C7 C9 没有前驱的顶点有C4和C9 任选C9 ，将此顶点和以它为起点的弧删除
7.7 图的应用——拓扑排序

84 7.7.4 拓扑排序算法实例 C6 C4 C7 没有前驱的顶点有C4 选C4 ，将此顶点和以它为起点的弧删除
得到拓扑序列：C1C2C3C5C8C9C4 7.7 图的应用——拓扑排序

85 7.7.4 拓扑排序算法实例 C6 C7 没有前驱的顶点有C6和C7
先后选C6和C7，最后得到的拓扑序列是：C1C2C3C5C8C9C4C6C7 7.7 图的应用——拓扑排序

86 8. 图的应用 ——关键路径

87 7.8.1 背景 问题：一个工程中由若干活动组成（见下面甘特图，用MS Project画），至少需要多长时间能完成整个工程？
7.8 图的应用——关键路径

88 7.8.2 定义 用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。我们把用这种方法构造的有向无环图叫做边表示活动的网（Activity On Edge Network）,简称AOE-网。 存在唯一的、入度为零的顶点，叫源点。 存在唯一的、出度为零的顶点，叫汇点。 7.8 图的应用——关键路径

89 7.8.2 定义 7.8 图的应用——关键路径

90 7.8.2 定义 事件vi的最早发生时间ve(i)：从源点到顶点vi的最长路径的长度。最早时间是通过“从前向后”（即从源点到汇点）的顺序求解的。 比如，事件v4的最早发生时间从(v0 ,v1,v4)计算的结果是7，从(v0 ,v2,v4)计算的结果是5 。最终结果是7。 7.8 图的应用——关键路径

91 7.8.2 定义 事件vi的最晚发生时间vl(i)：在保证汇点按其最早发生时间发生这一前提下，事件vi的最晚发生时间。最晚时间是通过“从后向前”（即从汇点到源点）的顺序求解的。 比如，事件v4的最早发生时间是7，因此v2的最晚发生时间是6（最早发生时间是4）。 7.8 图的应用——关键路径

92 7.8.2 定义 ve(i)=vl(i)的事件对应的顶点构成了关键路径。关键路径体现了完成整个工程任务所需的最小时间。
关键活动：关键路径上的活动。 比如， v2的最晚和最早发生时间不一致，因此(v0 ,v2,v4)不是关键路径，而(v0 ,v1,v4 )是关键路径 7.8 图的应用——关键路径

93 7.8.3 求解关键路径算法 第一步：计算事件最早发生时间ve(i) vi(第i个顶点) 1 2 3 4 5 6 7 8 ve(i) 16
1 2 3 4 5 6 7 8 ve(i) 16 14 18 7.8 图的应用——关键路径

94 7.8.3 求解关键路径算法 第二步：计算事件最晚发生时间vl(i) vi(第i个顶点) 1 2 3 4 5 6 7 8 ve(i) 16
1 2 3 4 5 6 7 8 ve(i) 16 14 18 vl(i) 10 ve(i)=vl(i)的事件vi对应的顶点构成了关键路径 关键路径有两条：（V0,V1,V4,V6,V8），（V0,V1,V4,V7,V8）。 关键活动分别是：（a1,a4,a7,a10）,（a1,a4,a8,a11）。 7.8 图的应用——关键路径

95 9. 图的应用 ——最短路径（1）

96 7.9.1 背景 最短路径的典型应用是旅游路线的选择问题。
迪科斯彻 （E.W.Dijkstra， ），荷兰人, 著名计算机科学家。1972年获得图灵奖。Dijkstra的贡献有：提出“goto有害论”，提出信号量和PV原语，解决了有趣的“哲学家聚餐”问题，创造最短路径算法和银行家算法等 7.9 图的应用——最短路径（1）

97 7.9.2 分类和评价 最短路径问题分为两种 求从某一点出发到其余各点的最短路径——用迪科斯彻（Dijkstra）算法
求图中每一对顶点之间的最短路径——用佛罗依德（Floyd）算法（又称为Floyd-Warshall算法） 虽然可以通过以图中每个顶点为源点重复调用n次Dijkstra算法来求出每一对顶点之间的最短路径，但是用Floyd算法可以更高效。这两种做法的时间复杂度都是O（n3）。 7.9 图的应用——最短路径（1）

98 7.9.2 分类和评价 Dijkstra算法局限于边的权值非负的情况。负权边情况可以用Bellman-Ford等算法。
Floyd算法可以在任何图中使用，包括带负权边的图。 什么时候边权重为负值？ 比如：A上班离家里很远，他要选择一条从家里到公司的最佳路径，使得费用最小。而公司的话，对于做公交车的那段路有补贴，且补贴的钱大于坐公交车的费用，此时，在计算最小费用的时候，这条边的权值就应该定义为负值 7.9 图的应用——最短路径（1）

99 7.9.3 Dijkstra算法思路 对于图G=(V,E)，将图中的顶点分成两组： 第一组S：已求出的最短路径的顶点集合。
第二组V－S：尚未求出的最短路径的顶点集合。 算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中，直到所有顶点都被加入到第一组顶点集S为止。 7.9 图的应用——最短路径（1）

100 7.9.3 Dijkstra算法思路 Dijkstra算法的动画 7.9 图的应用——最短路径（1）

101 7.9.4 Dijkstra算法举例 问题：求解下图中从v1到其他顶点的最短距离。 7.9 图的应用——最短路径（1）

102 7.9.4 Dijkstra算法举例 第一步，开始S={v1}。 i 1 2 3 4 5 6 path[i] v1 dist[i] 50
dist[i] 50 10 ∞ 45 path[i]中存放顶点i的当前最短路径（为区分中间结果和最后结果，这里只显示最后结果）。 dist[i]中存放顶点i的当前最短路径长度。 7.9 图的应用——最短路径（1）

103 7.9.4 Dijkstra算法举例 第二步，v3的dist[i]最小，因此把v3加入S。 i 1 2 3 4 5 6 path[i] v1
 v1v3 dist[i] 50 10 25 45 ∞ 7.9 图的应用——最短路径（1）

104 7.9.4 Dijkstra算法举例 第三步，v4的dist[i]最小，因此把v4加入S。 i 1 2 3 4 5 6 path[i] v1
 v1v3  v1v3v4 dist[i] 45 10 25 ∞ 7.9 图的应用——最短路径（1）

105 7.9.4 Dijkstra算法举例 第四步，v2和v5的dist[i]最小，因此把v2和v5加入S。
1 2 3 4 5 6 path[i] v1  v1v3v4v2  v1v3  v1v3v4  v1v5 dist[i] 45 10 25 ∞ 第五步，v6没改进，还是∞。算法结束。 7.9 图的应用——最短路径（1）

106 10. 图的应用 ——最短路径（2）

107 7.10.1 Floyd算法思路 算法分成n个步骤（n是顶点数量）。
在第k（k=1，...，n）步，判断所有的i和j（i=1，...，n，j=1，...，n）两个顶点之间距离能否通过第k个顶点而缩短。即若有i和j之间的当前距离dist(ij)> dist(ik)+ dist(kj)，则更新dist(ij)。 当查完所有的k时，dist(ij)里面存放的就是i到j之间的最短距离了。 7.10 图的应用——最短路径（2）

108 Floyd算法举例 问题：求解下图中每一对顶点之间的最短距离。 7.10 图的应用——最短路径（2）

109 Floyd算法举例 初始状态 7.10 图的应用——最短路径（2）

110 Floyd算法举例 第一步 对不在三条线上的元素进行判断。举例说明，因为dist(3,2)=∞>dist(3,1)+dist(1,2)=20+50=70 所以dist(3,2)更新为70 7.10 图的应用——最短路径（2）

111 Floyd算法举例 第二步 7.10 图的应用——最短路径（2）

112 Floyd算法举例 第三步 7.10 图的应用——最短路径（2）

113 Floyd算法举例 第四步 7.10 图的应用——最短路径（2）

114 Floyd算法举例 第五步 7.10 图的应用——最短路径（2）

115 Floyd算法举例 第六步 7.10 图的应用——最短路径（2）

116 总结

117 7.2.10 欧拉回路 若恰通过图中每条边一次回到起点，则称该回路为欧拉回路。具有欧拉回路的图称为欧拉图。
定理：一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数。一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。 七桥问题的简化 7.2 图的相关术语

118 7.8.2 定义（可暂时不看） 活动ai的最早开始时间e(i)：如果活动ai对应的弧为<j,k>，则：e(i)=ve(j)
活动ai的最晚开始时间l(i)：如果活动ai对应的弧为<j,k>，其持续时间为dut（<j,k>）则有：l(i)=vl(k)-dut（<j,k>） 活动ai的松弛时间：l(i)-e(i)。松弛时间为0的活动为关键活动。 7.8 图的应用——关键路径