c# - 图分层布局算法

Question

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

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

Answer 1

_{（来源：yworks.com）}

简单的分层布局算法是 ASAP 调度算法的可视化（查看本讲座[链接]），所以在我看来，阅读它会更好。

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

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

节点列表

node4
node2
node5
node1
node3
node6

依赖列表

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

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

• 对于第 2 层等也是如此。最后，你会得到：

           node1
          /     \
        node2  node3
         /     /   \
      node4 node5 node6
  

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