图分层布局算法

Question

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

有用的布局之一是"分层布局".但是没有纯算法或伪代码来描述它.甚至,这种布局没有明确的定义.有人知道算法吗？

Answer 1

http://docs.yworks.com/yfiles/doc/developers-guide/figures/hier-style-explanation-thumb.png

简单的分层布局算法是ASAP调度算法的可视化(查看本讲座[链接]),因此在我的观点上阅读它会更好.

BTW你的图片不完全正确 - 建议的可视化只是其中一个可能的.

想象一下,你有节点列表,你知道它们之间的依赖关系.

节点列表

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
  

这仅适用于非循环有向图.对于无向的算法,你应该稍微修改算法(以随机节点为根),但我认为主要的想法是可以理解的.