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的无向 边，而<v,>.是连接顶点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的无向 边，而<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