第七章 图 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.

Presentation on theme: "第七章 图 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件."— Presentation transcript:

1 第七章 图 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

2 本章主要内容 图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径

3 图的基本概念 定义 图是由顶点及顶点之间的关系集合组成的数据结构Graph = ( V, E )
V是顶点的有穷非空集，V={x | x∈某个对象} E是顶点之间关系，称为边(edge)的有穷非穷集，E={(x,y) | x,y∈V}

4 图的基本概念 有向图与无向图 完全图 有向图中，顶点对(x,y)是有序的 无向图中，顶点对(x,y)是无序的
n个顶点的无向图有n(n-1)/2条边,该图为完全图 n个顶点的有向图有n(n-1)条边,该图为完全有向图 6 8 1 2 1 1 2 3 4 5 6 7 2 3 完全无向图 无向图(自由树) 有向图 完全有向图

5 图的基本概念 邻接顶点 子图 权：边附带的权重，称这样的图称为带权图 (u, v)是E中的一条边，则称u与v互为邻接顶点
设有两个图 G＝(V, E) 和 G’＝(V’, E’)。若 V’ V 且 E’E, 则称G’是G 的子图 权：边附带的权重，称这样的图称为带权图 子图 1 2 1 1 2 1 2 3 3 3 3

6 图的基本概念 顶点v的度 路径 与v为端点的边条数，记作D(v) 入度：有向图中,以v为终点的边的条数,记作ID(v)
出度：有向图中,以v为始点的边的条数,记作OD(v) 有向图中v的度为入度与出度的和 路径 图 G＝(V, E) 中, 从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 (vi vp1 vp2 ... vpm vj)为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj) 应是属于E的边。

7 图的基本概念 路径长度 简单路径 回路 非带权图的路径长度是指此路径上边的条数 带权图的路径长度是指路径上各边的权之和
路径上各顶点 v1,v2,...,vm 均不互相重复 回路 路径上第一个顶点 v1 与最后一个顶点vm 重合

8 图的基本概念 连通图与连通分量 无向图中, 从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。
若图中任意一对顶点都是连通的, 则此图是连通图 非连通图的极大连通子图叫连通分量 1 2 4 5 1 2 4 5 3 3 连通图 非连通图(有2个连通分量)

9 图的基本概念 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图 非强连通图的极大强连通子图叫做强连通分量 生成树 一个连通图的生成树是其极小连通子图，在 n 个顶点的情形下，有n-1条边。

10 图的存储表示 邻接矩阵 一个有 n 个顶点的图G = ( V, E )， 图的邻接矩阵是一个二维数组 A.edge[n][n] 2 1 3
1 2 有向图的邻接矩阵可能不对称 无向图的邻接矩阵是对称的

11 图的存储表示 邻接矩阵 网络(带权图)的邻接矩阵 3 2 1 8 6 9 5 4

12 图的存储表示 邻接表 无向图的邻接表 dest link dest link D B C A data link 1 2  2 1 3 C
C B D A 3   1  顶点数组 链接结点 dest保存的是邻接顶点的下标

13 图的存储表示 邻接表 有向图的邻接表和逆邻接表 dest link data link B C A 1  2 1 C  B A dest
C  B A dest link 2  邻接表(出边表) dest link data link 1  2 1 C B A  2  逆邻接表(入边表)

14 图的存储表示 网络(带权图)的邻接表 C D B A 8 6 3 9 5 2 1 4 C B D A 2 1 3 data link
data link cost 6  4 dest 9 5 8 邻接表(出边表)

15 图的遍历 从给定顶点出发，沿某些边遍历图中所有顶点一次且仅一次 使用辅助数组visited[ ]标识顶点是否被访问过
访问过后标识为1

16 图的遍历 遍历方式 深度优先遍历 DFS (Depth First Search)
广度优先遍历 BFS (Breadth First Search)

17 图的遍历 遍历方式 深度优先遍历 DFS (Depth First Search) 从顶点v1出发，访问任一未被访问的邻接顶点v2;
退回一步到刚被访问的顶点，看是否有未被访问的邻接顶点。 若有，则继续访问 否则，再退回一步 直到所有顶点都被访问

