程序员
董欣欣的个人博客

拓扑排序 偏序 全序介绍

拓扑序列算法思想
 (1)从有向图中选取一个没有前驱(即入度为0)的顶点,并输出之;
 (2)从有向图中删去此顶点以及所有以它为尾的弧;
     重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。
注意:
 1)只有有向无环图才存在拓扑序列;
 2)对于一个DAG,可能存在多个拓扑序列;
 
偏序/全序关系:
偏序和全序实际上是离散数学中的概念。
这里不打算说太多形式化的定义,形式化的定义教科书上或者上面给的链接中就说的很详细。
以选课的例子来描述这两个概念。假设我们在学习完了算法这门课后,可以选修机器学习或者计算机图形学。这个或者表示,学习机器学习和计算机图形学这两门课之间没有特定的先后顺序。因此,在我们所有可以选择的课程中,任意两门课程之间的关系要么是确定的(即拥有先后关系),要么是不确定的(即没有先后关系),绝对不存在互相矛盾的关系(即环路)。以上就是偏序的意义,抽象而言,有向图中两个顶点之间不存在环路,至于连通与否,是无所谓的。所以,有向无环图必然是满足偏序关系的。
理解了偏序的概念,那么全序就好办了。所谓全序,就是在偏序的基础之上,有向无环图中的任意一对顶点还需要有明确的关系(反映在图中,就是单向连通的关系,注意不能双向连通,那就成环了)。可见,全序就是偏序的一种特殊情况。回到我们的选课例子中,如果机器学习需要在学习了计算机图形学之后才能学习(可能学的是图形学领域相关的机器学习算法……),那么它们之间也就存在了确定的先后顺序,原本的偏序关系就变成了全序关系。
实际上,很多地方都存在偏序和全序的概念
比如对若干互不相等的整数进行排序,最后总是能够得到唯一的排序结果(从小到大,下同)。这个结论应该不会有人表示疑问吧:)但是如果我们以偏序/全序的角度来考虑一下这个再自然不过的问题,可能就会有别的体会了。
那么如何用偏序/全序来解释排序结果的唯一性呢?
我们知道不同整数之间的大小关系是确定的,即1总是小于4的,不会有人说1大于或者等于4吧。这就是说,这个序列是满足全序关系的。而对于拥有全序关系的结构(如拥有不同整数的数组),在其线性化(排序)之后的结果必然是唯一的。对于排序的算法,我们评价指标之一是看该排序算法是否稳定,即值相同的元素的排序结果是否和出现的顺序一致。比如,我们说快速排序是不稳定的,这是因为最后的快排结果中相同元素的出现顺序和排序前不一致了。如果用偏序的概念可以这样解释这一现象:相同值的元素之间的关系是无法确定的。因此它们在最终的结果中的出现顺序可以是任意的。而对于诸如插入排序这种稳定性排序,它们对于值相同的元素,还有一个潜在的比较方式,即比较它们的出现顺序,出现靠前的元素大于出现后出现的元素。因此通过这一潜在的比较,将偏序关系转换为了全序关系,从而保证了结果的唯一性。
拓展到拓扑排序中,结果具有唯一性的条件也是其所有顶点之间都具有全序关系。如果没有这一层全序关系,那么拓扑排序的结果也就不是唯一的了。在后面会谈到,如果拓扑排序的结果唯一,那么该拓扑排序的结果同时也代表了一条哈密顿路径。
未经允许不得转载:董不董 - 董欣欣的个人博客 » 拓扑排序 偏序 全序介绍
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

www.dongxinxin.cn 技术博客

联系我关于我