摘  要：针对结构复杂、联通算法难以实现的层级结构联通性问题，提出了利用树结构的最长路径算法解决层级结构型数据的方法。本研究以传统城堡防护问题为例，找出中间相隔的城墙数量最多的两个点，即层级结构的联通厚度。通过数据结构分析，将城堡各区域转化为树结构，验证了树结构的最长路径即为层级结构的联通厚度，最终巧妙实现将层级结构转换为树结构，并利用树结构的遍历分析寻找到树的最长路径递归算法，解决了树节点到节点的最长路径，最终实现层级结构各层的联通路径建设规划，为层级结构问题的解决找到突破口与参考性。

关键词：层级结构;生成树结构;联通算法;最长路径

中图分类号：TP399     文献标识码：A

Research on the Connectivity of Hierarchical Structured Data

HE Junzhong

（Longnan Teachers College， Chengxian 742500， China）

lnszhjztg@163.com

Abstract： Aiming at the problem of hierarchical structure connectivity that is difficult to achieve with the complex structure， this paper， proposes a method of using the longest path algorithm of the tree structure to solve the problem of hierarchical structure data. This research takes traditional castle protection problem as an example. It is necessary to find the two points， between which there is the largest number of walls， namely the connectivity thickness of the hierarchical structure. Through data structure analysis， each area of the castle is transformed into a tree structure to verify that the longest path of the tree structure is the connectivity thickness of the hierarchical structure. Finally， hierarchical structure is ingeniously transformed into tree structure， and the traversal of the tree structure is used to analyze and find the longest path recursive algorithm of the tree. It solves the longest path from the tree node to the node. Finally， the proposed method realizes the connection path construction planning of each layer in the hierarchical structure， and makes breakthroughs and provides references for solving hierarchical structure problems.

Keywords： hierarchical structure; spanning tree structure; connectivity algorithm; longest path

1   引言（Introduction）

在無法利用线性结构表示的数据中，层级结构最常见。数据间存在上下级关系或包含关系时，就会产生层级结构。世界杯决赛的对阵表、公司或学校的组织结构图、网店商品的分类标准等，都具有层级结构。表示层级结构数据的数据结构就是树（tree）。若某一概念包含另一概念，就将两个概念连接为上下级形式。这种从一个上级概念分割出许多从属概念的形状与树非常相似，都可以转化为树结构解决。

2   问题概述（Problem overview）

在古代，为保护城堡，防止敌入侵，更好地守卫和保护更多领地，城堡中心都建有多层城墙，如图1所示。其中主建筑的Strawgoh要塞达到了这种建城模式的极致。巨大的圆形外墙包含若干圆形内墙，所有城墙均未设置城门。……