用于分层的最长路径算法

Question

我正在制作一个程序以生成公司的组织结构图。我一直在阅读最长路径算法来对顶点进行分层，并且有一件事情一直在困扰着我。我所做的阅读表明，图形应该从下到上进行分层，首先将底层没有子节点的节点放到底层，然后进行处理。不过，我也读过最长路径算法导致图底部非常宽。

我在想，我会尝试从顶部开始构建图表，从没有父母的节点开始，一路走下来。也许这是常见的，我只是没有看到它的使用，但我担心有一些原因，我没有看到这种做法不切实际。有什么我失踪？

Answer 1

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