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