数据结构幻灯片讲稿-图.ppt

Page *;Page *;Page *;;图的基础知识;*;;*;最短路问题（SPP－shortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。;运输问题(transportation problem) 某种原材料有N个产地，现在需要将原材料从产地运往M个使用这些原材料的工厂。假定N个产地的产量和M家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？;上述问题有两个共同的特点： 一、 它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题； 二、 它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。;线性表 每个数据元素只有一个直接前驱和一个直接后继。 树形结构 每个数据元素只有一个直接前驱，但可能有多个直接后继。 图形结构 每个数据元素可能有多个直接前驱和多个直接后继。;*;Page *;Page *;邻接、依附 无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。;*;*;*;*;*;;*;*;*;*;*;*;*;*;Page *;*;*;*;图的基础知识;*;Page *;Page *; GetVex(G, v);初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：返回 v 的值。 FirstAdjVex(G, v);初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：返回 v 的第一个邻接点。若该顶点在 G 中没 有邻接点，则返回“空”。 NextAdjVex(G, v, w);初始条件：图 G 存在，v 是 G 中某个顶点，w 是 v 的 邻接顶点。操作结果：返回 v 的（相对于 w 的）下一个邻接点。若 w 是 v 的最后一个邻接点，则返回“空”。;Page *;*;Page *;*;数组表示法(邻接矩阵) 将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。 假设图中顶点数为n，则邻接矩阵A定义为;*;*;Page *;;*;*;*;*;Page *;;Page *;*;*;;Page *;*;*;Page *;*;Page *;Page *;*;*;*;*;*;Page *;Page *;*;图的基础知识;*;Page *;;;;;*;*;*;*;Page *;;;;;;Page *;*;图的基础知识;;*;*;*;*;*;*;Page *;最小生成树的性质;*;*;*;*;*;*;*;Page *;*;*;*;*;*;*;*;*;*; i 数组;*;*;*;谢谢！