基于深度优先搜索的正方化树图布局算法

正方化布局算法在树图可视化形式中得到广泛使用，然而经典正方化树图布局算法无法获得平均长宽比最优的结果.通过分析经典正方化树图布局算法的实现细节，特别是每一步矩形块位置的选择过程，论证了经典正方化算法由于使用贪心算法原理导致的缺陷，结合深度优先搜索技术，提出了基于深度优先搜索的正方化树图布局算法（DSS算法）.在详细阐述DSS算法实现过程的基础上，结合实证研究，对DSS算法在平均长宽比方面的优势，时间性能的改进方向和本质特点进行了深入探讨.

Squarified Treemap Layout Algorithm Based on Depth-First Search

Squarified layout algorithm is widely used in the Treemap Visualization, but classic Squarified algorithm cannot achieve the best average aspect ratio. By analyzing implementation details of Squarified Treemap layout algorithm, especially each step of the rectangular block position selection process, the paper demonstrates the drawback of classic Squarified algorithm caused by using greedy algorithm. Combining with depth-first search technique, it also proposes Squarified Treemap layout algorithm based on depth-first search (DSS algorithm). Based on elaborating implementation process of DSS algorithm, combining empirical research, the advantage of the DSS algorithm in the aspect ratio, the improvement direction and the essential characteristics of the time performance are discussed.