圖形分層佈局算法

Question

有許多工具和SDK，其佈局圖。 ogdf，GraphViz的，mxGraph，YED ...

一個有用的佈局是 「分層結構佈局」。但是沒有純粹的算法或僞代碼來描述它。甚至，這種佈局沒有明確的定義。有人知道這個算法嗎？

Answer 1

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

簡單的分層佈局算法是儘快SHEDULING算法的可視化（檢查這個講座 [link]），所以它最好能夠閱讀它，在我的看法。

BTW您的圖片是不完全正確 - 所提出的可視化只是可能的一個。

試想一下，你有節點的列表，你知道它們之間的依賴關係。

節點列表

node4 
node2 
node5 
node1 
node3 
node6 

相關性列表

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

• 作爲你的第一步，你會發現，沒有Dependance的節點 - 這 將是你的層＃1的節點。畫他們。
• 然後發現，取決於層＃1節點的所有節點 - 這將是你的層＃2節點。

• 而對於層＃2同樣的事情，等 最後，你會得到：

    node1 
       / \ 
       node2 node3 
      / / \ 
      node4 node5 node6 
  

這將只能用於非循環有向圖。對於無向的應該修改一下算法（以隨機節點爲根節點），但我認爲，主要想法是可以理解的。