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. 根据您的数据生成数学图(坐标是顶点的标签，数据中的每条行都成为图中的一条边)。

2. 定义树的根顶点。

3. 叶子是所有不是根顶点并且只连接到一条边的顶点

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