做习题,学知识 |
您所在的位置:网站首页 › 拓扑有序什么意思 › 做习题,学知识 |
对如下所示的有向图进行拓扑排序,得到的拓扑序列可能是 () imageA、3,1,2,4,5,6 B、3,1,2,4,6,5 C、3,1,4,2,5,6 D、3,1,4,2,6,5 Q:什么是拓扑排序(Topological Sort)? A:简单地说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。 让我们一起来回顾离散数学中关于偏序和全序的定义: 若集合 X 上的关系 R 是自反的、反对称的和传递的,则称 R 是集合 X 上的偏序关系。 设 R 是集合 X 上的偏序(Partial Order),如果对每个 x,y∈X 必有 xRy 或yRx,则称 R 是集合 X 上的全序关系。 Q: 还不是很懂啊?! A:直观地看,偏序指集合中仅有部分成员之间可比较,而全序指集合中全体成员之间均可比较。 例如,下图所示的两个有向图图中弧(x,y)表示 x≤y,则(a)表示偏序,(b)表示全序。 image若在(a)的有向图上人为地加一个表示v2≤v3 的弧(符号 ≤ 表示 v2 领先于边 v3),则(a)表示的亦为全序,且这个全序称为拓扑有序,而由偏序定义得到拓扑有序的操作便是拓扑排序。 Q:嗯嗯,明白了呢。那么,又该如何进行拓扑排序呢? A:方法其实很简单: (1)在有向图中选一个没有前驱的顶点且输出之。 (2)从图中删除该顶点和所有以它为尾的弧。 重复上述两步,直至全部顶点均已输出或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。 Q:能不能举个栗子呢? A:好吧,以下面的有向图为例。 image图中,v1 和 v6 没有前驱,则可任选一个。假设先输出 v6,在删除 v6 及弧(v6,4),(v6,v5)之后,只有顶点 v1 没有前驱,则输出 v1 且删去 v1 及弧 (v1,v2)、(v1,v3)和(v1,v4),之后v3 和 v4 都没有前驱。 依次类推,可从中任选一个继续进行。整个拓扑排序过程如上图所示。 最后得到该有向图的拓扑有序序列为(注意:拓扑排序序列不一定唯一): v6 - v1 -v4 - v3 - v2 - v5 A:讲到这里,相信大家对拓扑排序应该有个大概的了解了吧,那么上面题目的答案就由你们自己推理啦。 文章首发于公众号【暗星涌动】。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |