图层次布局算法

有许多工具和 SDK 可以布局图表。 ogdf、GraphViz、mxGraph、yEd...

有用的布局之一是“分层布局”。但没有纯粹的算法或伪代码来描述它。甚至，这种类型的布局还没有明确的定义。有人了解算法吗？

_{(source: yworks.com http://docs.yworks.com/yfiles/doc/developers-guide/figures/hier-style-explanation-thumb.png)}

简单的层次布局算法是ASAP调度算法的可视化（查看这个讲座 [link] http://cas.ee.ic.ac.uk/people/gac1/Synthesis/Lecture9.pdf），所以我认为最好阅读它。

顺便说一句，您的图片并不完全正确 - 建议的可视化只是可能的可视化之一。

想象一下，您有节点列表并且您知道它们之间的依赖关系。

节点列表

node4
node2
node5
node1
node3
node6

依赖列表

node1 -> node2
node2 -> node4
node3 -> node5
node1 -> node3
node3 -> node6

• 作为第一步，您应该找到没有依赖关系的节点 - 这 将是您的第 1 层节点。画它们。
• 然后找到依赖于第 1 层节点的所有节点 - 这将是第 2 层节点。

• 对于第 2 层等也是同样的事情。 最后，你会得到：

           node1
          /     \
        node2  node3
         /     /   \
      node4 node5 node6
  

这仅适用于非循环有向图。对于无向的，你应该稍微修改一下算法（以随机节点为根），但我认为主要思想是可以理解的。