精华内容
下载资源
问答
  • 拓扑排序入门(真的很简单)

    万次阅读 多人点赞 2018-06-25 19:15:30
    在一个有向图中,对所有的节点...如果最后不存在入度为0的节点,那就说明有环,不存在拓扑排序,也就是很多题目的无解的情况。 下面是算法的演示过程。 下面是我以前的写法,比较好理解,但是效率低 //b[]...

    在一个有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。

    先统计所有节点的入度,对于入度为0的节点就可以分离出来,然后把这个节点指向的节点的入度减一。

    一直做改操作,直到所有的节点都被分离出来。

    如果最后不存在入度为0的节点,那就说明有环,不存在拓扑排序,也就是很多题目的无解的情况。

    下面是算法的演示过程。

    下面是我以前的写法,比较好理解,但是效率低

     //b[]为每个点的入度
    for(i=1;i<=n;i++){
       for(j=1;j<=n;j++){
          if(b[j]==0){   //找到一个入度为0的点
            ans=j;
            vis[cnt++]=j;
            b[j]--;
            break;
           }
        }
        for(j=1;j<=n;j++)
            if(a[ans][j]) b[j]--; //与入度为0的点相连的点的入度减一
    }
        printf("%d",vis[0]);
        for(i=1;i<cnt;i++) printf(" %d",vis[i]);
        printf("\n");
    

     

    下面是我现在一直以来的写法,O(V+E)。点数+边书

     

        queue<int>q;
        vector<int>edge[n];
        for(int i=0;i<n;i++)  //n  节点的总数
            if(in[i]==0) q.push(i);  //将入度为0的点入队列
        vector<int>ans;   //ans 为拓扑序列
        while(!q.empty())
        {
            int p=q.front(); q.pop(); // 选一个入度为0的点,出队列
            ans.push_back(p);
            for(int i=0;i<edge[p].size();i++)
            {
                int y=edge[p][i];
                in[y]--;
                if(in[y]==0)
                    q.push(y);  
            }
        }
        if(ans.size()==n)   
        {
            for(int i=0;i<ans.size();i++)
                printf( "%d ",ans[i] );
            printf("\n");
        }
        else printf("No Answer!\n");   //  ans 中的长度与n不相等,就说明无拓扑序列

    有些拓扑排序要求字典序最小什么的,那就把队列换成优先队列就好了。

    例如:ZCMU-2153点击打开链接

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int inf=1e9;
    const int maxn=1e6+5;
    vector<int>edge[50];
    int in[50];
    int main()
    {
        char s[5];
        set<int>k;
        while(cin>>s)
        {
            k.insert(s[2]-'A');
            k.insert(s[0]-'A');
            if(s[1]=='>')
            {
                in[s[2]-'A']++;
                edge[s[0]-'A'].push_back(s[2]-'A');
            }
            else
            {
                in[s[0]-'A']++;
                edge[s[2]-'A'].push_back(s[0]-'A');
            }
        }
        priority_queue<int,vector<int>,greater<int> >q;
        for(int i=0;i<30;i++)
        {
            if(in[i]==0&&k.count(i)!=0)
                q.push(i);
        }
        vector<int>ans;
        while(!q.empty())
        {
            int p=q.top(); q.pop();
            ans.push_back(p);
            for(int i=0;i<edge[p].size();i++)
            {
                int y=edge[p][i];
                in[y]--;
                if(in[y]==0&&k.count(y)!=0)
                    q.push(y);
            }
        }
        if(ans.size()==k.size())
        {
            for(int i=0;i<ans.size();i++)
                printf("%c",ans[i]+'A');
            printf("\n");
        }
        else printf("No Answer!\n");
        return 0;
    }

    还有一种比较坑的排序 要求编号小的尽量排在前面,这里与字典序最小是不一样的,看一下例题。

    HDU-4857 点击打开链接

     

     

    逃生

     

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 6725    Accepted Submission(s): 1965

     

     

    Problem Description

    糟糕的事情发生啦,现在大家都忙着逃命。但是逃命的通道很窄,大家只能排成一行。

    现在有n个人,从1标号到n。同时有一些奇怪的约束条件,每个都形如:a必须在b之前。
    同时,社会是不平等的,这些人有的穷有的富。1号最富,2号第二富,以此类推。有钱人就贿赂负责人,所以他们有一些好处。

    负责人现在可以安排大家排队的顺序,由于收了好处,所以他要让1号尽量靠前,如果此时还有多种情况,就再让2号尽量靠前,如果还有多种情况,就让3号尽量靠前,以此类推。

    那么你就要安排大家的顺序。我们保证一定有解。

     

     

    Input

    第一行一个整数T(1 <= T <= 5),表示测试数据的个数。
    然后对于每个测试数据,第一行有两个整数n(1 <= n <= 30000)和m(1 <= m <= 100000),分别表示人数和约束的个数。

    然后m行,每行两个整数a和b,表示有一个约束a号必须在b号之前。a和b必然不同。

     

     

    Output

    对每个测试数据,输出一行排队的顺序,用空格隔开。

     

     

    Sample Input

    
     

    15 103 51 42 51 23 41 42 31 53 51 2

     

     

    Sample Output

    
     

    1 2 3 4 5

     

    举个例子如图:

     

    如果你用优先队列拓扑排序得到的是:3 5 6 4 1 7 8 9 2 0

    但是正确答案为 6 4 1 3 9 2 5 7 8 0 这样使得小的(1)尽量在前面。

    这里我们可以得到 前面的小的不一定排在前面,但是有一点后面大的一定排在后面。

    我们看 6和3不一定3排在前面,因为6后面连了一个更小的数字1能使得6更往前排。

    在看 2和 8,8一定排在后面,因为8后面已经没有东西能使它更往前排(除了0)。

    所以最后我们的做法就是 建立一个反图,跑一边字典序最大的拓扑排序,最后再把这个排序倒过来就是答案了。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    typedef long long ll;
    vector<int>edge[30010],ans;
    priority_queue<int>q;
    int in[30010];
    int T,n,m;
    void init()
    {
        for(int i=1;i<=n;i++)
        {
            edge[i].clear();
            in[i]=0;
        }
        while(!q.empty()) q.pop();
        ans.clear();
    }
    void solve()
    {
        int i,j;
        for(i=1;i<=n;i++)
            if(in[i]==0) q.push(i);
        while(!q.empty())
        {
            int p=q.top(); q.pop();
            ans.push_back(p);
            for( i=0; i<edge[p].size(); i++ )
            {
                int v=edge[p][i];
                in[v]--;
                if(in[v]==0) q.push(v);
            }
        }
        for(i=ans.size()-1;i>0;i--)
            printf("%d ",ans[i]);
        printf("%d\n",ans[0]);
    }
    int main()
    {
        int a,b;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d",&n,&m);
            init();
            while(m--)
            {
                scanf("%d%d",&a,&b);
                edge[b].push_back(a);
                in[a]++;
            }
            solve();
        }
        return 0;
    }
    

     

     

     

     

     

     

     

    展开全文
  • 网络拓扑绘图 网络拓扑绘图 网络拓扑绘图 网络拓扑绘图
  • 学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

    展开全文
  • arcgis一键拓扑工具、三调拓扑工具,
  • 微网电路拓扑 微网电路拓扑微网电路拓扑微网电路拓扑
  • 拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序
  • GemFire部署拓扑

    2018-01-02 13:11:28
    GemFire部署拓扑 GemFire部署拓扑 GemFire部署拓扑 GemFire部署拓扑
  • 网络拓扑

    2018-06-29 16:17:12
    网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络系统拓扑图网络...
  • 拓扑结构

    千次阅读 2021-01-07 09:21:17
    拓扑结构前言一、网络拓扑结构二、分类1.总线型2、环型3、树型4、星型5、网状 前言 计算机网络的拓扑结构分析是指从逻辑上抽象出网上计算机、网络设备以及传输媒介所构成的线与节点间的关系加以研究的一种研究...


    前言

    在这里插入图片描述

    计算机网络的拓扑结构分析是指从逻辑上抽象出网上计算机、网络设备以及传输媒介所构成的线与节点间的关系加以研究的一种研究方式。
    在进行计算机网络拓扑结构设计的过程中,通过对网络节点进行有效控制,对节点与线的连接形式进行有效选取,已经成为合理计算机网络拓扑结构构建的关键。设计人员对计算机网络拓扑结构进行有效选择,可以在很大程度上促进当前网络体系的运行效果,从根本上改善技术性能的可靠性、安全性。

    一、网络拓扑结构

    网络拓扑结构是指把网络电缆等各种传输媒体的物理连接等物理布局特征,通过借用几何学中的点与线这两种最基本的图形元素描述,抽象地来讨论网络系统中各个端点相互连接的方法、形式与几何形状,可表示出网络服务器、工作站、网络设备的网络配置和相互之间的连接。它的结构主要有总线型结构、星型结构、环型结构、树型结构、网状结构。

    二、分类

    1.总线型

    总线型就是一根主干线连接多个节点而形成的网络结构。在总线型网络结构中,网络信息都是通过主干线传输到各个节点的。总线型结构的特点主要在于它的简单灵活、构建方便、性能优良。其主要的缺点在于总干线将对整个网络起决定作用,主干线的故障将引起整个网络瘫痪。
    在这里插入图片描述

    2、环型

    环型结构主要是各个节点之间进行收尾连接,一个节点连接着一个节点而形成一个环路。在环形网络拓扑结构中,网络信息的传输都是沿着一个方向进行的,是单向的,并且,在每一个节点中,都需要装设一个中继器,用来收发信息和对信息的扩大读取。环形网络拓扑结构的主要特点在于它的建网简单、结构易构、便于管理。而它的缺点主要表现为节点过多,传输效率不高,不便于扩充。
    在这里插入图片描述

    3、树型

    树形网络结构主要是指各个主机进行分层连接,其中处在越高的位置,此节点的可靠性就越强。树形网络结构其实是总线性网络结构的复杂化,如果总线型网络结构通过许多层集线器进行主机连接,从而形成了树形网络结构。在互联网中,树形结构中的不同层次的计算机或者是节点,它们的地位是不一样的,树根部位(最高层)是主干网,相当于广域网的某节点,中间节点所表示的应该是大局域网或者城域网,叶节点所对应的就是最低的小局域网。树型结构中,所有节点中的两个节点之间都不会产生回路,所有的通路都能进行双向传输。其优点是成本较低、便于推广、灵活方便,比较适合那些分等级的主次较强的层次型的网络。

    在这里插入图片描述

    4、星型

    星型结构主要是指一个中央节点周围连接着许多节点而组成的网络结构,其中中央节点上必须安装一个集线器。所有的网络信息都是通过中央集线器(节点)进行通信的,周围的节点将信息传输给中央集线器,中央节点将所接收的信息进行处理加工从而传输给其他的节点。星型网络拓扑结构的主要特点在于建网简单、结构易构、便于管理等等。而它的缺点主要表现为中央节点负担繁重,不利于扩充线路的利用效率。
    在这里插入图片描述

    5、网状

    网型结构是最复杂的网络形式,它是指网络中任何一个节点都会连接着两条或者以上线路,从而保持跟两个或者更多的节点相连。网型拓扑结构各个节点跟许多条线路连接着,其可靠性和稳定性都比较强,其将比较适用于广域网。同时由于其结构和联网比较复杂,构建此网络所花费的成本也是比较大的。
    在这里插入图片描述

    展开全文
  • 拓扑排序

    千次阅读 2021-02-02 17:50:31
    拓扑排序 一、拓扑排序的定义: 先引用一段百度百科上对于拓扑排序的定义: 对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序,是将 G 中所有顶点排成一个线性序列,使得图中任意一对顶点 u ...

    拓扑排序

    一、拓扑排序的定义:

    先引用一段百度百科上对于拓扑排序的定义:

    对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序,是将 G
    中所有顶点排成一个线性序列,使得图中任意一对顶点 u 和 v ,若边 < u , v > ∈ E ( G ),则 u 在线性序列中出现在 v
    之前。通常,这样的线性序列称为满足拓扑次序 ( Topological Order )
    的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

    什么意思呢,总结起来有三个要点:
    1.有向无环图;
    2.序列里的每一个点只能出现一次;
    3.任何一对 u 和 v ,u 总在 v 之前(这里的两个字母分别表示的是一条线段的两个端点,u 表示起点,v 表示终点);

    二、拓扑排序的过程

    这里以下面这个有向无环图为例,分析一下拓扑排序的具体过程。
    在这里插入图片描述

    首先,我举一个例子,比如打游戏时,刚开始一个游戏,你一定要先打第一关,因为只有打通了第一关,才能解锁下一关或下几关,而不能上来就打第二关。特别地,第一关时不需要之前打任何一关,最后一关打完不会解锁任何一关。
    回到图中我举的例子,1 号端点就相当于第一关,而 6 号端点就相当于是最后一关。所以我们就知道了:
    1.找一个入度为零(不需其他关卡通关就能解锁的)的端点,如果有多个,则从编号小的开始找;
    2.将该端点的编号输出;
    3.将该端点删除,同时将所有由该点出发的有向边删除;
    4.循环进行 2 和 3 ,直到图中的图中所有点的入度都为零;
    5.拓扑排序结束;

    那么我现在就以上图为例,详细分析一下过程;

    第一步:输出 “ 1 ”;
    在这里插入图片描述

    第二步:输出 “ 2 ”;
    在这里插入图片描述
    第三步:输出 “ 3 ”;
    在这里插入图片描述
    第四步:输出 “ 4 ”;
    在这里插入图片描述
    第五步:输出 “ 5 ”;
    在这里插入图片描述
    第六步:输出 “ 6 ”,排序结束。
    所以,最终拓扑排序的结果是
    1 2 3 4 5 6
    三、拓扑排序在具体题目中应用

    下面以最大食物链计数为例实际应用一下拓扑排序。

    题目背景
    你知道食物链吗?Delia生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。

    题目描述
    给你一个食物网,你要求出这个食物网中最大食物链的数量。

    (这里的“最大食物链”,指的是生物学意义上的食物链,即最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者。)

    Delia 非常急,所以你只有 11 秒的时间。

    由于这个结果可能过大,你只需要输出总数模上 8011200280112002 的结果。

    输入格式
    第一行,两个正整数 n、mn、m,表示生物种类 nn 和吃与被吃的关系数 mm。

    接下来 mm 行,每行两个正整数,表示被吃的生物A和吃A的生物B。

    输出格式
    一行一个整数,为最大食物链数量模上 8011200280112002 的结果。

    输入输出样例
    输入
    5 7
    1 2
    1 3
    2 3
    3 5
    2 5
    4 5
    3 4
    输出
    5

    【补充说明】 数据中不会出现环,满足生物学的要求。(感谢 @AKEE )

    代码及分析如下:

    `#include<bits/stdc++.h>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<cstdio>
    #include<vector>
    #include<cmath>
    #include<queue>
    #include<deque>
    #include<stack>
    #include<set>
    #include<map>
    using namespace std;
    int read(){
        int X=0,w=0;
    	char ch=0;
    	while(!isdigit(ch)){
    		w|=ch=='-';
    		ch=getchar();
    	}
        while(isdigit(ch)){
    		X=(X<<3)+(X<<1)+(ch^48);
    		ch=getchar();
    	}
        return w?-X:X;
    }
    char F[200];
    void write(int x){
    	if(x==0){
    		putchar('0');
    		return;
    	}
    	int cnt=0,tmp=x>0?x:-x;
    	if(x<0){
    		putchar( '-' );
    	}
    	while(tmp>0){
    		F[cnt++]=tmp%10+'0';
    		tmp/=10;
    	}
    	while(cnt>0){
    		putchar(F[--cnt]);
    	}
    }
    int n,m,ans;
    const int mod=80112002;
    const int N=0x3f3f3f;
    queue<int> q;//拓扑排序模板所需队列; 
    vector<int> p[N];//存每条有向边的起点和重点; 
    int in[N],out[N],num[N];//每个点的入度和出度和伪食物链的个数; 
    int main()
    {
    	n=read(),m=read();
    	for(int i=1;i<=m;i++){
    		int x=read(),y=read();
    		in[y]++;//右端点入度+1;
    		out[x]++;//左端点出度+1;
    		p[x].push_back(y);//将这条有向边存起来;
    	}
    	for(int i=1;i<=n;i++){
    	//寻找入度为零的点(源头生产者);
    		if(in[i]==0){
    			num[i]=1;//初始化;
    			q.push(i);//加到队列当中;
    		}
    	}
    	while(q.empty()==0){
    		int sum=q.front();
    		q.pop();
    		int len=p[sum].size();
    		for(int i=0;i<len;i++){
    			//枚举以该点为起点的所有线段的终点;
    			int now=p[sum][i];//取出目前枚举到的点;
    			in[now]--;//将这个点的入度-1(因为目前要删除第tot个点); 
    			num[now]=(num[now]+num[sum])%mod;//更新到下一个点的路径数量; 
    			if(in[now]==0){
    				q.push(now);//如果这个点的入度为零了,那么加入队列; 
    			}
    		}
    	}
    	for(int i=1;i<=n;i++){
    		//寻找出度为0的点(尽头消费者);
    		if(out[i]==0){
    			ans=(ans+num[i])%mod;
    		}
    	}
    	write(ans);
    	return 0;
    }`
    

    谢谢阅读!

    展开全文
  • 拓扑序列(拓扑排序)

    千次阅读 2020-03-31 21:07:31
    文章目录摘要什么是拓扑序列拓扑序的求法 摘要 本文主要介绍拓扑排序,和求解拓扑排序的方法。 什么是拓扑序列 拓扑序列是对于有向图而言的,有向图的拓扑序是其顶点的线性排序,使得对于从顶点uuu 到顶点vvv的每个...
  • 【Kafka】kafka拓扑架构

    万次阅读 2019-12-16 22:35:11
    1 kafka拓扑架构 Broker Kafka集群包含一个或多个服务器,这种服务器被称为broker Topic 每条发布到Kafka集群的消息都有一个类别,这个类别被称为Topic。(物理上不同Topic的消息分开存储,逻辑上一个Topic的...
  • 网上证券拓扑网上证券拓扑网上证券拓扑网上证券拓扑
  • 什么是拓扑结构_拓扑结构图

    万次阅读 多人点赞 2018-09-09 09:17:01
    什么是拓扑结构?  首先我们来解释一下拓扑的含义,所谓“拓扑”就是把实体抽象成与其大小、形状无关的“点”,而把连接实体的线路抽象成“线”,进而以图的形式来表示这些点与线之间关系的方法,其目的在于研究...
  • 建立拓扑和验证 1 ArcCatalog新建数据库 在ArcCatalog中,连接到文件夹后,右键→New→File Geodatabase,命名为test.gdb(后缀为mdb为个人数据库); 2 数据库中新建要素数据集 右键新建的test.gdb→New→Feature ...
  • 点集拓扑讲义

    2018-06-04 21:08:06
    《点集拓扑讲义(第四版)》讲述点集拓扑的基本知识,其基本内容涵盖:拓扑空间和连续映射的定义及其基本性质;构造新的拓扑空间的方法;各种拓扑不变性质,如连通性、分离性、紧致性、度量空间的完备性等,以及这些...
  • MPI_Graph_create和MPI_Cart_create函数分别用于产生通常(图)的虚拟拓扑和笛卡尔拓扑虚拟拓扑: 虚拟拓扑可以用图来表示,每个进程代表一个点,两点之间的连线代表通信联通,但是注意MPI在任意两个进程之间都可...
  • 用户对于网管自动化拓扑的需求,主要包括支持设备全面、自动高效地生成拓扑、体现中间件/数据库连接关系、支持特殊的拓扑操作实现。针于网管自动化拓扑的需求,智和网管平台提出了自动化拓扑解决方案,通过网管平台...
  • 没错,这个系列是我无法安心复习而使用记博客的方式来对拓扑学知识重点(考点)进行汇总总结。以尤承业老师的《基础拓扑学讲义》为基础。 第一节首先引入拓扑空间 0.前置知识( 幂集、子集族和连续的开集刻画) 0.1 ...
  • 网络拓扑

    2019-03-07 14:15:19
    网络拓扑简介拓扑结构分类折叠总线结构折叠星型结构折叠环形结构折叠树型结构折叠网状结构 简介 计算机网络的拓扑结构是引用拓扑学中研究与大小,形状无关的点、线关系的方法。把网络中的计算机和通信设备抽象为一个...
  • 点云拓扑

    千次阅读 2019-07-08 21:51:29
    一、拓扑关系 1.概念: 2.点云拓扑概念: 二、建立拓扑关系 三、建立拓扑关系算法 (一) KD-Tree 算法 1. 概念: 2. 划分K维数据: 3. KD-Tree构建 4. KD-Tree的最近邻查找 (二) Octree 算法 1.概念:...
  • 楼宇间拓扑,是将网络拓扑精确到楼宇级别,对某个单位或组织内部的网络组建情况进行测绘。该部分与城域网络拓扑的研究内容一致,但将路由器的位置更加精确地定位到楼宇级别。 关键技术 楼宇间网络拓扑测绘技术包含...
  • 网络拓扑结构

    万次阅读 2018-10-02 20:19:10
    网络拓扑结构 网络拓扑结构是指用传输媒体对各种... 目前常见的网络拓扑结构主要有:总线型拓扑结构、环形拓扑结构、星形拓扑结构、混合型拓扑结构和其他拓扑结构等。 一、总线型拓扑结构 总线结构上所有的结点都连...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,704
精华内容 32,681
关键字:

拓扑