拓扑排序与装修

发表于 更新于 分类于

最近在搞装修，发现在装修的过程中，很容易无法区分各种节点的主次，这时候就想起了拓扑排序。

装修

装修的过程中，一般都要经历很多的节点，比如：砌墙、刷漆、安装空调新风、吊顶、铺设地板瓷砖、水电等等。

大部分的功能其实是相互依赖的，比如你必须砌墙了才能刷漆；安装了新风空调才能吊顶；确定了电器才能打橱柜等等等等。这种繁琐的问题自己捋的时候经常混乱，有时候不得不就咨询施工方，总是怕自己耽误了进度。

这时候突然想到了算法中的调度问题。

逆后序

一般来说，数据结构（尤其是图）的遍历一般分为三种排列顺序。

  • 前序
  • 后序
  • 逆后序

其中逆后序定义是：在递归调用之后将顶点压入栈

也就是说，在节点没有被彻底搜索完之前是不会进入到栈中的，也就是说最先被加入栈的则是没有后续节点的节点，也就是最后的工序比如：进家具。

其中，这些步骤，也就是我们的节点，相互的依赖关系则将它们形成了一副有向图，这也是进行逆后序的关键。

拓扑排序

拓扑排序有可能有很多种算法来实现，主要是为了将杂乱无章的调度问题规划为一个线性的有序排列，为我们解决各种各样的问题，比如装修。逆后序就是其中的一种简单算法。

逆后序实现起来非常简单，如定义一样，只需要在深度优先搜索中加入简单的一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
private boolean[] marked;
private Stack<Integer> reversePost;

// 示意

private void dfs(Digraph G, int v) {
    marked[v] = true;
    for (int w: G.adj(v)) {
        if (!marked[w]) dfs(G, w);
    }
    reversePost.push(v);
}

其中再想获取拓扑排序的时候，只需要简单的进行出栈操作：

1
2
3
for (int v: reversePost) {
    System.out.println(v);
}

就可以非常简单直观的输出所需要的顺序，从而简化了调度任务。

我也就知道我得先赶紧买空调和新风了。