什么是数据结构与算法分析中偏序全序-问答-阿里云开发者社区-阿里云

开发者社区> 知与谁同> 正文

什么是数据结构与算法分析中偏序全序

2018-07-20 09:37:58 943 1
什么是数据结构与算法分析中偏序全序
取消 提交回答
全部回答(1)
  • 小旋风柴进
    2019-07-17 22:53:43
    查看Castle的代码,在Castle.Core中内部的数据结构采用图,排序使用的拓扑排序算法:
    对于一条有向边(u,v),定义u < v;满足所有这样条件的结点序列称为拓扑序列。拓扑排序就是求一个有向图的拓扑序列的算法。
    一个有向图顶点的拓扑序列不是惟一的。并不是任何有向图的顶点都可以排成拓扑序列,有环图是不能排的。
    例子:比如排课问题,比如士兵排队问题等。
    拓扑排序在实际生活中和算法中都有很大的应用。比如要排一下几门课程的先后次序,我们可以把课程抽象成结点,把什么课是什么课的基础抽象成边,那么该图的一个拓扑序列就是这些课的一个可行的先后次序。各种语言的编译器都用到了拓扑排序。
    数学基础:
    什么是拓扑排序(Topological Sort)?简单地说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
    回顾离散数学中关于偏序和全序的定义:
    若集合X上的关系R是自反的、反对称的和传递的,则称只是集合X上的偏序关系。
    设R是集合X上的偏序(Partial Order),如果对每个x,y∈X必有xRy或yRx,则称R是集合X上的全序关系。
    直观地看,偏序指集合中仅有部分成员之间可比较,而全序指集合中全体成员之间均可比较。[例如],图7.25所示的两个有向图,图中弧(x,y)表示x≤y,则(a)表示偏序,(b)表示全序。若在(a)的有向图上人为地加一个表示v2≤v3的弧(符号“≤”表示v2领先于v3),则(a)表示的亦为全序,且这个全序称为拓扑有序(Topological Order),而由偏序定义得到拓扑有序的操作便是拓扑排序。

    ToplogicalSort.gif
    AOV-网及其拓扑有序序列产生的过程
    (a)AOV-网;(b)输出v6之后;(c)输出v1之后;(d)输出v4之后;(e)输出v3之后;(f)输出v2之后

    [思想]:
    一、从有向图中选取一个没有前驱的顶点,并输出之;
    二、从有向图中删去此顶点以及所有以它为尾的弧;
    重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。没有前驱 -- 入度为零,删除顶点及以它为尾的弧-- 弧头顶点的入度减1。

    [人度为零的顶点拓扑排序算法]:
    Status Topological Sort(ALGraph G){
    //有向图G采用邻接表存储结构。
    //若G无回路,则输出G的顶点的1个拓扑序列并返回OK,否则ERROR。
    FindInDegree(G,indegree); //对各顶点求入度indegree[0..vernum-1]
    InitStack(S);
    for(i=0;i<G.vexnum; ++i)
    if(!indegree[i])Push(S,i) //建零入度顶点栈,s入度为0者进栈
    count=0; //对输出顶点计数
    while (!StackEmpty(S)) {
    Pop(S,i);
    printf(i,G.vertices[i].data); ++count; //输出i号顶点并计数
    for(p=G.vertices[i].firstarc;p; p=p—>nextarc) {
    k=p—>adivex; //对i号顶点的每个邻接点的入度减1
    if(。(--indegree[k]))Push(S,k);//若入度减为0,则入栈
    }//for
    }//while
    if(count<G.vexnum) return ERROR; //该有向图有回路
    else return OK;
    }//TopologicalSort
    算法 ,总的时间复杂度为O(n+e)。
    0 0
相关问答

1

回答

如何构建机器学习算法?

问问小秘 2020-04-15 14:07:23 35408浏览量 回答数 1

25

回答

云服务器网站没有被百度和google收录或者收录少怎么办?

qilu 2014-05-20 18:13:19 29955浏览量 回答数 25

38

回答

干货分享:DBA专家门诊一期:索引与sql优化问题汇总

xiaofanqie 2014-12-25 15:13:38 91788浏览量 回答数 38

9

回答

换个角度理解正则表达式

jagen 2014-07-23 14:00:21 25081浏览量 回答数 9

37

回答

阿里官方Java代码规范标准《阿里巴巴Java开发手册》下载

管理贝贝 2017-02-10 15:14:36 75015浏览量 回答数 37

13

回答

【阿里云产品公测】开放搜索服务之 智能聊天实现

啊里新人 2014-10-21 10:41:20 33517浏览量 回答数 13

6

回答

弹性计算。。

d1004 2011-11-23 14:35:13 24557浏览量 回答数 6

26

回答

云数据库OceanBase的架构演进【精品问答集锦】

管理贝贝 2016-09-02 16:57:42 44061浏览量 回答数 26

24

回答

比赛_快速入门_4_19_update_仅供参考,思维不要受局限

小斯never 2015-03-22 18:22:43 33078浏览量 回答数 24

5

回答

C语言算法 【精品问答合集】

我是管理员 2018-07-13 15:51:28 26907浏览量 回答数 5
+关注
10077
文章
2994
问答
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载