精华内容
下载资源
问答
  • 文章目录矢量空间数据结构实体数据结构/spaghetti数据结构拓扑空间数据结构索引式拓扑空间数据结构双重独立编码结构/DIME(Dual Independent Map Encoding)码链式双重独立编码 矢量空间数据结构 矢量数据结构对...

    在知识传播途中,向涉及到的相关著作权人谨致谢意!

    【有种说法】矢量数据的实质还是栅格数据

    1. 计算机中的数据本身就是对连续现实世界的离散表达。矢量数据在计算机存储和显示中的空间分辨率非常大,但受到计算机存储性能的限制,矢量数据也有小数点维数,即矢量数据的离散的空间坐标,这就和栅格数据在计算机中是离散的类型数据一样
    2. 矢量数据在计算机的存储中也是由一个个很小的像素点组成,这样才能组成计算机能处理识别的二值信息
    3. 矢量数据的本质是二值化的栅格数据,其实是一种理想化的栅格数据

    矢量空间数据结构

    【矢量数据结构】对矢量数据模型进行数据的组织

    【优点】

    1. 它通过记录实体坐标及其关系,尽可能精确地表示点、线、多边形等地理实体
    2. 具有精度高、存储空间小等特点,是一种高效的图形数据结构
    3. 允许任意位置、长度和面积的精确定义

    【具体方法】几何图形及其关系用关系文件方式组织

    • 几何图形及其关系用文件方式组织
    • 属性数据通常采用关系型文件记录
    • 两者通过实体标识符连接

    在这里插入图片描述

    【分类】矢量数据结构是否明确表示地理实体间的空间关系分为实体数据结构、拓扑数据结构

    实体数据结构/spaghetti数据结构

    【实体数据结构】构成多边形边界的各个线段,以多边形为单位进行组织,对点、线、面都单独编码并记录坐标的一种数据结构

    【优点】编码容易、数字化操作简单和数据编排直观

    【缺点】

    • 相邻多边形的公共边界要被数字化和存储两遍,节点在数据库中被多次记录,不仅造成数据冗余,还容易造成数据的不一致,引起严重的匹配误差,可能导致输出的公共边界出现间隙或重叠
    • 每个多边形自成体系,缺少多边形的邻域信息和图形的拓扑关系
    • 岛只作为一个单图形,没有建立与外界多边形的联系
    • 难以检查多边形边界的拓扑关系正确与否,如是否存在间隙、重叠、不完整的多边形(死点)或拓扑学上不能接受的环(奇异多边形)等问题

    【具体实现】

    1. 方法1:点数据文件(点号、XY坐标)+多边形数据文件(多边形ID、点号串、类别码)
    2. 方法2:点数据文件(点号、XY坐标)+多边形数据文件(多边形ID、坐标串、类别码)

    在这里插入图片描述

    在这里插入图片描述

    拓扑空间数据结构

    【拓扑空间数据结构】描述对象域周边对象关系特征的数据结构

    【类型】拓扑空间数据结构没有固定的格式,还没有形成标准,但基本原理相同

    • 索引式
    • 双重独立编码结构DIME
    • 链状双重独立编码结构

    【共同的特点】

    • 点是相互独立的,点连成线,线构成面;
    • 每条线始于起始结点,止于终止结点,并与左右多边形相邻接

    索引式拓扑空间数据结构

    【索引式结构】采用树状索引以减少数据冗余并间接增加邻域信息
    【思想】将点、线、面看成三个层次,面由线构成、线由点构成,形成树状索引。坐标只存储点的XY,一条线对应n个点的ID集,一个多边形对应n个线的ID集
    【具体方法】对所有边界点进行数字化 --> 将坐标对以顺序方式存储 --> 由点索引与边界线号相联系,以线索引与各多边形相联系,形成树状索引结构

    【优点】

    1. 树状索引结构消除了相邻多边形边界的数据冗余和不一致问题
    2. 在简化过于复杂的边界线或合并多边形时刻不必改造索引表,邻域信息和岛状信息

    【缺点】两个编码表都要以人工方式建立,工作量大且容易出错

    【文件】点文件(点ID、XY坐标)+线文件(边ID、组成该边的点ID集合)+多边形文件(多边形ID、组成该多边形的边ID集合)
    在这里插入图片描述
    在这里插入图片描述

    双重独立编码结构/DIME(Dual Independent Map Encoding)码

    【背景】这种数据结构最早是由美国人口统计系统采用的一种编码方式

    【DIME】它对图上网状或面状要素的任何一条线段,用其两端的节点及相邻多边形予以定义,组成一个弧段文件

    【优点】通过双重独立编码可以检查数据,并自动形成面文件
    【缺点】由于美国的行政边界是条直线,此编码结构的直线只表示两端点 --> 只能用直线两端点的序号及相邻的多边形来表示
    【文件组织】线文件:线号+左多边形+右多边形+起点+终点

    在这里插入图片描述

    链式双重独立编码

    1. what:多边形文件+弧段文件+弧段坐标文件+节点文件
    2. what:链式双重独立式数据结构是DIME数据结构的一种改进

    【DIME】在DIME中,一条边只能用直线两端点的序号及相邻的多边形来表示
    【链状数据】

    1. 在链状数据结构中,将多个直线段看成一个弧段(或链段),每个弧段可以有许多中间点
    2. 而弧段代替了DIME中的直线,使链式双重独立编码能够存储多结点的直线

    【数据结构】

    1. 【组织方法一】结点文件(结点号、XY坐标、连接的弧段)+弧段点文件(弧段ID、点号集)+弧段文件(弧段ID、起始点、终结点、左多边形、右多边形)+多边形文件(多边形ID、弧段号的集合、其他属性列)
    2. 【组织方法二】弧段坐标文件(弧段ID、坐标串)+弧段拓扑文件(弧段ID、起始点、终结点、左多边形ID、右多边形ID)、多边形拓扑文件(多边形ID、弧段号的集合、属性)
      没有结点文件,XY坐标以坐标串的形式存储在弧段坐标文件

    链式双重独立编码1
    链式双重独立编码2

    展开全文
  • 学GIS空间数据库的时候,拓扑方面内容笔记 拓扑的定义 拓扑是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的一个学科。它只考虑物体间的位置关系而不...表示点和线之间关系的图被称为拓扑结构图。拓...

    GIS空间数据库的时候,拓扑方面内容笔记

    拓扑的定义

    拓扑是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的一个学科。它只考虑物体间的位置关系而不考虑它们的形状和大小

    “拓扑”就是把实体抽象成与其大小、形状无关的“点”,而把连接实体的线路抽象成“线”,进而以图的形式来表示这些点与线之间关系的方法,其目的在于研究这些点、线之间的相连关系。表示点和线之间关系的图被称为拓扑结构图。拓扑结构与几何结构属于两个不同的数学概念。在几何结构中, 我们要考察的是点、线、面之间的位置关系,或者说几何结构强调的是点与线所构成的形状及大小。如梯形、正方形、平行四边形及圆都属于不同的几何结构,但从拓扑结构的角度去看,由于点、线间的连接关系相同,从而具有相同的拓扑结构即环型结构。也就是说,不同的几何结构可能具有相同的拓扑结构。 

    如三角形变成四边形、原型、环形,角度、长度、面积、形状等等都很可能发生变化。此时,不必考虑它们的形状和大小(如长度、面积、形状等等这些),只考虑物体间的位置、结构关系,只专注于在连续改变形状后还能保持不变的一些性质(如他们都是一个圈),这就是拓扑学。

    拓扑学历史

    拓扑英文名是Topology,直译是地志学,最早指研究地形、地貌相类似的有关学科。

    几何拓扑学是十九世纪形成的一门数学分支,它属于几何学的范畴。有关拓扑学的一些内容早在十八世纪就出现了。那时候发现的一些孤立的问题,在后来的拓扑学的形成中占着重要的地位。

    • 1679年德国数学家莱布尼茨提出的名词 拓扑学,起初叫形势分析学,他在17世纪提出“位置的几何学”(geometria situs)和“位相分析”(analysis situs)的说法。

    • 1736年欧拉在解决了七桥问题,给当时数学界引起很多思考;

    • 1750年欧拉在发表了多面体公式;

    • 1833年高斯在电动力学中用线积分定义了空间中两条封闭曲线的环绕数。

    • 1847年 J.B.利斯廷根据希腊文τπο和λγο(“位置”和“研究”),提出Topology这一数学名词,即拓扑学。Topology,直译是地志学,最早指研究地形、地貌相类似的有关学科。

    • 1851年左右,即19世纪中期,德国数学家黎曼在复变函数的研究中提出了黎曼面的几何概念,并且强调为了研究函数、研究积分,就必须研究形势分析学,从此数学界开始了现代拓扑学的系统研究。

     

     

    不同学科对拓扑的定义不尽相同

    集合拓扑:拓扑是集合上定义的一种结构

    点集拓扑学

    点集拓扑学(Point Set Topology),有时也被称为一般拓扑学(General Topology),是数学的拓扑学的一个分支。

    它研究拓扑空间以及定义在其上的数学结构的基本性质。这一分支起源于以下几个领域:对实数轴上点集的细致研究,流形的概念,度量空间的概念,以及早期的泛函分析。

    点集拓扑学定义

    拓扑是一个包含一个集合X连同和X的子集族Σ(称为开集系)的二元组(X,Σ),它满足如下三个公理:

    1. 开集的并集是开集。

    2. 有限个开集的交集是开集。

    3. X和空集∅是开集。

    设T为非空集X的子集族。若T满足以下条件:

    1. X与空集都属于T;

    2. T中任意两个成员的交属于T;

    3. T中任意多个成员的并属于T; 则T称为X上的一个拓扑。具有拓扑T的集合X称为拓扑空间,记为(X,T)。

    也等价于:

    • X和空集都属于T;

    • T中任意多个成员的并集仍在T中;

    • T中有限多个成员的交集仍在T中。

    此时称称T中的成员为这个拓扑空间的开集。最普通的例子便是实数集上的距离拓扑,这与我们通常对实数的认识相同。最简单(粗)的拓扑为平凡拓扑,它只包含T本身和空集,最复杂(细)的拓扑的构成开集为T的所有子集。

    同一个集合X,若指定不同的拓扑,则构造出不同的拓扑空间。凡属于X的子集称为X的一个关于T的开子集,即开集。开子集关于全集的补集,称为闭子集,即闭集。一个集合是不是开/闭子集,取决于拓扑的指定。由定义,X本身和空集是既开又闭的子集。

    v2-660c6aad53a19b48bfe90c0dcfabf5f2_hd.jpg

    本质上,拓扑就是要给一个集合指定一个几何结构,然后这个集合就成了一个我们可以研究的空间。比如,有了拓扑和开集的定义后,我们就可以摆脱大一数学分析的ε-δ来给出更一般的连续性定义:设A和B是两个拓扑空间,A到B的映射f称为连续的,若任何B的开集在f下的原象是A的开集。这样我们对于函数的研究将不再局限于实数,而是搬到更一般的拓扑空间内了。

     

     

     

    平面拓扑关系

    对于一般的拓扑关系,一图概括如下

    拓扑关系图

    Egenhofer和Franzosa在1991年共同撰写的论文Point-Set Topological Spatial Relations,为空间拓扑(九交模型)奠定了重要基础。

    依据集合论,作者对于点集拓扑空间定义了以下基本概念,以描述空间对象:

    • Interior(内部) [公式] :对于 [公式] , interior指的是所有包含 [公式] 的开放集合的并集。对于空间对象,可以认为是空间对象的内部。

    • Closure(闭包) [公式] :对于 [公式] , closure指的是所有包含 [公式] 的闭集合的交集。对于空间对象,可以认为是空间对象整体。

    • Boundary(边界) [公式] :对于 [公式] , boundary指的是Y的闭包与Y的补集的闭包的交集,即 [公式] 。对于空间对象,可以认为是空间对象的边界。

    简而言之,一个空间对象可定义为由内部+边界构成。

    根据以上三条定义可知以下两命题:

    1. [公式] 。即:内部和边界的交集为空。

    2. [公式] 。即:内部和边界的并集为整个对象。

    九交模型

    在一个平面R2上,两个对象A和B之间的二元拓扑关系要基于以下的相交情况:A的内部(A°)、边界(αA)和外部(A-)与B的内部(B°)、边界(αB)和外部(B-)之间的交。

     

    考虑取值有空(0)和非空(1),可以确定有256种二元拓扑关系。对于嵌在R2中的二维区域,有八个关系是可实现的,并且它们彼此互斥且完全覆盖。这些关系为:相离(disjoint)、相接(meet)、交叠(overlap)、相等(equal)、包含(contain)、在内部(inside)、覆盖(cover)和被覆盖(covered by)。

    九交模型

    三维空间拓扑关系

    • 点-点空间关系2种:相离、相等;

    • 点-线空间关系3种:相离、相接、包含于;

    • 点-面空间关系3种:相离、相接、包含于;

    • 点-体空间关系3种:相离、相接、包含于;

    • 线-线空间关系7种:相离、相交、交叠、相等、相接、包含于、包含;

    • 线-面空间关系5种:相离、相接、进入、穿越、包含于;

    • 线-体空间关系5种:相离、相接、进入、穿越、包含于;

    • 面-面空间关系10种:相离、相接、交叠、相等、包含于、包含、覆盖、被覆盖、穿越、被穿越;

    • 面-体空间关系8种:相离、相接、交叠、进入、包含于、包含、穿越、被穿越;

    • 体-体空间关系8种:相离、相接、进入、相等、包含于、包含、穿越、被穿越。

    基本空间拓扑关系的计算

    点与直线的关系计算

    直线方程:

    Ax+By+C=0

    A=y1-y2,

    B=x1-x2,

    C=y2x1-y1x2

    令S=Axi+Byi+C

    • 当S<0 点在顺时针方向上;

    • 当S=0 点在直线上;

    • 当S<0 点在逆指针方向上。

    两条直线关系的计算

    直线方程:

    Ax+By+C=0

    Ex+Fy+G=0

    当FA-EB=0时,两条直线的交点不存在;否则,交点坐标为:

    xi=(GB-FC)/(FA-EB)

    yi=(CE-AG)/(FA-EB)

     

    空间目标之间的拓扑关系推理

    两条线的直线段之间基本空间拓扑关系的推理

    点与其他类型空间目标之间的拓扑关系决策树

    线与面之间的全域空间拓扑关系决策树

    面与面之间的全域空间拓扑关系基本类型的决策树

     

    空间度量关系

    度量关系是在欧氏空间(Euclidean Space)(Blumenthal,1970)和度量空间(Metric Space)(Dhage,1992)上进行的操作,它是一切空间数据定量化的基础。它包含长度、周长、面积、距离等定量的度量关系,其中最主要的度量空间关系是空间对象之间的距离关系。

    欧几里德距离定义如下(Kolountzakis and Kutulakos,1992):

    曼哈顿距离是两点在南北方向上的距离加在东西方向上的距离(Wu et al.,1987),即:

    空间顺序关系及描述方法

    锥形模型

    每区域赋予东、南、西和北,为得到更精确的方向关系可对其再进行细分得8或16方向。

    最小外接矩形模型

     

    该模型通过延伸目标的MBR的边,将空间划分为9个区域,分别表示为北、东北、东、东南、南、西南、西、西北和目标MBR所在的中心方向。

    Freksa-Zimmermann模型

    以直线段为参考的定性空间方向模型:以直线为空间参考目标,把二维空间分解为15个方向区域。

    以点为参考目标的基本空间方向

    点A与点B的空间方向关系可以用向量AB与正北方向的夹角(顺时针)来描述。

    以直线为参考目标的基本空间方向

    点与线或面之间的空间方向关系

    线与点、线或面之间的空间方向计算与描述

    面与点、线、面之间的空间方向关系计算与描述

    • 点与点之间距离&点与线之间距离:dPL(P,L)=min{d1,d2,…dn}

    • 线与线之间的距离:d(L1,L2)=min{d(P1,P2)|P1∈L1,P2 ∈L2}

    • 点与面之间的距离:

      • “中心距离”是点P与面A中几何中心或者重心之间的距离,

      • “最小距离”是指点P与面A中所有点之间距离的最小值,

      • “最大距离”是指点P与面A中所有点之间距离的最大值。

    • 面与面之间的距离

      • “中心距离”是指两个面状物体的质心之间的距离;

      • “最小距离”是指面A1中的点P1与A2中的点P2之间的距离的最小值;

      • “最大距离”是指面A1中的点P1与A2中的点P2之间的距离的最大值。

      • (a) 点A与点B之间的空间方向关系。

      • (b)点A与直线BC之间的空间方向关系,以角平分线L的方位表示。

      • (c) 用两条直线的中点代表代表其方位。

      • (a) 直线AB和直线CD的方向可用向量EF(E和F分别为两直线的中点)来描述。

      • (b)直线AB和点C的方向关系。

      • (c) 划分直线段AB的方向片,点C相对直线AB的关系可描述为点C在直线AB的哪个方向片中。

      • (d)直线AB和直线CD的方向可用向量EF(E和F分别为两直线的中点)来描述,或用向量ED和向量EC来定义。

      • (a) 方向线PS和PE定义了点A与线L之间的全域空间方向关系,点A与P1、P2、P3(中点)的连线定义了点A与不同直线段的局域空间方向关系。

      • (b)方向线PS和PE重和,说明点A被线L包围,这是全域空间方向关系,点A与P1、P2、P3、P4(中点)的连线定义了点A与不同直线段的局域空间方向关系。

      • (c)方向线PS和PE定义了点A与面B之间的全域空间方向关系,用方向线P1、P2把面域B分为3部分,每部分可以用该锥形的角平分线描述方向关系,这3部分的面积与面积B的总面积之比分别为B1、B2、B3。也可以用该锥形的每个角平分线在面内的长度与角平分线在面内的总长度之比L1、L2、L3来表示。

      • (d)方向线PS和PE重和,说明点A被面B包围,这是全域空间方向关系,面域不同和点A之间的局域空间方向关系描述方法与(c)同。

      • (a) 线ABCD与点E之间的全域空间方向关系为“相同”,直线段AB与点E之间的局域空间方向关系为“西”。

      • (b) 反映线与线之间的全域空间方向关系,直线段AB与线L2的每条直线段和线的任意子集之间都有局域空间方向关系。

      • (c) 线与面的全域空间方向关系和局域空间方向关系均可象(b)一样计算和描述。

      • (a) 面P与点C之间的全域空间方向关系为“相同”,面P的直线AB与点C之间的局域空间方向关系为“北”。

      • (b) 面P与直线EFG之间的全域空间方向关系和局域空间方向关系如图所示,前者为“东”、“相同”和“南”,而后者为“东”。

      • (c) 把区域栅格化,判断子区域与源目标的全域空间方向关系和局域空间方向关系。

     

    转载本站文章《代数拓扑\集合拓扑\代数拓扑\拓扑关系\拓扑结构_笔记》, 请注明出处:https://www.zhoulujun.cn/html/theory/math/2019_0929_8164.html

    展开全文
  • 数据结构 - 拓扑排序

    千次阅读 2015-05-03 09:23:01
    学生应按怎样的顺序学习这些课程,才能无矛盾、顺利地完成学业——拓扑排序 拓扑序列是有向无环图中各顶点构成的有序序列。该序列满足如下条件:如果图中一顶点vi到另一顶点vj存在一条路径,那么vj在此图的拓扑排序...

    应用背景

    学生选修课程问题
    顶点——表示课程
    有向弧——表示先决条件,若课程i是课程j的先决条件,则图中有弧(i,j)
    学生应按怎样的顺序学习这些课程,才能无矛盾、顺利地完成学业——拓扑排序

         拓扑序列是有向无环图中各顶点构成的有序序列。该序列满足如下条件:如果图中一顶点vi到另一顶点vj存在一条路径,那么vj在此图的拓扑排序序列中位于vi之后。
    

    有向无环图(DAG)和 AOV网

    有向无环图”(Directed Acyclic Graph,简称DAG
    AOV网 (Activity On Vertex network): 一个“可行的” AOV 网络必须是DAG。否则图中有回路,从而就不能确定回路中的活动究竟哪个先实施。
    顶点表示活动,
    弧表示活动间的优先关系,
    注意:
    AOV网中的弧表示活动之间存在某种制约关系:若

    void ToplogicalSort ( Graph G, int TopNum[ ] )
    {
        int Counter;    /* 拓扑序号,用以标识每个顶点输出的次序*/
        int v, w;
        int *InDegree = (int *)malloc( G.n * sizeof(int) );
        GetInDegree(G, InDegree);   /* 计算图G中各顶点的入度 */
        for( Counter = 0; Counter < G.n; Counter++ ) {
            v = FindNewVertexOfDegreeZero( );   
            /* 查找入度为0的顶点,若找到,则返回顶点在顶点数组的下标。若找不到入度为0的顶点,返回-1 */
            if ( v == -1 ) {
                 printf( “图存在环路”);
                 break;
            }
            TopNum[v] = Counter;
            for( G中关于v 的每个邻接点w )
               Indegree[w]--;  /* 与顶点v相连的各顶点的入度减1 */
        }
    }
    
    void ToplogicalSort ( GraphAdjList GL, int * TopNum )
    {    
        Queue queue;    EdgeNode *p;     int Counter = 0;    int v, w;
         //int *InDegree = (int *)malloc( G.n * sizeof(int) );
       //  GetInDegree(G, InDegree);   /* 计算图G中各顶点的入度 */
         queue = InitQueue( GL->numVertexes ); /* 创建空队列 */
         for( v = 0; v <GL->numVertexes; v++ )
              if( GL->adjList[v].in==0 )        EnQueue( &queue, v );
         while( ! QueueEmpty(queue) ) {
               v = DeQueue( &queue);
               TopNum[v] = ++Counter;      /* 赋顶点拓扑排序序号 */
               for( p=GL->adjList[v].firstedge;p!=NULL;p=p->next)
                  if( --GL->adjList[p->adjvex].in == 0 )
                      EnQueue( &queue, p->adjvex );
          }
          if( Counter != GL->numVertexes )      
              printf( "图存在环路\n" );
          DisposeQueue(&queue);    /* 释放队列空间*/
          //free(InDegree);
    }
    

    关键路径

        与AOV网相对应的是AOE(Activity On Edge) ,是边表示活动的有向无环图。
        顶点表示事件(Event),每个事件表示在它之前的活动已完成,在它之后的活动可以开始;
        弧表示活动,弧上的权值表示相应活动所需的时间或费用

    AOV网与AOE网

    拓扑排序主要是为解决一个工程能否顺利进行的问题。
    关键路径是解决工程完成需要的最短时间问题。
    AOV网与AOE网的区别:
    AOV网,顶点表示活动,边描述活动之间的制约关系
    AOE网,边上的权值表示活动持续的时间,
    建立在活动之间制约关系没有矛盾的基础上,
    讨论完成整个工程至少需要多少时间;或者为缩短完成工程所需时间,应当加快哪些活动等问题。

    路径长度—路径上各活动持续时间之和
    关键路径—从源点到汇点具有最大路径长度的路径
    关键活动—关键路径上的活动。关键活动是影响整个工程的关键,延迟就会影响整个工期的活动。
    最早发生时间—设v0是起点,从v0到vi的最长路径长度称为事件vi的最早发生时间,即是以vi为尾的所有活动的最早发生时间。

    求AOE中关键路径和关键活动

    ⑴ 算法思想
    ① 利用拓扑排序求出AOE网的一个拓扑序列;
    ② 从拓扑排序的序列的第一个顶点(源点)开始,按拓扑顺序依次计算每个事件的最早发生时间ve(i) ;
    从拓扑排序的序列的最后一个顶点(汇点)开始,按逆拓扑顺序依次计算每个事件的最晚发生时间vl(i) ;
    求出各活动的最早发生时间e(i)和最晚发生时间l(e),同时求出ai的时间余量,时间余量=0的那些活动就是关键活动。

    最短路径

    用带权的有向图表示一个交通运输网,图中:
    顶点:城市
    边:城市间的交通联系
    权:此线路的长度或沿此线路运输所花的时间或费用等
    问题:
    两地之间是否有通路?
    在有多条通路的情况下,哪条最短?
    将一条路径的起始顶点称为源点,最后一个顶点称为终点。

    单源点最短路径

    对于给定的有向图G=(V,E)及单个源点V0,求V0到G的其余各顶点的最短路径。
    针对单源点的最短路径问题,Dijkstra提出了一种按路径长度递增次序产生最短路径的算法,即迪杰斯特拉(Dijkstra)算法。
    

    求最短路径步骤

    初使时令 S={V0},T={其余顶点},T中顶点对应的距离值
    若存在 V0,Vi,为V0,Vi弧上的权值
    若不存在 V0, Vi,为
    从T中选取一个其距离值为最小的顶点W,加入S
    对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值比不加W的路径要短,则修改此距离值
    重复上述步骤,直到S中包含所有顶点,即S=V为止

    算法实现
    图用带权邻接矩阵存储
    数组dist[ ]存放当前找到的从源点V0到每个终点的最短路径长度(这些路径中间只经过集合S中的顶点),其初态为图中直接路径权值
    数组pre[ ]表示从V0到各终点的最短路径上,此顶点的前一顶点的序号;若从V0到某终点无路径,则用0作为其前一顶点的序号

    展开全文
  • 什么是拓扑结构_拓扑结构

    万次阅读 多人点赞 2018-09-09 09:17:01
    什么是拓扑结构?  首先我们来解释一下拓扑的含义,所谓“拓扑”...表示点和线之间关系的图被称为拓扑结构图。拓扑结构与几何结构属于两个不同的数学概念。在几何结构中,  我们要考察的是点、线之间的位置关系...

    什么是拓扑结构?
      首先我们来解释一下拓扑的含义,所谓“拓扑”就是把实体抽象成与其大小、形状无关的“点”,而把连接实体的线路抽象成“线”,进而以图的形式来表示这些点与线之间关系的方法,其目的在于研究这些点、线之间的相连关系。表示点和线之间关系的图被称为拓扑结构图。拓扑结构与几何结构属于两个不同的数学概念。在几何结构中,
      我们要考察的是点、线之间的位置关系,或者说几何结构强调的是点与线所构成的形状及大小。如梯形、正方形、平行四边形及圆都属于不同的几何结构,但从拓扑结构的角度去看,由于点、线间的连接关系相同,从而具有相同的拓扑结构即环型结构。也就是说,不同的几何结构可能具有相同的拓扑结构。
      类似地,在计算机网络中,我们把计算机、终端、通信处理机等设备抽象成点,把连接这些设备的通信线路抽象成线,并将由这些点和线所构成的拓扑称为网络拓扑结构。
      网络拓扑结构反映出网络的结构关系,它对于网络的性能、可靠性以及建设管理成本等都有着重要的影响,因此网络拓扑结构的设计在整个网络设计中占有十分重要的地位,在网络构建时,网络拓常见的网络拓扑结构
      在计算机网络中常见的拓扑结构有总线型、星型、环型、树型和网状型等。
      1.总线型拓扑
    这里写图片描述
      如图1.4所示,总线型拓扑中采用单根传输线路作为传输介质,所有站点通过专门的连接器连到这个公共信道上,这个公共的信道称为总线。任何一个站点发送的数据都能通过总线传播,同时能被总线上的所有其他站点接收到。可见,总线型结构的网络是一种广播网络。扑结构往往是首先要考虑的因素之一。
      在总线结构中,总线有一定的负载能力,因此,总线长度有一定限制,一条总线也只能连接一定数量的结点。
      总线布局的特点是:结构简单灵活,非常便于扩充;可靠性高,网络响应速度快;设备量少、价格低、安装使用方便;共享资源能力强,极便于广播式工作即一个结点发送所有结点都可接收。总线型拓扑是基本局域网拓扑形式之一。
      在总线两端连接的器件称为端结器(末端阻抗匹配器、或终止器)。主要与总线进行阻抗匹配,最大限度吸收传送端部的能量,避免信号反射回总线产生不必要的干扰。
      总线形网络结构是目前使用最广泛的结构,也是最传统的一种主流网络结构,适合于信息管理系统、办公自动化系统领域的应用。
      2.星型拓扑
    这里写图片描述
      如图1.5所示,星型拓扑中有一个中心节点,其他各节点通过各自的线路与中心节点相连,形成辐射型结构。各节点间的通信必须通过中心节点的作用,如图A 到B 或A到C 都要经过中心节点D。
      星型拓扑的网络具有结构简单、易于建网和易于管理等特点。但这种结构要耗费大量的电缆,同时中心节点的故障会直接造成整个网络的瘫痪。星型拓扑也经常应用于局域网中。
      星型布局是以中央结点为中心与各结点连接而组成的,各结点与中央结点通过点与点方式连接,中央点执行集中式通信控制策略,因此中央结点相当复杂,负担也重。
      目前流行的PBX就是星型拓扑结构的典型实例,如图1.5(右)所示。
      以星型拓扑结构组网,其中任何两个站点要进行通信都必须经过中央结点控制。中
      央结点主要功能有
      1) 为需要通信的设备建立物理连接
      2) 为两台设备通信过程中维持这一通路
      3) 在完成通信或不成功时,拆除通道
      在文件服务器/工作站(File Server/Workstation )局域网模式中,中心点为文件服务器,存放共享资源。由于这种拓扑结构,中心点与多台工作站相连,为便于集中连线,目前多采用集线器(HUB)。
      星型拓扑结构特点:网络结构简单,便于管理、集中控制, 组网容易;网络延迟时间短,误码率低,网络共享能力较差,通信线路利用率不高,中央节点负担过重,可同时连双绞线、同轴电缆及光纤等多种媒介。
      树型拓扑结构可以看作成星型拓扑的一种扩展,也称扩展星型拓扑。
      3.环型拓扑
    这里写图片描述
      如图1.6 所示,在环型拓扑中,各节点和通信线路连接形成的一个闭合的环。在环路中,数据按照一个方向传输。发送端发出的数据,延环绕行一周后,回到发送端,由发送端将其从环上删除。我们可以看到任何一个节点发出的数据都可以被环上的其他节点接收到。
      环型拓扑具有结构简单,容易实现,传输时延确定以及路径选择简单等优点,但是,网络中的每一个节点或连接节点的通信线路都有可能成为网络可靠性的瓶颈。当网络中的任何一个节点出现故障都可能会造成网络的瘫痪。另外,在这种拓扑结构中,节点的加入和拆除过程比较复杂。环型拓扑也是局域网中常用的一种拓扑形式。
      环形网的特点是:信息在网络中沿固定方向流动,两个结点间仅有唯一的通路,大大简化了路径选择的控制;某个结点发生故障时,可以自动旁路,可靠性较高;由于信息是串行穿过多个结点环路接口,当结点过多时,影响传输效率,使网络响应时间变长。但当网络确定时,其延时固定,实时性强;由于环路封闭故扩充不方便。
      环形网也是微机局域网常用拓扑结构之一,适合信息处理系统和工厂自动化系统。1985年IBM公司推出的令牌环形网(IBM Token Ring)是其典范。在FDDI得以应用推广后,这种结构会进一步得到采用。
      4.网状拓扑
    这里写图片描述
      在网状拓扑结构中,节点之间的连接是任意的,每个节点都有多条线路与其他节点相连,这样使得节点之间存在多条路径可选,如图1.7中从A 到C 可以是A-B-C 也可以是A-D-B-C,在传输数据时可以灵活的选用空闲路径或者避开故障线路。
      可见网状拓扑可以充分、合理的使用网络资源,并且具有可靠性高的优点。我们知道,广域网覆盖面积大,传输距离长,网络的故障会给大量的用户带来严重的危害,因此在广域网中,为了提高网络的可靠性通常采用网状拓扑结构,如图1.7(右)所示为一个简单的广域网示意图。
      但是我们也应该看到,这个优点是以高投资和高复杂的管理为代价的。将多个子网或多个局域网连接起来构成网状型拓扑结构。在一个子网中,集线器、中继器将多个设备连接起来,而桥接器、路由器及网关则将子网连接起来。根据组网硬件不同,主要有三种网状型拓扑:
      网状网:在一个大的区域内,用无线通信连路连接一个大型网络时,网状网是最好的拓扑结构。通过路由器与路由器相连,可让网络选择一条最快的路径传送数据。
      主干网:通过桥接器与路由器把不同的子网或LAN 连接起来形成单个总线或环型拓扑结构,这种网通常采用光纤做主干线。
      星状相连网:利用一些叫做超级集线器的设备将网络连接起来,由于星型结构的特点,网络中任一处的故障都可容易查找并修复。应该指出,在实际组网中,拓扑结构不一定是单一的,通常是几种结构的混用。
    这里写图片描述
      比如,将总线型与星型结合起来就形成了总线型/星型拓扑结构,用一条或多条总线把多组设备连接起来,相连的每组设备呈星型分布。采用这种拓扑结构,用户很容易配置和重新配置网络设备。如图1.8 所示。

    展开全文
  • 数据结构---拓扑排序详解

    万次阅读 多人点赞 2017-03-06 19:54:41
    前言 The time of test,family is best. Name:Willam Time:2017/3/61、拓扑排序的介绍对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排... 拓扑排序对应施工的流程图具有特别重要
  • 数据结构图---拓扑结构

    千次阅读 2019-05-28 09:31:14
    数据结构图---拓扑结构 【1】拓扑排序 在一个表示工程的有向图中,有顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网。 AOV网中的弧表示活动之间存在的某种制约关系...
  • 常用数据结构图--拓扑排序

    千次阅读 2016-09-16 15:24:21
    图是十分重要的数据结构,常常被应用于实际生活的应用之中。生活中常见的问题例如交通路线图、任务指定分配、工期计算、航空网络等,都可以使用图相关的理论来建立模型。下面是《数据结构与算法分析》对图的若干定义...
  • 【1】拓扑排序 在一个表示工程的有向图中,有顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网。 AOV网中的弧表示活动之间存在的某种制约关系。 所谓拓扑排序,...
  • 数据结构与算法之拓扑排序

    千次阅读 2016-11-01 14:03:09
    假设我非常想学习一门机器学习的课程,但是在修这么课程之前,我们必须要学习一些基础课程,比如计算机科学概论,C语言程序设计,数据结构,算法等等。那么这个制定选修课程顺序的过程,实际上就是一个拓扑排序的...
  • 什么是拓扑结构?...表示点和线之间关系的图被称为拓扑结构图。拓扑结构与几何结构属于两个不同的数学概念。在几何结构中,  我们要考察的是点、线之间的位置关系,或者说几何结构强调的是点与线所构...
  • 拓扑结构和几何结构的区别

    千次阅读 2020-09-28 17:38:41
    最近在看数据结构中的图,里面有一节叫做拓扑排序,不是很明白这个“拓扑”是什么意思,上网搜了一下,有个说法如下,感觉比较通俗易懂。 所谓“拓扑”就是把实体抽象成与其大小、形状无关的“点”,而把连接实体的...
  • [GIS算法] 拓扑关系

    千次阅读 2020-03-24 14:27:20
    文章目录拓扑关系数据结构拓扑关系的自动建立弧段的预处理直线段相交的判断方法自相交弧段处理弧段相交打断处理结点匹配算法建立拓扑关系计算结点关联弧段的方位角,并按由小到大排序左转算法岛的判断 拓扑关系 「...
  • 拓扑结构

    千次阅读 2018-05-20 13:52:12
    转自:https://blog.csdn.net/starshinning975/article/details/53511343什么是拓扑结构? 首先我们来解释一下拓扑的含义,所谓“拓扑”就是把实体抽象成与其大小、...表示点和线之间关系的图被称为拓扑结构图。拓扑...
  • 数据结构--DAG拓扑排序

    千次阅读 2019-04-16 17:23:57
    在学习拓扑排序之前,应该已经掌握了图的两种遍历方式+堆栈、队列的特点。 此文的实现,我会用Java实现。 蓝色表示细节,红色表示重要。 二、拓扑排序概念 1.在图中有一个重要的有向图类型,(有向图的表示方法...
  • 1.拓扑排序 说了两个有环的图应用,现在我们来谈谈无环的图应用。在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网(Activity On Vertex ...
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能被计算机处理的...
  • 本文主要介绍了拓扑排序、关键路径、AOE、AOV的基本概念,拓扑排序和关键路径算法的思想,以及它们的实现。
  • GIS中的拓扑关系和ArcGIS中的拓扑

    千次阅读 2019-09-19 18:20:18
    GIS中的拓扑关系 ArcGIS中的拓扑 GIS中的拓扑关系 拓扑研究的是几何图形的一些性质,它们在图形被弯曲、拉大、缩小或任意的变形下保持不变。在变形过程中不使原来不同的点重合为同一个点,又不产生新点。拓扑有一...
  • 数据结构知识整理

    万次阅读 多人点赞 2018-07-30 18:50:47
    1.数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。 2.数据结构涵盖的内容: 3.基本概念和术语: 数据:对客观事物的符号表示,在计算机科学中是指所有能...
  • 超硬核!数据结构学霸笔记,考试面试吹牛就靠它

    万次阅读 多人点赞 2021-03-26 11:11:21
    上次发操作系统笔记,很快浏览上万,这次数据结构比上次硬核的多哦,同样的会发超硬核代码,关注吧。
  • 本文代码实现基本按照《数据结构》课本目录顺序,外加大量的复杂算法实现,一篇文章足够。能换你一个收藏了吧?
  • 拓扑图是从拓扑学引用的名称,拓扑学是几何学中一个分支,它是研究几何图形在连续改变形状时还能保留不变的一些特点,它只考虑物体之间的位置关系而不考虑它们的距离和大小。拓扑图也具有上述的特点。因此,有人称之...
  • 拓扑排序 一个无环的有向图称为无环图(Directed Acyclic Graph),简称DAG图。 在一个表示工程的有向图中,用顶点表示活动,用弧...拓扑序列:设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列V1,V2,……,Vn...
  • 拓扑结构的解释

    万次阅读 2018-03-15 21:31:27
    什么是拓扑结构?...表示点和线之间关系的图被称为拓扑结构图。拓扑结构与几何结构属于两个不同的数学概念。在几何结构中, 我们要考察的是点、线之间的位置关系,或者说几何结构强调的是点与线所构成的...
  • 计算机网络拓扑结构

    千次阅读 2017-03-10 22:16:58
    互联网时代已经到来了,下面学习啦小编为您科普一下网络相关基础知识《什么是拓扑结构》,让您更快融入互联网时代,希望对您有所帮助! 什么是拓扑结构?  首先我们来解释一下拓扑的含义,所谓“拓扑”就是把实体...
  • 星型拓扑 总线拓扑 ▪ 环型拓扑 ▪ 树型拓扑 ▪ 混合型拓 ▪ 网型拓扑 开关电源拓扑 简单介绍的: 星型 优点:可靠性高,方便管理,易于扩展,传输效率高 缺点:线路利用率低,中心节点需要很高的...
  • 拓扑排序 学了两个有环的图应用,现在我们来谈谈无环的图应用。无环,即是图中没有回路的意思。 拓扑排序介绍 在一个表示工作的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样有向图为顶点表示活动...
  • 拓扑结构

    千次阅读 2008-04-15 10:58:00
    网络拓扑是由网络节点设备和通信介质构成的网络结构图。在选择拓扑结构时,主要考虑的因素有:安装的相对难易程度、重新配置的难易程度、维护的相对难易程度、通信介质发生故障时,受到影响的设备的情况.一.基本术语...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,078
精华内容 14,031
关键字:

具有拓扑关系的数据结构是

数据结构 订阅