一种图层分配的最长路径算法

Question

我正在开发一个程序来生成一家公司的组织结构图。我一直在阅读关于分层顶点的最长路径算法，有一件事一直困扰着我。我所做的阅读表明，图表应该从下往上分层，首先将没有子节点的节点放在最底层，然后向上工作。然而，我也读到过最长路径算法会产生底部非常宽的图。

我在想，我应该尝试自上而下地构建图形，从没有父节点的节点开始，然后向下工作。也许这很常见，我只是没有看到它的使用，但我担心有一些原因，我没有看到使这种方法不切实际。我是不是漏掉了什么？

Answer 1

最长路径算法将高度最小化，但本质上忽略了宽度。如果你从下到上对图进行分层，并且图中有许多下沉(零出度数的顶点)，那么你将得到一个较宽的底层。如果你从上到下对图进行分层，并且它有很多源(零度数的顶点)，那么你会得到一个很宽的顶层。如果您将汇的数量与源的数量进行比较，则可以选择要使用的变量。然而，你仍然可以得到宽的中间层。要减少(而不是最小化)所有层的宽度，您需要查看像Coffman-Graham algorithm这样的算法。