数据结构_图 (1)

数据结构图LinkedData的支持网站(出处：wikipedia)例1设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少.已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213使用不同时间设备所需维修费为：使用年限0－11－22－33－44－5维修费568111822304159233041223123v1v2v3v4v5v616161717187图的基本概念１、图：由结点集合及结点间的关系集合组成的一种数据结构。v1v2v3v5v4v4v1v2v3v42、有向图：图中的每条边都是有方向的，G＝(V,{A})；３、无向图：图中的每条边都是无方向的，G＝(V,{E})；４、完全图：图任意两个顶点都有一条边相连接；若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图(a)无向图(b)有向图(c)无向完全图(d)有向完全图123412347.1图的定义和术语85、子图：设有两个图G1＝(V1,{E1})和G2＝(V2,{E2})。若V2V1且E2E1,则称图G2是图G1的子图。7.1图的定义和术语96、带权图：指边上带权的图。其中权是指每条边标上具有与该边相关的数据信息。８、简单路径：路径上各顶点v1,v2,...,vm均不互相重复。９、回路：若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。７、路径：在无向图中,若从顶点vi出发,沿一些边经过一顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vi,vp1,vp2,…,vpm,vj)为从顶点vi到顶点vj的路径。（有向图，路径是有向的）路径长度：非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。7.1图的定义和术语1010、连通图：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。7.1图的定义和术语1111、强连通图：在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。7.1图的定义和术语1212、生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。14、结点的度：结点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,结点的度等于该结点的入度与出度之和。其中结点v的入度是以v为终点的有向边的条数,记作ID(v);结点v的出度是以v为始点的有向边的条数,记作OD(v)。如果有e条边或弧，有n各结点，满足如下关系：13、邻接结点：对于无向图，若(u,v)是G中的一条边，则称u与v互为邻接结点。7.1图的定义和术语弧尾弧头7.2图的存储结构7.2图的存储结构1、数组表示法2、邻接表3、十字链表7.2图的存储结构1、数组表示法2、邻接表3、十字链表需存放n个定点信息，和n2个弧信息的存储量对于无向图来说：7.2图的存储结构1、数组表示法2、邻接表3、十字链表7.2图的存储结构（v1v2v3v4v5）v1v2v3v4v5分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度＝第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。顶点表：V=例1、无向图的邻接矩阵如何表示？v1v2v3v5v4v4A0101010101010111010101110邻接矩阵：A=7.2图的存储结构例2：有向图的邻接矩阵如何表示？分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点vi的出度=第i行元素之和，OD(vi)=A[i][j]顶点vi的入度=第i列元素之和。ID(vi)=A[j][i]顶点的度=第i行元素之和+第i列元素之和,即：TD(vi)=OD(vi)+ID(vi)v1v2v3v4A邻接矩阵：A=(v1v2v3v4)v1v2v3v4注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度）；第i列含义：以结点vi为头的弧(即入度）。顶点表：01100000000110007.2图的存储结构容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。例3：有权图（即网络）的邻接矩阵如何表示？v1v2v3v4Av5v65489755613以有向网为例：邻接矩阵：A=(v1v2v3v4v5v6)邻接矩阵法优点：邻接矩阵法缺点：顶点表：∞5∞7∞∞∞∞4∞∞∞8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞3∞∞∞1∞v1v2v3v4v5v6对稀疏图而言尤其浪费空间。7.2图的存储结构1、数组表示法2、邻接表3、十字链表分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。2、邻接表存储法的特点：分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。—它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？邻接表的缺点：邻接表的优点：TD(Vi)=单链表中链接的结点个数空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。7.2图的存储结构邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2)7.2图的存储结构7.2图的存储结构1、数组表示法2、邻接表3、十字链表