Блог

Я хотел бы удалить вершину (назовем ее B) из ориентированного графа без потери существующих путей между всеми оставшимися вершинами. Это означает, что если существует путь от некоторого узла A к некоторому узлу C, который включает B, B должен быть удален, но C должен быть по-прежнему доступен из A.

Допустим, мне нужно удалить вершину B в любом графике, а A и C — это любые узлы, связанные с B на графике. Для достижения результата достаточно выполнения такого алгоритма?

1) если существует путь A -> B -> C, удалите ссылки A -> B и B -> C и добавьте ссылку A -> C

2) если существует путь A <- B <- C, удалите ссылки A <- B и B <- C и добавьте ссылку A <- C

3) если существует ссылка A -> B или B -> A (которая не имеет ссылки на C, изображенной в случаях 1 и 2), удалите A -> B или B -> A

Ваш подход хорош. В принципе, если вы найдете всех соседей узла B и соедините их всех друг с другом (в ориентированном графе по направлению это имеет смысл), то вы можете быть уверены, что ни один путь не был потерян при удалении B.

Если есть какие-либо требования, такие как «создать как можно меньше новых соединений, при этом все узлы будут доступны в том виде, в каком они были до удаления» -> тогда решение может быть более сложным, т. е. имитировать удаление узла B и использовать dijsktra из каждого соседнего узла, чтобы выяснить, какой узел был потерян, и создавать только ребра к узлам, которые были потеряны процессом.