厦门大学：《数据结构》课程教学课件（PPT讲稿）第七章 图

Algorithms and DataStrucstures:Graphs 第七章图 1、 图的定义和术语 2、图的存储结构 3、图的遍历 4、图的连通性问题 5、有向无环图及其应用 6、最短路径 ALDS

1 物料管理 ALDS 1 Algorithms and DataStrucstures:Graphs 1、图的定义和术语 2、图的存储结构 3、图的遍历 4、图的连通性问题 5、有向无环图及其应用 6、最短路径 第七章 图

Algorithms and DataStrucstures:Graphs 图的定义和术语 有向图G1 无向图G2 E D ·结点或顶点： B ·结点或顶点： ·有向边（弧)、弧尾或初始结 ·无向边或边 点、弧头或终止结点 A ·有向图：G1=(V1,{A1}) ·有向图：G2=(V2,{A2}) V1={A,B,C,D]} V2 =[A,B,C,D,E) A1={A,B>,, A2={A,B)(A,C>,(B,D), ,} (B,E>,(C,E),(D,E)} ALDS

2 物料管理 ALDS 2 Algorithms and DataStrucstures:Graphs 图的定义和术语 A B C D A B C D E 有向图 G1 无向图 G2 • 结点或 顶点： • 有向边（弧）、弧尾或初始结 点、弧头或终止结点 A B A B • 有向图：G1 =（V1，{A1}） V1 = {A,B,C,D} A1 = {, , , } • 结点或 顶点： • 无向边或边 A B • 有向图：G2 =（V2，{A2}） V2 = {A,B,C,D,E} A2 = {(A,B), (A,C>,(B,D), (B,E>, (C,E),(D,E)} A B

Algorithms and DataStrucstures:Graphs 图的定义和术语 有向图G1 有向图G1的子图 B 9 B B C 0 D D 无向图G2 无向图G2的子图 B B B E E E D D 3 ALDS

3 物料管理 ALDS 3 Algorithms and DataStrucstures:Graphs 图的定义和术语 A B C D 无向图 G2 A B C D A C A B C D 有向图G1的子图 A B C D E A B D E A A B C D A B C D E 无向图G2的子图 有向图 G1

Algorithms and DataStrucstures:Graphs 图的定义和术语 无向图的连通性 ·路径：在无向图G=(N,E)中由顶点v至v'的顶点序列。 ·回路或环：第一个顶点和最后一个顶点相同的路径。 ·简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v”之间有路径存在 ·连通图：无向图图G的任意两点之间都是连通的，则称G是连通图。 ·连通分量：极大连通子图 无向图G 无向图G的三个连通分量 E M c ALDS

4 物料管理 ALDS 4 Algorithms and DataStrucstures:Graphs 图的定义和术语 无向图的连通性 A B C D E •路径：在无向图G=(V,{E})中由顶点v至v‘’ 的顶点序列。 •回路或环：第一个顶点和最后一个顶点相同的路径。 •简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 •连通：顶点v至v‘’ 之间有路径存在 •连通图：无向图图 G 的任意两点之间都是连通的，则称 G 是连通图。 •连通分量：极大连通子图 F G I J L H M K A B C D E H M F G I J K L 无向图G 无向图G的三个连通分量

Algorithms and DataStrucstures:Graphs 图的定义和术语 有向图的连通性 ·路径：在有向图G=(VE)中由顶点v经有向边至v”的顶点序列。 ·回路或环：第一个顶点和最后一个顶点相同的路径。 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v”之间有路径存在 强连通图：有向图图G的任意两点之间都是连通的，则称G是强连通图。 •强连通分量：极大连通子图 有向图G 有向图G的两个强连通分量 D 5 ALDS

5 物料管理 ALDS 5 Algorithms and DataStrucstures:Graphs 图的定义和术语 有向图的连通性 •路径：在有向图G=(V,{E})中由顶点v经有向边至v‘’ 的顶点序列。 •回路或环：第一个顶点和最后一个顶点相同的路径。 •简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 •连通：顶点v至v‘’ 之间有路径存在 •强连通图：有向图图 G 的任意两点之间都是连通的，则称 G 是强连通图。 •强连通分量：极大连通子图 有向图G 有向图G的两个强连通分量 A B C D A B C D

Algorithms and DataStrucstures:Graphs 图的定义和术语 ,生成树：极小连通子图。包含图的所有个结点，但只含图的n-1条边。在生成树中添 加一条边之后，必定会形成回路或环。 无向图G 无向图G的生成树 B H M M ALDS

6 物料管理 ALDS 6 Algorithms and DataStrucstures:Graphs 图的定义和术语 •生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添 加一条边之后，必定会形成回路或环。 A B C D E H M A B C D E H M 无向图G 无向图G的生成树

Algorithms and DataStrucstures:Graphs 图的定义和术语 完全图：有n(n-1)/2条边的无向图。其中n是结点个数。 图的其它 有向完全图：有n(n-)条边的有向图。其中n是结点个数。 ·边的权值，边有权的图称之为网络。 邻接点： 香 •无向图结点的度 •有向图结点的出度和入度 无向图G1 有向图G2 B ALDS

7 物料管理 ALDS 7 Algorithms and DataStrucstures:Graphs 图的定义和术语 •完 全 图：有 n(n-1)/2 条边的无向图。其中 n 是结点个数。 •有向完全图：有 n(n-1) 条边的有向图。其中 n 是结点个数。 •边的权值，边有权的图称之为网络。 •邻接点： •无向图结点的度 •有向图结点的出度和入度 A B C D E H M 无向图G1 图 的 其 它 术 语 有向图G2 A B C D

Algorithms and DataStrucstures:Graphs 图的存储结构 图的四种常用的存储形式： .邻接矩阵和加权邻接矩阵(labeled adjacency matrix) 邻接表 十字链表 •邻接多重表 1、邻接矩阵和加权邻接矩阵(labeled adjacency matrix) 无权值的有向图的邻接矩阵 设有向图具有n个结点，则用n行n列的布尔矩阵A表示该有向图； 并且A[,j=1,如果i至j有一条有向边；A[l,=0如果i至j没有一条有向边 注意：A,]=0。出度：i行之和。入度：j列之和。 A B 0 1 1 0 表示成右图矩阵 0 00 0 0 0 0 1 1 0 0 0 D ALDS

8 物料管理 ALDS 8 Algorithms and DataStrucstures:Graphs 图的存储结构 图的四种常用的存储形式： •邻接矩阵和加权邻接矩阵（labeled adjacency matrix） •邻接表 •十字链表 •邻接多重表 1、邻接矩阵和加权邻接矩阵（labeled adjacency matrix） A B C D •无权值的有向图的邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图； 并且 A[i,j] = 1 , 如果i 至 j 有一条有向边；A[I,j] = 0如果 i 至 j 没有一条有向边 注意： A[i,i] = 0。出度: i行之和。入度: j列之和。 表示成右图矩阵 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0

Algorithms and DataStrucstures:Graphs 图的存储结构 1、邻接矩阵和加权邻接矩阵(labeled adjacency matrix) (续) 无权值的无向图的邻接矩阵 设无向图具有n个结点，则用n行n列的布尔矩阵A表示该无向图； 并且A,j=1,如果i至j有一条无向边；Al,】=0如果i至j没有一条无向边 注意：A[,]=0。结点的度：行或列之和。上三角矩阵或下三角矩阵。 B 01100 1 0 0 11 E 表示成右图矩阵 10001 0100 1 D 0111 0 ALDS

9 物料管理 ALDS 9 Algorithms and DataStrucstures:Graphs 图的存储结构 1、邻接矩阵和加权邻接矩阵（labeled adjacency matrix）（续） •无权值的无向图的邻接矩阵 设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图； 并且 A[i,j] = 1 , 如果i 至 j 有一条无向边；A[I,j] = 0如果 i 至 j 没有一条无向边 注意： A[i,i] = 0。i结点的度: i行或i列之和。上三角矩阵或下三角矩阵。 表示成右图矩阵 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 0 A B C D E

Algorithms and DataStrucstures:Graphs 图的存储结构 1、邻接矩阵和加权邻接矩阵(labeled adjacency matrix) (续) •有向图的加权邻接矩阵 设有向图具有n个结点，则用n行n列的矩阵A表示该有向图； 并且A[,】=a,如果i至j有一条有向边且它的权值为a。A[心，j]=空或其它标 志；如果1至j没有一条有向边。 a A B 表示成右图矩阵 6 b a D a 优点：判断任意两点之间是否有边方便，仅耗费O()时间。 缺点：即使<n2条边，也需内存n2单元，太多；仅读入数据耗费O(n2) 10 时间，太长。 ALDS

10 物料管理 ALDS 10 Algorithms and DataStrucstures:Graphs 图的存储结构 1、邻接矩阵和加权邻接矩阵（labeled adjacency matrix）（续） •有向图的加权邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图； 并且 A[i,j] = a , 如果i 至 j 有一条有向边且它的权值为a。A[i,j] = ‘空 或其它标 志；如果 i 至 j 没有一条有向边。 A B C D 表示成右图矩阵 a b b b a a a a b a b b 优点：判断任意两点之间是否有边方便，仅耗费 O(1) 时间。 缺点：即使 << n2 条边，也需内存 n2 单元，太多; 仅读入数据耗费 O( n2 ) 时间，太长