меня есть отображение маршрутов в данной формеПоиск максимальной глубины дерева?
(a d)
(a b)
(b a)
(b c)
(b e)
(b f)
(c b)
(d a)
(e b)
(e g)
(g e)
(g f)
(f g)
(f b)
[где (а, г) означает Запись подключается для записи D]
Подключение все это из структуры графа. Я хочу найти максимальную глубину структуры графа. Это должно быть реализовано с помощью java.
Просто используйте глубину первого поиска и сохраняйте карту посещенных узлов (чтобы избежать циклов). Просто пойдите глубже, пока следующий ребенок еще не посещен. Возвращает 1 + глубину ребенка (0 в листовых узлах).
Но у меня нет определенного корневого узла в моей структуре графика, поэтому я смущен, откуда я должен начать свою DFS. – pkm
Если у вас нет явного корня и вы хотите найти максимальное расстояние, вам, вероятно, придется запускать его каждый раз с другим корнем и сравнивать значения. – ceekay
Максимальное расстояние не дает глубины структуры графика. Это дает самый длинный маршрут, и это намного больше, чем глубина графика. @ceekay – pkm
Вы пробовали это до сих пор? –
Покажите нам, что вы пробовали до сих пор. Здесь не здесь делать домашнее задание. Тем не менее, я уверен, что в Интернете есть достаточно алгоритмов, если вы за него заходите. – ceekay
Я пробовал. Получил очень близко к нему, но получил исключение в конце. И не знаю, как его исправить. – pkm