@sashx

Как узнать расстояние между вершинами в дереве?

Друзья, здравствуйте! Не могу догадаться, как используя DFS я могу узнать расстояния между двумя введёнными вершинами в дереве? (Дерево неориентированное и не взвешенное)

Для примера из картинки:
Расстояние между 0 и 15 равно трём.

61d362cc07d79873350126.png
  • Вопрос задан
  • 215 просмотров
Пригласить эксперта
Ответы на вопрос 2
Alexandroppolus
@Alexandroppolus
кодир
Для такого дела BFS удобнее.
Складывая узлы в очередь, просто добавляй туда же расстояние (если у текущего обрабатываемого узла расстояние равно N, то попавшие в очередь чилды получают N+1)
Ответ написан
Комментировать
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Ваше дерево должно быть неориентированным. Просто список соседних вершин для каждой. А там запускайте от одной вершины DFS или BFS, который считает расстояние и выводит его, если дошли до второй вершины.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы