algorithm - 找到树的叶子的最佳解决方案

Question

我有一个树状结构。我可以得到几条连接在一起并组成树的线。线由起点和终点组成。这是来自 XML 格式的树的一些示例数据。

<Skeleton>
   <Line StartX="384" StartY="135"  EndX="385" EndY="129"  /> 
   <Line StartX="384" StartY="137"  EndX="384" EndY="135"  /> 
   <Line StartX="384" StartY="138"  EndX="384" EndY="137"  /> 
   <Line StartX="384" StartY="139"  EndX="384" EndY="138"  /> 
   <Line StartX="383" StartY="144"  EndX="384" EndY="139"  /> 
   <Line StartX="383" StartY="147"  EndX="383" EndY="144"  /> 
    ...
</Skeleton>

这是树的图形表示：

我需要做的是提取这棵树上的叶子和连接点，如图所示：

我想找到一个关于复杂性和时间的优化算法来完成这项任务。

Answer 1

1. 根据您的数据生成数学图（坐标是顶点的标签，line数据中的每个都成为图中的边）。

2. 定义root vertex你的树。

3. 叶子是不是root vertex只连接到一条边的所有顶点

4. 连接点是连接到至少 3 条边的所有顶点（在您的示例中）