18 图的遍历 遍历方式 深度优先遍历 DFS (Depth First Search) A B E D C G F H I A B E D C
前进 回退 1 2 3 A B E D C G F H I 1 2 3 4 5 6 7 8 9 A B E D C G F H I 7 5 4 6 8 9 深度优先搜索过程 深度优先生成树

19 图的遍历 遍历方式 广度优先遍历 BFS (Breadth First Search)
从起始顶点v出发，依次访问v的未被访问的邻接顶点w1, w2, … , wm 顺序访问w1, w2, … , wm的所有未被访问的邻接顶点,以此类推，直到所有顶点都被访问

20 图的遍历 遍历方式 广度优先遍历 BFS (Breadth First Search) A B E D C G F H I A B E D
1 2 5 A B E D C G F H I 1 2 5 3 6 4 8 9 A B E D C G F H I 4 3 7 6 8 9 广度优先搜索过程 广度优先生成树

21 作业： n个顶点无向图，邻接矩阵形式存储在矩阵Edge[N][N]， 用visited记录是否访问过，初始时visited[N]={0} 写出深度优先遍历程序： DFS(0, Edge[][]) { } 写出广度优先遍历程序： BFS(0, Edge[][]) {

22 图的遍历 遍历方式 深度优先遍历 DFS (Depth First Search)
回溯算法 广度优先遍历 BFS (Breadth First Search) 分层算法

23 图的连通性 当无向图不连通时，从顶点v出发，遍历方法只能遍历v所在连通分量上的所有顶点 A C D E G B F H K J L I A
非连通无向图 A C D E G B F H K J L I 一种遍历生成森林

24 图的连通性 强连通有向图 A D A D C F C F B E B E A D A D C C F F B E B E
不同出发点得到生成树不同 A C D E B F 1 2 3 4 6 5 A C D E B F 非强连通图 A C D E B F 5 1 6 2 4 3 2 3 4 5 1 6 A C D E B F

25 图的连通性 非强连通有向图 3 4 5 A C B 2 1 D E A C D E B 1 2 3 5 4 A C D E B
遍历可能生成的不是树，而是森林 3 4 5 A C B 2 1 D E A C D E B 生成森林 非强连通图 D,E不能到达A,B,C 但A,B,C可到达D,E 1 2 3 5 4 A C D E B 生成树

26 最小生成树 在连通带权图上构造一棵生成树，使得该树上边权值的总和最小 连通带权图 生成树(n个顶点，n-1条边，无回路) 边的权值总和最小

27 最小生成树 克鲁斯卡尔 (Kruskal) 算法 初始时所有顶点自成一连通分量
在图上选权值最小的边emin，判断emin两端点是否属于不同连通分量ci,cj 若是，将ci,cj用emin连接成同一个连通分量 否则，舍弃emin 重复上一过程，直到所有顶点在同一连通分量

28 最小生成树 克鲁斯卡尔 (Kruskal) 算法 5 4 6 1 3 2 5 4 6 1 3 2 5 4 6 1 3 2 5 4 6 1 3
28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 4 6 1 3 2 5 4 6 1 3 2 10 5 4 6 1 3 2 10 12 5 4 6 1 3 2 10 14 12 5 4 6 1 3 2 10 14 16 12 5 4 6 1 3 2 10 14 22 16 12 5 4 6 1 3 2 10 25 14 22 16 12

29 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 5 4 6 1
可使用并查集技术加快判断速度 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 4 6 1 3 2 10 (0,5) 初始时 12 (2,3) 14 (1,6) 16 (1,2) 18 (3,6) 22 (3,4) 24 (4,6) 25 (4,5)

30 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 5 4 6 1
可使用并查集技术加快判断速度 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 4 6 1 3 2 10 (0,5) 12 (2,3) 14 (1,6) 取边(0,5) 16 (1,2) 18 (3,6) 22 (3,4) 24 (4,6) 25 (4,5)

31 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 5 6 3 1
可使用并查集技术加快判断速度 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 6 3 1 4 2 10 (0,5) 12 (2,3) 14 (1,6) 取边(2,3) 16 (1,2) 18 (3,6) 22 (3,4) 24 (4,6) 25 (4,5)

32 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 5 6 3 1
可使用并查集技术加快判断速度 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 6 3 1 4 2 10 (0,5) 12 (2,3) 14 (1,6) 取边(1,6) 16 (1,2) 18 (3,6) 22 (3,4) 24 (4,6) 25 (4,5)

33 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 5 6 1 4
可使用并查集技术加快判断速度 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 6 1 4 3 2 10 (0,5) 12 (2,3) 14 (1,6) 16 (1,2) 18 (3,6) 22 (3,4) 取边(1,2) 24 (4,6) 25 (4,5)

34 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 5 6 1 4
可使用并查集技术加快判断速度 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 6 1 4 3 2 10 (0,5) 12 (2,3) 14 (1,6) 16 (1,2) 18 (3,6) 22 (3,4) 取边(3,6) 24 (4,6) 25 (4,5)

35 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 5 6 1 4
可使用并查集技术加快判断速度 28 22 5 4 6 1 3 2 10 25 14 24 16 18 12 5 6 1 4 3 2 10 (0,5) 12 (2,3) 14 (1,6) 16 (1,2) 18 (3,6) 22 (3,4) 取边(3,4) 24 (4,6) 25 (4,5)

36 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 5 6 1 4
可使用并查集技术加快判断速度 28 22 5 4 6 1 3 2 10 25 14 24 16 18 12 5 6 1 4 3 2 10 (0,5) 12 (2,3) 14 (1,6) 16 (1,2) 18 (3,6) 22 (3,4) 取边(4,6) 24 (4,6) 25 (4,5)

37 最小生成树 克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 5 4 6 1 3 2 6 1 4 5
可使用并查集技术加快判断速度 28 25 22 5 4 6 1 3 2 10 14 24 16 18 12 6 1 4 5 3 2 10 (0,5) 12 (2,3) 14 (1,6) 16 (1,2) 18 (3,6) 22 (3,4) 取边(4,5) 此时所有顶点属于同一连通分量，结束 24 (4,6) 25 (4,5)

38 最小生成树 普里姆(Prim) 算法 初始时令生成树T为图中任一顶点v0 找u∈T，v∉ T，且边(u,v)权值最小，将v加入T中

39 最小生成树 普里姆(Prim) 算法 设初始时生成树中只有顶点 0 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 10 10 25 5 4 5 4 3 10 25 22 5 4 3 2 10 25 22 12 5 4 1 3 2 10 25 22 16 12 5 4 6 1 3 2 10 25 14 22 16 12

40 最短路径 寻找从一顶点到另一顶点路径，使得该路径上边的权值总和最小 单源最短路径 (一个顶点到其他顶点) 所有顶点之间最短路径
非负权值 (Dijkstra算法) 任意权值 (Bellman-Ford算法) 所有顶点之间最短路径 Floyd算法

41 最短路径 单源最短路径的Dijkstra算法 给定带权图 (每条边权值 ≥ 0) 给定源点v，求v到其他顶点的最短路径

42 最短路径 Dijkstra算法 初始时令S={v0}，dist[v0]=0, dist[i]=Edge[v0][i]
找u∈S,v∉S,且dist[u]+Edge[u][v]最小, 则将v加入S中，dist[v]=dist[u]+Edge[u][v] 重复上一步骤，直到所有顶点都加入S中

43 最短路径 Dijkstra算法(不记录路径) 1 4 2 3 1 1 3 1 2 3 1 4 2 3 原图 10 50 30 100 60
1 4 2 3 50 30 100 60 20 d=0 10 1 d=0 d=10 原图 d=0 d=10 10 1 30 3 d=30 d=30 10 1 2 3 20 d=0 d=10 30 d=50 10 1 4 2 3 30 20 d=0 d=10 d=30 d=50 d=60

44 最短路径 Dijkstra算法(记录路径) 1 4 2 3 1 1 3 1 2 3 1 4 2 3 原图 10 50 30 100 60
1 4 2 3 50 30 100 60 20 d[0]=0 p[0]=-1 10 1 d[0]=0 p[0]=-1 d[1]=10 p[1]=0 原图 d[0]=0 p[0]=-1 d[1]=10 p[1]=0 10 1 30 3 d[3]=30 p[3]=0 d[3]=30 p[3]=0 10 1 2 3 20 d[0]=0 p[0]=-1 d[1]=10 p[1]=0 30 d[2]=50 p[2]=3 10 1 4 2 3 30 20 d[0]=0 p[0]=-1 d[1]=10 p[1]=0 d[3]=30 p[3]=0 d[2]=50 p[2]=3 d[4]=60 p[4]=2

45 最短路径 Dijkstra算法(记录路径) 1 4 2 3 1 4 2 3 原图 获取最短路径方法，以顶点4为例： p[4]=3
10 1 4 2 3 50 30 100 60 20 10 1 4 2 3 30 20 d[0]=0 p[0]=-1 d[1]=10 p[1]=0 d[3]=30 p[3]=0 d[2]=50 p[2]=3 d[4]=60 p[4]=2 原图 获取最短路径方法，以顶点4为例： p[4]=3 p[3]=2 p[2]=0 反向读得0到4的最短路径为 (0,3,2,4)

46 用顶点表示活动的网络(AOV) 画流程图、工程图等 (用有向图表示) 顶点表示活动 有向边表示两活动间的先后关系
一活动须先于另一活动完成 例如盖楼，打地基和砌墙有先后关系 图中有向边(u,v)，则称u是v的直接前驱，v是u的直接后继

47 用顶点表示活动的网络(AOV) 给定这样的有向图，判断是否存在有向环 使用拓扑排序判定是否存在有向环
若存在有向环，这个有向图设计有问题，一个活动不能先于自身完成 使用拓扑排序判定是否存在有向环 若能将所有顶点排入拓扑序列中，则无有向环

48 用顶点表示活动的网络(AOV) 拓扑排序 例如，有一些课，课程之间有先修后修关系 c1 c8 c9 c7 c3 c4 c2 c5 c6
课程代号 课程名称 先修课程 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C9 计算机原理 c1 c8 c9 c7 c3 c4 c2 c5 c6 课程学习工程图

49 用顶点表示活动的网络(AOV) 拓扑排序 在图中选一个没有直接前驱的顶点，并输出 删除输出的顶点及以它为起点的有向边 重复以上两步，直到：
所有顶点均输出 (不存在有向环) 或找不到没有直接前驱的顶点 (存在有向环)

50 用顶点表示活动的网络(AOV) 拓扑排序 在图中选一个没有直接前驱的顶点，并输出 删除输出的顶点及以它为起点的有向边 重复以上两步，直到：
所有顶点均输出 (不存在有向环) 或找不到没有直接前驱的顶点 (存在有向环) c8 c9 输出拓扑序列： c1 c7 c1 c8 c2 c3 c9 c4 c5 c6 c7 c3 c4 拓扑有序序列不是唯一的 c2 c6 c5

51 用边表示活动的网络(AOE) 工程估算(带权有向无环图) 计算工程至少需要多长时间？哪些是关键活动(为缩短工期应加快哪些活动)？ 边表示活动
边上权值表示活动所需时间 顶点表示事件 计算工程至少需要多长时间？哪些是关键活动(为缩短工期应加快哪些活动)？ 关键路径

52 用边表示活动的网络(AOE) 关键路径 事件vi 的最早可能开始时间Ve(i) 事件vi 的最迟允许开始时间Vl(i)
1 2 3 a1=6 a2=4 a3=1 a4=1 关键路径 事件vi 的最早可能开始时间Ve(i) v0 到vi 的最长路径长度 事件vi 的最迟允许开始时间Vl(i) 结束点的Ve(n-1)减去vi 到vn-1的最长路径长度 活动ak 的最早可能开始时间Ae(k)，设ak在边(i, j)上 v0 到vi 的最长路径长度， Ae(i)=Ve(i) 活动ak 的最迟允许开始时间Al(k) ，设ak在边(i, j)上 结束点的Ve(n-1)减去vj 到vn-1的最长路径长度，再减去ak的长度，(即Vl(j)- dur(i,j)) 用Al[k]-Ae[k]表示活动ak的松弛时间

53 用边表示活动的网络(AOE) 关键路径 先向前递推计算各事件的最早可能开始时间Ve[i] 再逆向递推计算各事件的最迟允许开始时间Vl[i]
Ve[i] = max{ Ve[x] + dur(x, i) } 再逆向递推计算各事件的最迟允许开始时间Vl[i] Vl[n-1]=Ve[n-1] Vl[i] = min{ Vl[x] - dur(i, x) } 根据各顶点的Ve[i]和Vl[i]，求各有向边Ae[i]和Al[i] 其中Ae[i]==Al[i]即为关键活动

54 用边表示活动的网络(AOE) 事件的最早可能开始时间：Ve[i] = max{ Ve[x] + dur(x, i) } 关键路径 前驱顶点Ve[x] 边权值 1 2 3 4 5 6 7 8 开始 结束 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 Ve[0] = 0 Ve[1] = 6 Ve[2] = 4 Ve[3] = 5 Ve[4] = max{Ve[1]+1, Ve[2]+1} = 7 Ve[5] = 7 Ve[6] = 16 Ve[7] = max{Ve[4]+7, Ve[5]+4} = 14 Ve[8] = max{Ve[6]+2, Ve[7]+4} = 18

55 用边表示活动的网络(AOE) 事件的最迟允许开始时间： Vl[i] = min{ Vl[x] - dur(i, x) } 关键路径 后继顶点Vl[x] 边权值 Vl[0] = min{Vl[1]-6, Vl[2]-4, Vl[3]-5} =0 1 2 3 4 5 6 7 8 开始 结束 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 Vl[1] = 6 Vl[2] = 6 Vl[3] = 8 Vl[4] = min{Vl[6]-9, Vl[7]-7} = 7 Vl[5] = 10 Vl[6] = 16 Vl[7] = 14 Vl[8] = Ve[8] = 18

56 用边表示活动的网络(AOE) 关键路径 1 6 4 8 2 7 3 5 活动的最早可能开始时间： Ae[k] = Ve[x]
边ak前驱顶点Ve[x] 1 2 3 4 5 6 7 8 开始 结束 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 Ae[1] = Ve[0] = 0 Ae[2] = Ve[0] = 0 Ae[3] = Ve[0] = 0 Ae[4] = Ve[1] = 6 Ae[5] = Ve[2] = 4 Ae[6] = Ve[3] = 5 Ae[7] = Ve[4] = 7 Ae[8] = Ve[4] = 7 Ae[9] = Ve[5] = 7 Ae[10] = Ve[6] = 16 Ae[11] = Ve[7] = 14

57 用边表示活动的网络(AOE) 活动的最迟允许开始时间： Al[k] = Vl[x] - dur(i, x) 关键路径 边ak的后继顶点Vl[x] 边权值 1 2 3 4 5 6 7 8 开始 结束 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 Al[1] = Vl[1]-6 = 0 Al[2] = Vl[2]-4 = 2 Al[3] = Vl[3]-5 = 3 Al[4] = Vl[4]-1 = 6 Al[5] = Vl[4]-1 = 6 Al[6] = Vl[5]-2 = 8 Al[7] = Vl[6]-9 = 7 Al[8] = Vl[7]-7 = 7 Al[9] = Vl[7]-4 = 10 Al[10] = Vl[8]-2 = 16 Al[11] = Vl[8]-4 = 14

58 用边表示活动的网络(AOE) 关键路径 1 6 4 8 2 7 3 5 Ae[i]==Al[i]即为关键活动 Ae[1] = 0
1 2 3 4 5 6 7 8 开始 结束 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 Ae[1] = 0 Al[1] = 0 Ae[2] = 0 Al[2] = 2 Ae[3] = 0 Al[3] = 3 Ae[4] = 6 Al[4] = 6 Ae[5] = 4 Al[5] = 6 Ae[6] = 5 Al[6] = 8 Ae[7] = 7 Al[7] = 7 Ae[8] = 7 Al[8] = 7 Ae[9] = 7 Al[9] = 10 Ae[10] = 16 Al[10] = 16 Ae[11] = 14 Al[11] = 14