Определите все начальные вершины, дающие дерево минимальной высоты, используя обход в глубину
Дерево задается матрицей смежности. Я поняла, что "вершины, дающие дерево минимальной высоты" это если взять вершинку за корень (получается перевернуть дерево), то будет минимально возможная длина.
Я поняла, что нужно как то использовать диаметр, но реализация создает трудности. Помогите пожалуйста советом или кусочком кода.
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Вы правильно диагностировали, диаметр к этой задаче имеет отношение. Но в ней нужно найти центр дерева - это одна или две вершины.
Для поиска центра используете всё тот же DFS. Нужно пошагово удалять листья (точнее, висячие вершины, корень тоже туда относится), пока не останется одна или две вершины.