Оптимальное решение для поиска листьев дерева

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 ребрами (в вашем примере)