Опишите алгоритм, который по графу G и двум вершинам s и t определяет существует ли путь из одной вершины в другую.

задан 3 Мар 19:02

1

Такой алгоритм можно придумать самостоятельно, не зная никакой теории. Фиксируем вершину s, и присваиваем ей метку 0. Далее читаем список вершин, выбираем из них непомеченные. Если они соединены с s, помечаем их 1. Далее читаем список снова, отбирая непомеченные вершины, соединённые с вершинами с меткой 1. Им присваиваем метку 2. И так далее. Рано или поздно окажется, что новых меток не будет возникать. Тогда алгоритм прекращает работу, и метка каждой вершины даст расстояние от неё до s. Если нас интересует только t, то в случае её появления можно остановить алгоритм досрочно.

(3 Мар 19:10) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×507
×211
×130

задан
3 Мар 19:02

показан
100 раз

обновлен
3 Мар 19:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru