0

Какой примерный план реализации кода этой задачи: Определить внешний радиус не взвешенного неориентированного графа методом обхода в ширину. (Внешним радиусом графа будем называть наибольшее среди кратчайших расстояние от центра до какого-либо узла. ) Вывести значение, а также соотвтуетсвующие ему цепи. Правильно ли я понимаю, что нужно найти центр этого графа, а потом найти кратчайший маршрут по алгоритму Дейкстры?

1
  • Вот здесь нужно принять ответ галочкой, если он понятен.
    – MBo
    8 дек 2020 в 8:03

1 ответ 1

0

Нет, Дейкстра тут ни при чём.

Выполняем поиск в ширину (BFS) из каждой вершины S. Получаем таблицу расстояний от всех вершин. Находим строку, максимальное значение в которой минимально по сравнению с другими строками. Она соответствует центру графа С, то самое значение - радиус графа R.

Выполняем ещё один поиск в ширину из С. Находим самую удалённую от неё вершину U. При втором обходе нужно записывать предшественника для каждой вершины, тогда после нахождения U разматываем предшественников до C (на R шагов) - это и есть нужная цепь.

3
  • первый раз - это поиск в ширину.
    – Daniyar
    8 дек 2020 в 9:40
  • второй раз - обход в ширину?
    – Daniyar
    8 дек 2020 в 9:41
  • Это одно и то же
    – MBo
    8 дек 2020 в 9:55

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.