На графе существует две особые вершины: синяя и красная. Задача состоит в том, чтобы при удалении красной вершины, также удалить все вершины из которых нельзя достичь синей, т.е. граф как бы должен распасться на два, один из которых подлежит удалению.
Мое решение состоит в том, чтобы проверить существование пути из каждой вершины в синюю. Если все пути очередной вершины проходят через красную, то производить удаление этой вершины.
Может существует более оптимальное решение?
Ответ
А если так:
Удалить красную вершину и все ребра, примыкающие к ней.
В получившемся графе провести поиск в глубину из синей вершины.
Найденная компонента связности и есть искомый результат.
Комментариев нет:
Отправить комментарий