Знакомство с графами
Немного познакомился с алгоритмами на графах. Решая одну весьма практическую задачу, я внезапно понял, что ее можно свести к абстрактной на графах.
Задача по удалению ненужного. Строим граф связанных друг с другом вещей, вершин. И нужно оставить только те вершины в графе, через которые есть путь от начала в конец. Остальное удалить.
Алгоритм Дейкстры по поиску кратчайшего пути здесь не подойдёт, поскольку он найдёт только 1 путь, а нужно сохранить все пути.
Использовал обход графа в глубину. С некоторыми нюансами.
Берём вершину, вначале это вершина Старт. Идём от неё в любом не посещённом направлении до тупика. Если дошли до финиша — хорошо, идём назад до ближайшей развилки и помечаем путь как транзитный. Если нет, то стираем за собой ветку. Дойдя назад до развилки, снова идём вперёд уже от этой вершины.
Если при шагах вперед, мы достигли вершины, которая имеет хотя бы одну транзитную связь — здесь тоже отлично, возвращаемся назад до первой развилки, помечая путь как транзитный.
Нюансы здесь такие, что посещенными должны быть связи между вершинами, а не сами вершины. Можно пройти одну и ту же вершину несколько раз, но по разным связям. Поскольку могут быть циклы, из которых, все-таки можно дойти от старта до финиша. Такие пути тоже считаются валидными, а значит их нужно сохранить.
Множественные связи, на одну и ту же вершину в тупиковом пути доставили много бед. Нужно удалять все связи на вершину при удалении самой вершины. Поэтому, чтобы не лазать по всему графу в поисках связей на такую вершину, эти связи можно сохранить в самой вершине.
И наконец нужно удалить вершины не достижимые из точки старта.
