数据结构C 清华版 3第三部分.ppt

第三部分 图 一、 图的定义和基本概念 二、 图的基本操作 三、 图的存储结构 四、 图的遍历 五、 最小生成树 六、 拓扑排序 七、 最短路径和关键路径 2、其它术语 有向图、弧(arc)、弧尾(tail)或始点(initial node)、弧头(head)或终点(terminal node)、完全有向图、无向图、边(edge) 、完全无向图或称完全图、子图和生成子图、度(degree)、入度和出度、路径(path)、回路或环(cycle)、简单路径、简单回路或简单环。路径长度、连通图、强连通图、弱连通图、连通分量、强连通分量、生成树、森林、权(weight)、带权图、网络 根据上述图的定义和有关的其他术语，我们有如下性质： 性质1：无论是无向图还是有向图，如果含有n个顶点， 每个顶点的度为di，则其边（或弧）数目e为： 根据上述图的定义和有关的其他术语，有如下性质： 性质2：在含有n个顶点的无向完全图中，一定存在 n(n-1)/2条边。 性质3：在含有n个顶点的有向完全图中，一定存在 n(n-1)条弧。 §2 图的基本操作 (1) CreateGraph(G)：图的创建操作。 初始条件：无。 操作结果：生成一个没有顶点的空图G。 (2) LocateVex(G,v)：顶点定位函数。 初始条件：G已经存在，v是一个顶点。 操作结果：返回v在G中的位置，若G中无此顶点，则返回“空”。 (3) FirstAdj(G,v)：求第一个邻接点函数。 初始条件：G已经存在，v是G中某个顶点。 操作结果：返回v的第一个邻接点，若v在G中无邻接点，则返回“空”。 (4) NextAdj(G,v,w)：求下一个邻接点函数。 初始条件：G已经存在，v是G中某个顶点，w是v的一个邻接点。 操作结果：返回v的邻接点中w之后的下一个邻接点，若无下一邻接点， 则返回“空”。 (5) getVexVal(G,v)：取顶点元素值函数。 初始条件：G已经存在，v是G中某个顶点。 操作结果：返回v的值。 (6) Updatevex(G,v,e)：修改顶点元素操作。 初始条件：G已经存在，v是G中某个顶点。 操作结果：将v的元素值改为e。 (7) AddVex(G,v)：增加顶点操作。 初始条件：G已经存在，且G中不存在顶点v。 操作结果：在G中增加一个新顶点v。 (8) deletevex(G,v)：删除顶点操作。 初始条件：G已经存在，v是G中某个顶点。 操作结果：从G中删除顶点v以及与v相关的弧或边。 (9) AddArc(G,arc)：增加弧（或边）操作。 初始条件：G已经存在，arc是一条弧（或边）。 操作结果：在G中增加一条弧（或边）arc。 (10) deleteArc(G,v,w): 删除弧（或边）操作。 初始条件：G已经存在，v,w是G中的两个顶点。 操作结果：从G中删除弧v,w，若G为无向图，则删除边(v,w)。 (11) destoryG(G)：撤消图操作。 初始条件：G已经存在。 操作结果：将图G清除。 (12) TraverseGraph (G，v)：遍历图操作。 初始条件：G已经存在，v是指定的起始顶点。 操作结果：按照某种规则将图G的每个顶点进行遍历。 §3 图的存储结构 由于图是一种非线性数据结构，任何两个顶点之间都可能存在关系，它比树形非线性结构更为复杂，因而图的存储方法也很多。具体选择哪一个更为合适，取决于具体的应用和对图的操作。但无论采用什么存储方法，目标总是相同的，即不仅要存储图中各个顶点的信息，同时还要存储顶点与顶点之间的所有关系（包括弧或边的信息）。 下面介绍几种不同的存储方法。 一、邻接矩阵存储方法 对于具有n个顶点的图，每个顶点的数据信息可以用一个长度为一维数组vexs[n]来存储，顶点之间的关系信息，可以用一个二维数组A[n][n]来存储，我们称这个二维数组为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标来代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间的关系信息，于是对于无权图的邻接矩阵可定义为： 如下图(a)是一个有向图G1，下图(b)是一个无向图G2，对应的邻接矩阵表示分别为： 如下图是一个带权有向图G3，对应的邻接矩阵表示分别为： 从图