我有一个树状结构我可以把几条线连接起来组成这棵树。这些线由起点和终点组成下面是来自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>
下面是树的图形表示:
我需要做的是提取这棵树上的叶子和连接点,如图所示:
我想找到一个复杂的算法来处理这个任务的复杂性和时间。
最佳答案
从数据中生成一个数学图形(坐标是顶点的标签,数据中的每个line
都成为图形中的一条边)。
定义树的root vertex
。
叶是所有不是root vertex
且仅连接到一条边的顶点
连接点是连接到至少3条边的所有顶点(在您的示例中)