《编程珠玑(续)(修订版)》—第2章2.3节拓扑排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

《编程珠玑(续)(修订版)》—第2章2.3节拓扑排序

简介: 算法的循环步骤每次选出一个祖先结点数为零的结点,把它写到输出文件中,其所有后代结点的祖先数量全部减少1。

本节书摘来自异步社区《编程珠玑(续)(修订版)》一书中的第2章,第2.3节拓扑排序,作者【美】Jon Bentley,更多章节内容可以访问云栖社区“异步社区”公众号查看。

2.3 拓扑排序
拓扑排序算法的输入是一个有向无环图,例如:


bf058c7cb10464e21133cb1a051adbeb18e0301b

如果图中包含从A到B的边,那么A就是B的祖先而B是A的后代。算法必须对图中结点排序以使得所有祖先出现在它们的后代之前,下图是许多可能排序中的一种。

4f771f8b0dccd909293dce91418024e685f2f7fd

算法还必须能够处理输入图中包含回路因此无法完成排序的可能情况。

这样的算法可以应用于绘制物体的三维场景。如果物体B在视图中处于物体A的前面,那么A就在B之前,因为A必须在B之前完成绘制。下图左边由4个矩形构成的场景能够导出右边的偏序。


01c62d439ab87e2c89298098876eddc3ca81f414

图2-5中有两种对顶点的有效排序,即A B C D和A C B D。每种排序都恰当地给出了物体的覆盖图。拓扑排序的其他应用包括对技术文档进行布局(术语在使用之前必须先定义)以及处理层次化VLSI设计(算法在处理一个部件之前必须先处理其组成部分)。继续阅读之前,请花一分钟思考你将如何编写对有向图进行拓扑排序的程序。

我们将研究一个拓扑排序算法,该算法引自Knuth的《计算机程序设计艺术,卷1:基本算法》④一书的2.2.3节。该算法的循环步骤如下:选出一个没有祖先的结点T,将T写到输出文件中,然后从图中删除从T出发的所有边。下图显示了这个算法如何应用在之前的四结点场景图上。算法的各阶段从左向右进行,每一阶段选出的结点T都画了圈。


2c7c8d8f9b9982a105ad7f3196ae0c818f9cf7a6

排序结果是A B C D。

这个算法的一种低效的实现在每一步都要扫描整个图以找到没有祖先的结点。现在来研究一个更简单也更高效的算法。对每个结点,新算法都存储它的祖先数量以及后代结点集合。比如,上面所画的四结点图表示如下:


c912f2a9e131bbb558ad5394838b4c8444a8dbab

算法的循环步骤每次选出一个祖先结点数为零的结点,把它写到输出文件中,其所有后代结点的祖先数量全部减少1。然而,算法必须仔细记住不同顶点其祖先计数变为零的先后顺序,这里使用了一个结点队列。(如果在所有结点的祖先计数变为零之前队列为空,那么程序报告图中存在回路。)

下面的伪代码假设输入给程序的图是由一系列(祖先,后代)对表示的,每行一对。

as each (pred, succ) pair is read
   increment pred count of succ
   append succ to successors of pred
at the end of the input file
   initialize queue to empty
   for each node i
     if pred count of i is zero then append i to queue
   while queue isn't empty do
     delete t from front of queue; print t
     for each successor s of t
        decrement pred count of s
        if that goes to zero then append x to queue
   if some nodes were not output then report a cycle

算法的运行时间与图中的边数成比例,只比最理想的情况多出一个常数因子。(每条边处理两次:一次是读,一次是从队列中将其删除。)

Awk程序使用一个索引范围是1..n的数组来实现队列。整型变量qlo是队列首元素的索引,qhi是尾元素的索引。后代集合由两个数组实现。如果A有后代B、C、D,那么下面的关系成立:

succct["A"] == 3
succlist["A",  "1"] == "B"
succlist["A",  "2"] == "C"
succlist["A",  "3"] == "D"

这个Awk程序的输入是一个祖先-后代对文件,其输出是排序好的结点列表或关于这样的列表不存在的警告。

{ ++predct[$2]        _#_ record nodes in predct,
    predct[$1] = predct[$1]  _#_ even those with no preds
    succlist[$1, ++succcnt[$1]] = $2
   }
END  { qlo = 1
    for (i in predct)  {
      n++; if (predct[i] == 0) q[++qhi] = i
    }
    while (qlo <= qhi)  {
      t = q[qlo++]; print t
      for (i = 1; i <= succcnt[t]; i++)  {
         s = succlist[t, i]
         if (--predct[s] == 0) q[++qhi] = s
      }
    }
    if (qhi != n) print "tsort error: cycle in input"
}

程序第二行保证所有结点都作为predct的索引出现,即便没有祖先的结点也一样。

本程序的关联数组表示了几种不同的抽象数据类型:一个结点名字的符号表、一个记录数组、一个二维的后代集合序列以及一个结点队列。本程序小巧、便于理解,但在较大的程序中无法清楚分辨不同的抽象数据类型就会降低程序可读性。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: