graph-drawing - 层分配的最长路径算法

Question

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

我在想我会尝试从上到下构建图表，从没有父节点的节点开始，然后一路向下。也许这很常见，我只是没有看到它使用过，但我担心有一些我没有看到的原因导致这种方法不切实际。有什么我想念的吗？

Answer 1

最长路径算法使高度最小化，但本质上忽略了宽度。如果您从下往上对图进行分层，并且该图有许多汇（出度为零的顶点），那么您将得到一个较宽的底层。如果您从上到下对图形进行分层，并且它有很多来源（入度为零的顶点），那么您将获得一个较宽的顶层。如果您将接收器的数量与源的数量进行比较，您可以选择使用哪个变体。但是，您可能仍然会得到较宽的中间层。要减少（而不是最小化）所有层的宽度，您需要查看类似Coffman-Graham 算法的算法。