Datastrucstures And Algorithms:Graphs 第七章图 1、 图的基本概念 图的存储表示 图的遍历与连通性 4、 最小生成树 5、最短路径 6、 活动网络 ALDS
1 物料管理 ALDS 1 DataStrucstures And Algorithms:Graphs 1、图的基本概念 2、图的存储表示 3、图的遍历与连通性 4、最小生成树 5、最短路径 6、活动网络 第七章 图
Datastrucstures And Algorithms:Graphs 图的基本概念 有向图G1 无向图G2 B ·结点或顶点： B ·结点或顶点： B ·有向边（弧）、弧尾或初始结 ·无向边或边 点、弧头或终止结点 A B ·有向图：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)} 2 ALDS
2 物料管理 ALDS 2 DataStrucstures And Algorithms: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
Datastrucstures And Algorithms:Graphs 图的基本概念 有向图G1 有向图G1的子图 A B A A B A B D C D D 无向图G2 无向图G2的子图 A B B E E E D 3 ALDS
3 物料管理 ALDS 3 DataStrucstures And Algorithms: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
Datastrucstures And Algorithms:Graphs 图的基本概念 无向图的连通性 ·路径：在无向图G=(N,{E)中由顶点v至v’的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 ·简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v’之间有路径存在 连通图：无向图图G的任意两点之间都是连通的，则称G是连通图。 连通分量：极大连通子图 无向图G 无向图G的三个连通分量 M 4 ALDS
4 物料管理 ALDS 4 DataStrucstures And Algorithms: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的三个连通分量
Datastrucstures And Algorithms:Graphs 图的基本概念 有向图的连通性 路径：在有向图G=(八，{E》中由顶点V经有向边至v’的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 ·简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v’之间有路径存在 ·强连通图：有向图图G的任意两点之间都是连通的，则称G是强连通图。 •强连通分量：极大连通子图 有向图G 有向图G的两个强连通分量 A B A B C D D 5 ALDS
5 物料管理 ALDS 5 DataStrucstures And Algorithms:Graphs 图的基本概念 有向图的连通性 •路径：在有向图G=(V,{E})中由顶点v经有向边至v‘’ 的顶点序列。 •回路或环：第一个顶点和最后一个顶点相同的路径。 •简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 •连通：顶点v至v‘’ 之间有路径存在 •强连通图：有向图图 G 的任意两点之间都是连通的，则称 G 是强连通图。 •强连通分量：极大连通子图 有向图G 有向图G的两个强连通分量 A B C D A B C D
Datastrucstures And Algorithms:Graphs 图的基本概念 生成树：极小连通子图。包含图的所有n个结点，但只含图的-1条边。在生成树中添 加一条边之后，必定会形成回路或环。 无向图G 无向图G的生成树 B M M b ALDS
6 物料管理 ALDS 6 DataStrucstures And Algorithms:Graphs 图的基本概念 •生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添 加一条边之后，必定会形成回路或环。 A B C D E H M A B C D E H M 无向图G 无向图G的生成树
Datastrucstures And Algorithms:Graphs 图的基本概念 完全 图：有n(n-1)2条边的无向图。其中n是结点个数。 图 有向完全图：有n(n-)条边的有向图。其中n是结点个数。 C 22 •边的权值，边有权的图称之为网络。 其它术语 邻接点： 无向图结点的度 •有向图结点的出度和入度 无向图G1 有向图G2 A B M D 7 ALDS
7 物料管理 ALDS 7 DataStrucstures And Algorithms:Graphs 图的基本概念 •完 全 图：有 n(n-1)/2 条边的无向图。其中 n 是结点个数。 •有向完全图：有 n(n-1) 条边的有向图。其中 n 是结点个数。 •边的权值，边有权的图称之为网络。 •邻接点： •无向图结点的度 •有向图结点的出度和入度 A B C D E H M 无向图G1 图 的 其 它 术 语 有向图G2 A B C D 2 n 2 2 n
Datastrucstures And Algorithms:Graphs 图的基本概念 图的抽象数据类型ADT Data: 和边的集合。边是连接顶一对顶点(v,u)或的，其中(v,u)连接顶点v和u的无向 边，而.是连接顶点v到u的有向边。边可以有一权值，或称为从一个顶点到 另一个顶点的代价。 Operations: Constructor 前提：无。 结果：创建 一个包含顶点和边的集合的图。 Getweight 前提：顶点V和V组成的顶点对的数据值，i 该顶点对必须属于该图。 结果：如果顶点V和V,之间的边如果存在，则返回其权值。 GetNeighbor 前提：顶点V。 结果：返回和顶点相邻接的所有的顶点。 InsertVertex 前提：一个新的顶点。 结果：将该新顶点插入到图的顶点集合。 InsertEdge 前提：一条边的顶点V和U及其它们的权值，且顶点V和U己在图中 而顶点V到U的边不在图中。 结果：将该条边插入到图中，图的边的集合的规模增大1。 Remove Vertex 前提： 顶点V的数据值，并且它必须存在于图的顶点集之中。 结果：将该顶点删除，并且删除从顶点V出发的，和进入顶点V的所 有的边。图的边的集合和顶点的集合规模被更新。 RemoveEde 前提：一条边的顶点V和U及其它们的权值，且相应的权值必须存在 于顶点的值的集合之中。 结果：如果该条边存在，则将它从图中删除，图的边的少1。 ALDS
8 物料管理 ALDS 8 DataStrucstures And Algorithms:Graphs 图的基本概念 • 图的抽象数据类型 ADT Data: 和边的集合。边是连接顶一对顶点(v,u) 或 的，其中(v,u) 连接顶点v和u的无向 边，而.是连接顶点 v 到 u 的有向边。边可以有一权值，或称为从一个顶点到 另一个顶点的代价。 Operations: Constructor 前提：无。 结果：创建一个包含顶点和边的集合的图。 Getweight 前提：顶点 VI和 Vj 组成的顶点对的数据值，该顶点对必须属于该图。 结果：如果顶点 VI和 Vj 之间的边如果存在，则返回其权值。 GetNeighbor 前提：顶点 V。 结果：返回和顶点相邻接的所有的顶点。 InsertVertex 前提：一个新的顶点。 结果：将该新顶点插入到图的顶点集合。 InsertEdge 前提：一条边的顶点 V 和 U 及其它们的权值，且顶点 V 和 U已在图中 ，而顶点 V 到 U 的边不在图中。 结果：将该条边插入到图中，图的边的集合的规模增大1。 RemoveVertex 前提：顶点 V 的数据值，并且它必须存在于图的顶点集之中。 结果：将该顶点删除，并且删除从顶点 V 出发的，和进入顶点 V 的所 有的边。图的边的集合和顶点的集合规模被更新。 RemoveEde 前提：一条边的顶点 V 和 U 及其它们的权值，且相应的权值必须存在 于顶点的值的集合之中。 结果：如果该条边存在，则将它从图中删除，图的边的少1
Datastrucstures And Algorithms:Graphs 图的存储表示 图的四种常用的存储形式： 邻接矩阵和加权邻接矩阵(labeled adjacency matrix) 邻接表 十字链表 •邻接多重表 1、邻接矩阵和加权邻接矩阵(labeled adjacency matrix) 无权值的有向图的邻接矩阵 设有向图具有n个结点，则用n行n列的布尔矩阵A表示该有向图； 并且A[,]=1,如果i至j有一条有向边；A[,j]=0如果i至j没有一条有向边 注意：A,j=0。出度：i行之和。入度：j列之和。 B 0110 表示成右图矩阵 0000 0001 0 0 0 D 9 ALDS
9 物料管理 ALDS 9 DataStrucstures And Algorithms: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
Datastrucstures And Algorithms:Graphs 图的存储表示 无权值的有向图的邻接矩阵 设有向图具有n个结点，则用n行n列的布尔矩阵A表示该有向图； 并且A[,]=1,如果1至j有一条有向边；A,]=0如果i至j没有一条有向边 注意：A,门=0。出度：行之和。入度：j列之和。 0 1 2 3 0 0 1 表示成右图矩阵 1 0 0 2 0 0 3 在物理实现时的考虑：分别用0、1、2、3分别标识结点A、B、C、D。而将真 正的数据场之值放入以个一维数组之中。注意：这里的数据场之值是逻辑意义上 的。 0 1 2 3 A B C D 10 ALDS
10 物料管理 ALDS 10 DataStrucstures And Algorithms:Graphs 图的存储表示 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 •在物理实现时的考虑：分别用 0、1、2、3 分别标识结点A、B、C、D。而将真 正的数据场之值放入以个一维数组之中。注意：这里的数据场之值是逻辑意义上 的。 0 1 2 3 0 1 2 3 A B C D 0 1 2 3