Всем привет.
Есть список ребер: [[1, 7], [3, 7], [5, 7], [3, 8], [2, 4], [4, 9], [5, 10], [6, 9], [4, 10]], где цифры - номера вершин. Нужно нарисовать дерево, чтобы ребра (линии) не пересекались, примерно вот так:
Если что, есть такое понятие как диаметр графа.
Его можно легко найти для дерева пустив обычную волну (bfs) от любой вершины, затем от самой дальней снова запустить (bfs). Последняя и предыдущая будут образовывать диаметр. Затем если поделить этот путь пополам, можно выбрать хорошую в некотором смысле вершину, за которую можно подвесить дерево, если оно не подвешено изначально.
Предлагаю рисовать рекурсивно. Нарисовать все поддеревья (обведены синим), потом корень (желтым). Каждое поддерево рисуем по тому же принципу. Если в поддереве 1 вершина -- просто рисуем ее.
Чтобы понять с каким отступом рисовать поддеревья, так же рекурсивно считаем ширину.
1. Находим корень дерева и рисуем его на рисунке;
2. Присвоить v корень;
3. Посчитать количество cu ребер таких, что существует [v, u];
4. 140 / cu (или что-то подобное, константы по вкусу) - угол нарисунке между ребрами. Зная угол и вертикальную состовляющую расстояния между уровнями дерева, вычисляем координаты на рисунке вершин u таких, что существует ребро [v, u];
5. Рисуем в вычисленных точках новые вершины. Для каждой из них выполнить алгоритм с пункта 2 (то есть каждая из u должна побывать раз в жизни v).
Простой
