cms网站如何修改,做h5页面的网站蘑菇,网站开发的经济可行性分析,阿里巴巴国际站外贸流程序言 1对1的线性结构#xff0c;一对多的树二叉树以及森林#xff0c;第3种就是多对多的结构#xff0c;也就是我们所要讲到的图的结构#xff0c;图形结构是数据结构当中最复杂的一种结构#xff0c;图形结构的特点就是在这个图当中任意两点之间都会有关系#xff0c;这…序言 1对1的线性结构一对多的树二叉树以及森林第3种就是多对多的结构也就是我们所要讲到的图的结构图形结构是数据结构当中最复杂的一种结构图形结构的特点就是在这个图当中任意两点之间都会有关系这里的关系指的是可能会有关系因为不是一对多也不是1对1所以没有办法区分层次和顺序了图上的顶点与顶点之间我们可以认作是平等的那我们如何去描述图形结构 在这里我们会提到两个概念一个是顶点集一个是弧集在这里要区分弧跟边儿的概念 对于前面1对1和一对多的关系我们是可以用数据来进行描述它们之间的关系的也很方便找到他们的前驱和后继1对1或者是一对多的关系他们之间的数据与数据之间都有一定的关系找到某一个数据之后另外的数据就可以根据前一个数据进行推导出来和我们现在所提到的图的结构是有区别的图的结构在描述数据与数据之间的关系时所采用的描述方式包括了边儿边儿的方向决定了数据与数据之间存在怎样的关系那为什么说描述不了图形之间的关系因为图形当中点和点之间的关系是不确定的他们没有一个确定的关系并不像树形结构一样可以看作是一个家族家族之间存在血缘关系但是对于图来说点和点之间是没有血缘关系的 【1】根据图形结构我们能够想到哪些个东西 图形结构就是把没有关系的点和点之间通过一些个辅助条件转化成为一种有关系的结构只有当辅助条件相当多的时候我们才能够描述出图形之间点和点之间各种数据关系 【2】图的概念 图是有一个顶点及V和一个弧集R构成的数据结构 弧描述了点与点之间的关系是一条有效线段起点为弧尾终点为弧头 有向图此时a和b之间的关系是不相等的是对于有象图来说的因为有象图包含弧也就是包含一条有向线段 无向图 先提出的弧的概念有弧推广得到的边的概念若一根弧正向属于弧反过来也属于弧那么我们就概括为边的概念 【1】相等如果两个点之间存在边那么我们就认为这两个点之间的关系是平级的 相关术语 nlogn是我们人为规定的我们根据需要来进行规定拿些我们可以认为是稀疏图哪些我们认为是稠密的图都是我们自己决定的我们注意关联是三者之间的一种关系而不是点与点之间的一种关系要包括他们之间的边 我们在讲哈弗曼树的时候提到过路径的概念简单回路是由简单路径组成的不能出现重复的点----简单回路是在简单路径中提出来的具有基础性质判断联通图的方法 点与点之间是有一条或多条边连接在一起的不能够单独拆开如果拆开了那就是联通分量 对于有向图来说若任意两个顶点之间都存在一条有向路径那么称此有向图为强连通图简单的来说就是有出度和入度
图的生成树
先说一种思想 复杂的东西我们要往简单的方向考虑这样我们的编码生活才会更加的简单-----复杂的东西简单化但是我们解决复杂的东西我们要找到对应的关系就像是我们想要马拉松比赛那么我们可以找到每一段对应的终点将复杂的问题简单化 生成树是什么 首先我们要知道生成树是原图的一个子图此图的特性是包含原图的所有顶点以及其中的n-1条边这n-1条边是从原来的一条边开始进行寻找通过n-1条边能够将原来的所有顶点连接到一起形成一个连通子图所谓的联通就是没有孤立的点 问题用到哪些特性了 如果我们将n个顶点用n-1条边连接起来要把它作为联通的图就一定不会出现回路基本可以肯定的是他是一个树形结构不会存在圈儿到每一个点有唯一一条线与它连接因此引出了树形结构我们的树形结构从下向上看除了根节点每一个顶点都有唯一一个指针指向他我们试想一下我们有5个点如果我们用4条边将5个点连接在一起那么就不会出现回路的情况三角形是有三个顶点三条边正方形是有4个顶点4条边当边与顶点的数值相同的时候才会出现回路 联通图才可以得到生成树
图的存储表示
我们知道存储结构有两大类一类是顺序结构一类是链式结构但是对于简单的顺序结构以及链式结构是不能够满足图的存储使用的需要在此基础上做出一些改变图的邻接矩阵表示总结以下特点 【1】对于无向图来说邻接矩阵就是对称的因为我们的线段是从两个方向同时指出来的那么我们就需要记录两个1因此我们应该想到的是前面提到的三角矩阵 计算 有向图的邻接矩阵不一定是对称矩阵我们如何计算顶点的出度以及入度 首先我们应该找到节点所在的行行上面的1代表的就是出度列代表的是入度总的度我们用出度加上入度来进行表示就可以了 图上的矩阵数据表示的是边或者弧而不是表示的节点问题因此我们在进行结点的删除以及添加的时候我们还是不方便的原因是我们使用的是线性结构而不是链式结构因此下面我们将要介绍的就是链式结构有向图是分为两种的一种是正向的后面的连接是从小到大的另外一种是反向的对应的链接表时从大到小进行连接的
